Annals of Mathematical Sciences and Applications

Volume 1 (2016)

Number 2

Fast algorithm for periodic density fitting for Bloch waves

Pages: 321 – 339



Jianfeng Lu (Dept. of Mathematics, Dept. of Physics, and Dept. of Chemistry, Duke University, Durham, North Carolina, U.S.A.)

Lexing Ying (Department of Mathematics and Institute of Computational and Mathematical Engineering, Stanford University, California, U.S.A.)


We propose an efficient algorithm for density fitting of Bloch waves for Hamiltonian operators with periodic potential. The algorithm is based on column selection and random Fourier projection of the orbital functions. The computational cost of the algorithm scales as $\mathscr{O} (N_{\mathrm{grid}} N^2 + N_{\mathrm{grid}} N K \log(N K))$, where $N_{\mathrm{grid}}$ is number of spatial grid points, $K$ is the number of sampling $k$-points in first Brillouin zone, and $N$ is the number of bands under consideration. We validate the algorithm by numerical examples in both two and three dimensions.


density fitting, Bloch waves, column selection

2010 Mathematics Subject Classification

Primary 65Z05. Secondary 65F99.

Published 25 July 2016