Emanuel H. Rubensson

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson

In this paper, we present a local convergence analysis of the self-consistent field (SCF) iteration using the density matrix as the state of a fixed-point iteration. Sufficient and almost necessary conditions for local convergence are formulated in terms of the spectral radius of the Jacobian of a fixed-point map. The relationship between convergence and certain properties of the problem is explored by deriving upper bounds expressed in terms of higher gaps. This gives more information regarding how the gaps between eigenvalues of the problem affect the convergence, and hence these bounds are more insightful on the convergence behaviour than standard convergence results. We also provide a detailed analysis to describe the difference between the bounds and the exact convergence factor for an illustrative example. Finally we present numerical examples and compare the exact value of the convergence factor with the observed behaviour of SCF, along with our new bounds and the characterization using the higher gaps. We provide heuristic convergence factor estimates in situations where the bounds fail to well capture the convergence.

Emanuel H. Rubensson, Anders M. N. Niklasson

An accelerated polynomial expansion scheme to construct the density matrix in quantum mechanical molecular dynamics simulations is proposed. The scheme is based on recursive density matrix expansions, e.g. [Phys. Rev. B. 66 (2002), p. 155115], which are accelerated by a scale-and-fold technique [J. Chem. Theory Comput. 7 (2011), p. 1233]. The acceleration scheme requires interior eigenvalue estimates, which may be expensive and cumbersome to come by. Here we show how such eigenvalue estimates can be extracted from the recursive expansion by a simple and robust procedure at a negligible computational cost. Our method is illustrated with density functional tight-binding Born-Oppenheimer molecular dynamics simulations, where the computational effort is dominated by the density matrix construction. In our analysis we identify two different phases of the recursive polynomial expansion, the conditioning and purification phases, and we show that the acceleration represents an improvement of the conditioning phase, which typically gives a significant reduction of the computational cost.

Elias Jarlebring, Emanuel H. Rubensson

Consider a matrix function f defined for Hermitian matrices. The purpose of this paper is two-fold. We derive new results for the absolute structured condition number of the matrix function and we derive new bounds for the perturbation ||f(A+E)-f(A)|| expressed in terms of eigenvalues of A and A+E. The results are general and under certain conditions hold for an arbitrary unitarily invariant matrix norm ||\cdot||. We illustrate the use of the formulas with an application to the error analysis of calculations in electronic structure theory.

Emanuel H. Rubensson, Elias Jarlebring, Gustaf Lorentzon

We consider the problem of efficiently computing the matrix step function of a large dense symmetric matrix. To this end, we introduce a recursive polynomial expansion method in which a composite polynomial of high degree is built recursively from component polynomials of degree eight. The component polynomial used in each iteration is designed to achieve strong amplification of the spectral gap across the step while favorably positioning the updated gap for subsequent iterations. A key ingredient is a novel evaluation scheme for arbitrary matrix polynomials of degree exactly eight requiring only three matrix-matrix multiplications and three matrices in memory. This scheme makes available a substantially larger class of component polynomials than previously possible within a three-multiplication budget, thereby expanding the class of composite polynomials that can be generated. Together with our polynomial selection strategy, this leads to a significant and consistent reduction in the number of matrix-matrix multiplications required to compute the matrix step function compared to existing recursive expansion methods.

Emanuel H. Rubensson, Anton G. Artemov, Anastasia Kruchinina et al.

We propose a localized divide and conquer algorithm for inverse factorization $S^{-1} = ZZ^*$ of Hermitian positive definite matrices $S$ with localized structure, e.g. exponential decay with respect to some given distance function on the index set of $S$. The algorithm is a reformulation of recursive inverse factorization [J. Chem. Phys., 128 (2008), 104105] but makes use of localized operations only. At each level of recursion, the problem is cut into two subproblems and their solutions are combined using iterative refinement [Phys. Rev. B, 70 (2004), 193102] to give a solution to the original problem. The two subproblems can be solved in parallel without any communication and, using the localized formulation, the cost of combining their results is proportional to the cut size, defined by the binary partition of the index set. This means that for cut sizes increasing as $o(n)$ with system size $n$ the cost of combining the two subproblems is negligible compared to the overall cost for sufficiently large systems. We also present an alternative derivation of iterative refinement based on a sign matrix formulation, analyze the stability, and propose a parameterless stopping criterion. We present bounds for the initial factorization error and the number of iterations in terms of the condition number of $S$ when the starting guess is given by the solution of the two subproblems in the binary recursion. These bounds are used in theoretical results for the decay properties of the involved matrices. The localization properties of our algorithms are demonstrated for matrices corresponding to nearest neighbor overlap on one-, two-, and three-dimensional lattices as well as basis set overlap matrices generated using the Hartree-Fock and Kohn-Sham density functional theory electronic structure program Ergo [SoftwareX, 7 (2018), 107].