Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Localized spectrum slicing


Author: Lin Lin
Journal: Math. Comp. 86 (2017), 2345-2371
MSC (2010): Primary 65F60, 65F50, 65F15, 65N22
DOI: https://doi.org/10.1090/mcom/3166
Published electronically: January 9, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1137/100814019
  • [2] 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, https://doi.org/10.1023/A:1022362401426
  • [3] 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
  • [4] D. R. Bowler and T. Miyazaki, O(N) methods in electronic structure calculations, Rep. Prog. Phys. 75 (2012), 036503.
  • [5] W. W. Bradbury and R. Fletcher, New iterative methods for solution of the eigenproblem, Numer. Math. 9 (1966), 259-267. MR 0219230
  • [6] Ernest R. Davidson, The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices, J. Computational Phys. 17 (1975), 87-94. MR 0381271
  • [7] 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, https://doi.org/10.1145/1024074.1024079
  • [8] 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, https://doi.org/10.1145/2049662.2049663
  • [9] Stephen Demko, Inverses of band matrices and local convergence of spline projections, SIAM J. Numer. Anal. 14 (1977), no. 4, 616-619. MR 0455281
  • [10] 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, https://doi.org/10.2307/2008290
  • [11] Alan George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal. 10 (1973), 345-363. MR 0388756
  • [12] S. Goedecker, Linear scaling electronic structure methods, Rev. Mod. Phys. 71 (1999), 1085-1123.
  • [13] 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
  • [14] Ralf Gruber and Jacques Rappaz, Finite Element Methods in Linear Ideal Magnetohydrodynamics, Springer Series in Computational Physics, Springer-Verlag, Berlin, 1985. MR 800851
  • [15] 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 (electronic). MR 1639073, https://doi.org/10.1137/S1064827595287997
  • [16] Andrew V. Knyazev, New estimates for Ritz vectors, Math. Comp. 66 (1997), no. 219, 985-995. MR 1415802, https://doi.org/10.1090/S0025-5718-97-00855-7
  • [17] 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 (electronic). MR 1861263, https://doi.org/10.1137/S1064827500366124
  • [18] W. Kohn, Density functional and density matrix method scaling linearly with the number of atoms, Phys. Rev. Lett. 76 (1996), 3168-3171.
  • [19] 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.
  • [20] L. Lin and J. Lu, Sharp decay estimates of discretized Green's functions for Schrödinger type operators, arXiv:1511.07957 (2015).
  • [21] 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.
  • [22] L. Lin and L. Ying, Element orbitals for Kohn-Sham density functional theory, Phys. Rev. B 85 (2012), 235144-235153.
  • [23] Günter Meinardus, Approximation of Functions: Theory and Numerical Methods, Expanded translation of the German edition. Translated by Larry L. Schumaker. Springer Tracts in Natural Philosophy, Vol. 13, Springer-Verlag New York, Inc., New York, 1967. MR 0217482
  • [24] G. Nenciu, Existence of the exponentially localised Wannier functions, Comm. Math. Phys. 91 (1983), no. 1, 81-85. MR 719812
  • [25] E. Polizzi, Density-matrix-based algorithm for solving eigenvalue problems, Phys. Rev. B 79 (2009), 115112-115117.
  • [26] E. Prodan and W. Kohn, Nearsightedness of electronic matter, Proc. Natl. Acad. Sci. 102 (2005), 11635-11638.
  • [27] 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, https://doi.org/10.1016/S0377-0427(03)00565-X
  • [28] 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, https://doi.org/10.1016/j.cpc.2011.11.005
  • [29] 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, https://doi.org/10.1145/1236463.1236464

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F60, 65F50, 65F15, 65N22

Retrieve articles in all journals with MSC (2010): 65F60, 65F50, 65F15, 65N22


Additional Information

Lin Lin
Affiliation: Department of Mathematics, University of California Berkeley and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, California 94720
Email: linlin@math.berkeley.edu

DOI: https://doi.org/10.1090/mcom/3166
Keywords: Spectrum slicing, localization, decay properties, basis set, interior eigenvalue problem
Received by editor(s): November 20, 2014
Received by editor(s) in revised form: October 10, 2015, and March 16, 2016
Published electronically: January 9, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society