Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
Hermitian eigenproblem; Ritz-Galerkin approximation; subspace projected approximate matrix; Lanczos method; Jacobi-Davidson method
Hermitian eigenproblem; Ritz-Galerkin approximation; subspace projected approximate matrix; Lanczos method; Jacobi-Davidson method
Summary:
We provide a comparative study of the Subspace Projected Approximate Matrix method, abbreviated SPAM, which is a fairly recent iterative method of computing a few eigenvalues of a Hermitian matrix $A$. It falls in the category of inner-outer iteration methods and aims to reduce the costs of matrix-vector products with $A$ within its inner iteration. This is done by choosing an approximation $A_0$ of $A$, and then, based on both $A$ and $A_0$, to define a sequence $(A_k)_{k=0}^n$ of matrices that increasingly better approximate $A$ as the process progresses. Then the matrix $A_k$ is used in the $k$th inner iteration instead of $A$. In spite of its main idea being refreshingly new and interesting, SPAM has not yet been studied in detail by the numerical linear algebra community. We would like to change this by explaining the method, and to show that for certain special choices for $A_0$, SPAM turns out to be mathematically equivalent to known eigenvalue methods. More sophisticated approximations $A_0$ turn SPAM into a boosted version of Lanczos, whereas it can also be interpreted as an attempt to enhance a certain instance of the preconditioned Jacobi-Davidson method. Numerical experiments are performed that are specifically tailored to illustrate certain aspects of SPAM and its variations. For experiments that test the practical performance of SPAM in comparison with other methods, we refer to other sources. The main conclusion is that SPAM provides a natural transition between the Lanczos method and one-step preconditioned Jacobi-Davidson.
References:
[1] Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., (eds.), H. van der Vorst: Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Software-Environments-Tools. 11 SIAM, Philadelphia (2000). MR 1792141 | Zbl 0965.65058
[2] Bauer, F. L., Fike, C. T.: Norms and exclusion theorems. Numer. Math. 2 (1960), 137-141. DOI 10.1007/BF01386217 | MR 0118729 | Zbl 0101.25503
[3] Beattie, C.: Harmonic Ritz and Lehmann bounds. ETNA, Electron. Trans. Numer. Anal. 7 18-39 (1998). MR 1665476 | Zbl 0918.65027
[4] Brandts, J.: The Riccati algorithm for eigenvalues and invariant subspaces of matrices with inexpensive action. Linear Algebra Appl. 358 335-365 (2003). MR 1942737 | Zbl 1030.65022
[5] Brandts, J., Silva, R. R. da: A subspace-projected approximate matrix method for systems of linear equations. East Asian J. Appl. Math. 3 120-137 (2013). DOI 10.4208/eajam.070213.280513a | MR 3109561 | Zbl 1287.65021
[6] Chen, W., Poirier, B.: Parallel implementation of efficient preconditioned linear solver for grid-based applications in chemical physics. II: QMR linear solver. J. Comput. Phys. 219 (2006), 198-209. DOI 10.1016/j.jcp.2006.03.031 | MR 2273374 | Zbl 1106.65025
[7] Ciarlet, P. G., (eds.), J. L. Lions: Handbook of Numerical Analysis. Volume II: Finite Element Methods (Part 1). North-Holland, Amsterdam (1991). MR 1115235 | Zbl 0712.65091
[8] Crouzeix, M., Philippe, B., Sadkane, M.: The Davidson method. SIAM J. Sci. Comput. 15 62-76 (1994). DOI 10.1137/0915004 | MR 1257154 | Zbl 0803.65042
[9] Davidson, E. R.: The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices. J. Comput. Phys. 17 87-94 (1975). DOI 10.1016/0021-9991(75)90065-0 | MR 0381271 | Zbl 0293.65022
[10] Genseberger, M., Sleijpen, G. L. G.: Alternative correction equations in the Jacobi-Davidson method. Numer. Linear Algebra Appl. 6 (1999), 235-253. DOI 10.1002/(SICI)1099-1506(199904/05)6:3<235::AID-NLA166>3.0.CO;2-8 | MR 1706333 | Zbl 0983.65047
[11] Golub, G. H., Vorst, H. A. van der: Eigenvalue computation in the 20th century. J. Comput. Appl. Math. 123 (2000), 35-65. DOI 10.1016/S0377-0427(00)00413-1 | MR 1798518
[12] Golub, G. H., Loan, C. F. van: Matrix Computations. The Johns Hopkins Univ. Press Baltimore (1996). MR 1417720
[13] Győrffy, W., Seidler, P., Christiansen, O.: Solving the eigenvalue equations of correlated vibrational structure methods: preconditioning and targeting strategies. J. Chem. Phys. 131 (2009), 024108. DOI 10.1063/1.3154382
[14] Jia, Z., Stewart, G. W.: An analysis of the Rayleigh-Ritz method for approximating eigenspaces. Math. Comput. 70 637-647 (2001). DOI 10.1090/S0025-5718-00-01208-4 | MR 1697647 | Zbl 0968.65020
[15] Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Research Nat. Bur. Standards 45 (1950), 255-282. DOI 10.6028/jres.045.026 | MR 0042791
[16] Medvedev, D. M., Gray, S. K., Wagner, A. F., Minkoff, M., Shepard, R.: Advanced software for the calculation of thermochemistry, kinetics, and dynamics. J. Phys.: Conf. Ser. 16 (2005), 247-251.
[17] Morgan, R. B., Scott, D. S.: Generalizations of Davidson's method for computing eigenvalues of sparse symmetric matrices. SIAM J. Sci. Stat. Comput. 7 (1986), 817-825. DOI 10.1137/0907054 | MR 0848565 | Zbl 0602.65020
[18] Paige, C. C., Saunders, M. S.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12 (1975), 617-629. DOI 10.1137/0712047 | MR 0383715 | Zbl 0319.65025
[19] Parlett, B. N.: The Symmetric Eigenvalue Problem. Classics in Applied Mathematics 20 SIAM, Philadelphia (1998). MR 1490034 | Zbl 0885.65039
[20] Ribeiro, F., Lung, C., Leforestier, C.: A Jacobi-Wilson description coupled to a block-Davidson algorithm: an efficient scheme to calculate highly excited vibrational levels. J. Chem. Phys. 123 (2005), 054106.
[21] Shepard, R., Wagner, A. F., Tilson, J. L., Minkoff, M.: The subspace projected approximate matrix (SPAM) modification of the Davidson method. J. Comput. Phys. (2001), 172 472-514. MR 1857613 | Zbl 0986.65027
[22] Sleijpen, G. L. G., Eshof, J. van den: On the use of harmonic Ritz pairs in approximating internal eigenpairs. Linear Algebra Appl. 358 115-137 (2003). MR 1942726
[23] Sleijpen, G. L. G., Vorst, H. A. van der: A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM J. Matrix Anal. Appl. 17 (1996), 401-425. DOI 10.1137/S0895479894270427 | MR 1384515
[24] Sleijpen, G. L. G., Vorst, H. A. van der: The Jacobi-Davidson method for eigenvalue problems and its relation with accelerated inexact Newton schemes. Iterative Method in Linear Algebra II S. D. Margenov, P. S. Vassilevski IMACS Ann. Comput. Appl. Math. 3 (1996), 377-389.
[25] Sleijpen, G. L. G., Vorst, H. A. van der: A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM Rev. 42 267-293 (2000). DOI 10.1137/S0036144599363084 | MR 1778354
[26] Sorensen, D. C.: Implicit application of polynomial filters in a $k$-step Arnoldi method. SIAM J. Matrix Anal. Appl. 13 (1992), 357-385. DOI 10.1137/0613025 | MR 1146670 | Zbl 0763.65025
[27] Stewart, G. W.: Matrix Algorithms. Vol. 2: Eigensystems. SIAM, Philadelphia (2001). MR 1853468 | Zbl 0984.65031
[28] Stewart, G. W.: A Krylov-Schur algorithm for large eigenproblems. SIAM J. Matrix Anal. Appl. 23 (2002), 601-614 addendum ibid. 24 599-601 (2002). DOI 10.1137/S0895479800371529 | MR 1896808
[29] Stewart, G. W., Sun, J. G.: Matrix Perturbation Theory. Computer Science and Scientific Computing Academic Press, Boston (1990). MR 1061154 | Zbl 0706.65013
[30] Wrobel, L. C., Aliabadi, M. H.: The Boundary Element Method. Vol. 1: Applications in Thermo-Fluids and Acoustics. Wiley, Chichester (2002). Zbl 0994.74002
[31] Zhou, Y., Shepard, R., Minkoff, M.: Computing eigenvalue bounds for iterative subspace matrix methods. Comput. Phys. Commun. 167 (2005), 90-102. DOI 10.1016/j.cpc.2004.12.013 | MR 2124799 | Zbl 1196.15007
Search
Partner of
