Toward a general purpose linear scaling method for eigenvalue problems in Quantum Chemistry

Maxime Barrault

CERMICS - ENPC, 6 et 8 Avenue Blaise Pascal
Cité Descartes, Champs-sur-Marne, 77455 MARNE LA VALLEE Cedex 2

Eric Cancès
Véronique Duwig


Abstract

The most popular methods to solve the electronic problem in Quantum Chemistry consist in computing the projector D over the subspace generated by the eigenvectors associated with the lowest N eigenvalues of a real sparse symmetric matrix F whose dimension Nb grows proportionally to N with a typical ratio Nb ~ 10 N. This is achieved by a complete diagonalization of F computed by standard methods with complexity Nb^3, and therefore N^3. In terms of computational time, this step is the bottleneck of the standard methods in Computational Chemistry. In order to simulate large molecular systems (proteins, crystals) thousands of atoms at least have to be treated. Many groups have tried to develop methods which solve this specific sparse symmetric eigenvalue problem in a time proportional to N (``linear scaling methods''). So far, such methods have been designed in the particular case where it exists a sufficient gap between the N-th and (N+1)-th eigenvalues of the sparse matrix F. This mathematical property reflects some insulating behaviour and therefore holds true for non-metallic systems. In the case of metallic systems where the matrix F has a very small - even vanishing - gap, no linear scaling method is available. We propose here a method, based on deflation, which reduces the computational complexity of D to N^p with p ~ 2.