Hermitian Pseudospectral Shattering, Cholesky, Hermitian Eigenvalues, and Density Functional Theory in Nearly Matrix Multiplication Time

Floating point algorithms are studied for computational problems arising in Density Functional Theory (DFT), a powerful technique to determine the electronic structure of solids, e.g., metals, oxides, or semiconductors. Specifically, we seek algorithms with provable properties for the density matrix and the corresponding electron density in atomic systems described by the Kohn-Sham equations expressed in a localized basis set. The underlying problem is a Hermitian generalized eigenvalue problem of the form $HC=SCE$, where $H$ is Hermitian and $S$ is Hermitian positive-definite (HPD). Different methods are developed and combined to solve this problem. We first describe a Hermitian pseudospectral shattering method in finite precision, and use it to obtain a new gap-independent floating point algorithm to compute all eigenvalues of a Hermitian matrix within an additive error $\delta$ in $O(T_{MM}(n)\log^2(\tfrac{n}{\delta}))$. Here $T_{MM}(n) = O(n^{\omega+\eta})$, for any $\eta>0$, and $\omega\leq 2.371552$ is the matrix multiplication exponent. To the best of our knowledge, this is the first algorithm to achieve nearly $O(n^\omega)$ bit complexity for all Hermitian eigenvalues. As by-products, we also demonstrate additive error approximations for all singular values of rectangular matrices, and, for full-rank matrices, relative error approximations for all eigenvalues, all singular values, the spectral norm, and the condition number. We finally provide a novel analysis of a logarithmically-stable Cholesky factorization algorithm, and show that it can be used to accurately transform the HPD generalized eigenproblem to a Hermitian eigenproblem in $O(T_{MM}(n))$. All these tools are combined to obtain the first provably accurate floating point algorithms with nearly $O(T_{MM}(n))$ bit complexity for the density matrix and the electron density of atomic systems.