Atomistic simulations of the vertical propagation of perturbations in deep gravitationally compacted granular columns characterized by the intergrain potential Vδδn, with n2 and δ the grain overlap, are shown to recover the results of elasticity theory for weak perturbations. For strong perturbations, the sound velocity cstrong→cweak as z→ with the deviations from cweak best expressed via a certain recursion relation in z. We predict that voids in real granular columns lead to c1-ε, when the void fraction ε is small, and show that the velocity power spectrum of a grain resembles that of a harmonic oscillator chain as z→. © 1995 The American Physical Society.