Localized spectrum slicing

Lin, Lin

doi:10.1090/mcom/3166

Localized spectrum slicing
HTML articles powered by AMS MathViewer

by Lin Lin PDF

Math. Comp. 86 (2017), 2345-2371 Request permission

Abstract:

Given a sparse Hermitian matrix $A$ and a real number $\mu$, we construct a set of sparse vectors, each approximately spanned only by eigenvectors of $A$ corresponding to eigenvalues near $\mu$. This set of vectors spans the column space of a localized spectrum slicing (LSS) operator, and is called an LSS basis set. The sparsity of the LSS basis set is related to the decay properties of matrix Gaussian functions. We present a divide-and-conquer strategy with controllable error to construct the LSS basis set. This is a purely algebraic process using only submatrices of $A$, and can therefore be applied to general sparse Hermitian matrices. The LSS basis set leads to sparse projected matrices with reduced sizes, which allows the projected problems to be solved efficiently with techniques using sparse linear algebra. As an example, we demonstrate that the LSS basis set can be used to solve interior eigenvalue problems for a discretized second order partial differential operator in one-dimensional and two-dimensional domains, as well as for a matrix of general sparsity pattern.

References

Michele Benzi, Paola Boito, and Nader Razouk, Decay properties of spectral projectors with applications to electronic structure, SIAM Rev. 55 (2013), no. 1, 3–64. MR 3032838, DOI 10.1137/100814019
Michele Benzi and Gene H. Golub, Bounds for the entries of matrix functions with applications to preconditioning, BIT 39 (1999), no. 3, 417–438. MR 1708693, DOI 10.1023/A:1022362401426
Michele Benzi and Nader Razouk, Decay bounds and $O(n)$ algorithms for approximating functions of sparse matrices, Electron. Trans. Numer. Anal. 28 (2007/08), 16–39. MR 2455657
D. R. Bowler and T. Miyazaki, O(N) methods in electronic structure calculations, Rep. Prog. Phys. 75 (2012), 036503.
W. W. Bradbury and R. Fletcher, New iterative methods for solution of the eigenproblem, Numer. Math. 9 (1966), 259–267. MR 219230, DOI 10.1007/BF02162089
Ernest R. Davidson, The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices, J. Comput. Phys. 17 (1975), 87–94. MR 381271, DOI 10.1016/0021-9991(75)90065-0
Timothy A. Davis, John R. Gilbert, Stefan I. Larimore, and Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Trans. Math. Software 30 (2004), no. 3, 353–376. MR 2124396, DOI 10.1145/1024074.1024079
Timothy A. Davis and Yifan Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software 38 (2011), no. 1, Art. 1, 25. MR 2865011, DOI 10.1145/2049662.2049663
Stephen Demko, Inverses of band matrices and local convergence of spline projections, SIAM J. Numer. Anal. 14 (1977), no. 4, 616–619. MR 455281, DOI 10.1137/0714041
Stephen Demko, William F. Moss, and Philip W. Smith, Decay rates for inverses of band matrices, Math. Comp. 43 (1984), no. 168, 491–499. MR 758197, DOI 10.1090/S0025-5718-1984-0758197-9
Alan George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal. 10 (1973), 345–363. MR 388756, DOI 10.1137/0710032
S. Goedecker, Linear scaling electronic structure methods, Rev. Mod. Phys. 71 (1999), 1085–1123.
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Ralf Gruber and Jacques Rappaz, Finite element methods in linear ideal magnetohydrodynamics, Springer Series in Computational Physics, Springer-Verlag, Berlin, 1985. MR 800851, DOI 10.1007/978-3-642-86708-8
George Karypis and Vipin Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput. 20 (1998), no. 1, 359–392. MR 1639073, DOI 10.1137/S1064827595287997
Andrew V. Knyazev, New estimates for Ritz vectors, Math. Comp. 66 (1997), no. 219, 985–995. MR 1415802, DOI 10.1090/S0025-5718-97-00855-7
Andrew V. Knyazev, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput. 23 (2001), no. 2, 517–541. Copper Mountain Conference (2000). MR 1861263, DOI 10.1137/S1064827500366124
W. Kohn, Density functional and density matrix method scaling linearly with the number of atoms, Phys. Rev. Lett. 76 (1996), 3168–3171.
R. Lehoucq and D. Sorensen, Implicitly restarted Lanczos method (section 4.5), Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide (Philadelphia) (Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds.), SIAM, 2000, pp. 67–81.
L. Lin and J. Lu, Sharp decay estimates of discretized Green’s functions for Schrödinger type operators, arXiv:1511.07957 (2015).
L. Lin, J. Lu, L. Ying, and W. E, Adaptive local basis set for Kohn-Sham density functional theory in a discontinuous Galerkin framework I: Total energy calculation, J. Comput. Phys. 231 (2012), 2140–2154.
L. Lin and L. Ying, Element orbitals for Kohn-Sham density functional theory, Phys. Rev. B 85 (2012), 235144–235153.
Günter Meinardus, Approximation of functions: Theory and numerical methods, Expanded translation of the German edition, Springer Tracts in Natural Philosophy, Vol. 13, Springer-Verlag New York, Inc., New York, 1967. Translated by Larry L. Schumaker. MR 0217482
G. Nenciu, Existence of the exponentially localised Wannier functions, Comm. Math. Phys. 91 (1983), no. 1, 81–85. MR 719812
E. Polizzi, Density-matrix-based algorithm for solving eigenvalue problems, Phys. Rev. B 79 (2009), 115112–115117.
E. Prodan and W. Kohn, Nearsightedness of electronic matter, Proc. Natl. Acad. Sci. 102 (2005), 11635–11638.
Tetsuya Sakurai and Hiroshi Sugiura, A projection method for generalized eigenvalue problems using numerical integration, Proceedings of the 6th Japan-China Joint Seminar on Numerical Mathematics (Tsukuba, 2002), 2003, pp. 119–128. MR 2022322, DOI 10.1016/S0377-0427(03)00565-X
Grady Schofield, James R. Chelikowsky, and Yousef Saad, A spectrum slicing method for the Kohn-Sham problem, Comput. Phys. Commun. 183 (2012), no. 3, 497–505. MR 2875139, DOI 10.1016/j.cpc.2011.11.005
Hong Zhang, Barry Smith, Michael Sternberg, and Peter Zapol, SIPs: shift-and-invert parallel spectral transformations, ACM Trans. Math. Software 33 (2007), no. 2, Art. 9, 19. MR 2326953, DOI 10.1145/1236463.1236464