Robust and efficient design of algorithms in quantum chemistry: the case of Davidson's diagonalization

In this chapter, we discuss the efficient and robust design of algorithms using Davidson's diagonalization, both in the general case and in its application to the solution of the linear response equations, with particular emphasis on the numerical aspects. After introducing some general concepts of numerical analysis, in particular, the floating-point representation of real numbers and the conditioning of a matrix, we illustrate Davidson's algorithm for computing a few eigenvalues and eigenvectors of a large, possibly sparse matrix. We discuss in detail the orthogonalization of a set of vectors to an existing set, a step required in the Davidson's algorithm, and how this can be a source of numerical problems: we then propose a computationally efficient and robust strategy to address all such issues. Finally, we illustrate a few principles of algorithm design using as an example of the adaptation of Davidson's method to the solution of the linear response equations.