  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.
