  Phonon calculations based on first principle electronic structure theory,
such as the Kohn-Sham density functional theory, have wide applications in
physics, chemistry and material science. The computational cost of first
principle phonon calculations typically scales steeply as $\mathcal{O}(N_e^4)$,
where $N_e$ is the number of electrons in the system. In this work, we develop
a new method to reduce the computational complexity of computing the full
dynamical matrix, and hence the phonon spectrum, to $\mathcal{O}(N_e^3)$. The
key concept for achieving this is to compress the polarizability operator
adaptively with respect to the perturbation of the potential due to the change
of the atomic configuration. Such adaptively compressed polarizability operator
(ACP) allows accurate computation of the phonon spectrum. The reduction of
complexity only weakly depends on the size of the band gap, and our method is
applicable to insulators as well as semiconductors with small band gaps. We
demonstrate the effectiveness of our method using one-dimensional and
two-dimensional model problems.
