On the subspace projected approximate matrix method

Jan Brandts; Ricardo Reis da Silva

Applications of Mathematics (2015)

  • Volume: 60, Issue: 4, page 421-452
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Brandts, Jan, and Reis da Silva, Ricardo. "On the subspace projected approximate matrix method." Applications of Mathematics 60.4 (2015): 421-452. <http://eudml.org/doc/271649>.

@article{Brandts2015,
abstract = {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.},
author = {Brandts, Jan, Reis da Silva, Ricardo},
journal = {Applications of Mathematics},
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},
language = {eng},
number = {4},
pages = {421-452},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the subspace projected approximate matrix method},
url = {http://eudml.org/doc/271649},
volume = {60},
year = {2015},
}

TY - JOUR
AU - Brandts, Jan
AU - Reis da Silva, Ricardo
TI - On the subspace projected approximate matrix method
JO - Applications of Mathematics
PY - 2015
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 60
IS - 4
SP - 421
EP - 452
AB - 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.
LA - eng
KW - 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
UR - http://eudml.org/doc/271649
ER -

References

top
  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). (2000) Zbl0965.65058MR1792141
  2. Bauer, F. L., Fike, C. T., 10.1007/BF01386217, Numer. Math. 2 (1960), 137-141. (1960) Zbl0101.25503MR0118729DOI10.1007/BF01386217
  3. Beattie, C., Harmonic Ritz and Lehmann bounds, ETNA, Electron. Trans. Numer. Anal. 7 18-39 (1998). (1998) Zbl0918.65027MR1665476
  4. Brandts, J., The Riccati algorithm for eigenvalues and invariant subspaces of matrices with inexpensive action, Linear Algebra Appl. 358 335-365 (2003). (2003) Zbl1030.65022MR1942737
  5. Brandts, J., Silva, R. R. da, 10.4208/eajam.070213.280513a, East Asian J. Appl. Math. 3 120-137 (2013). (2013) Zbl1287.65021MR3109561DOI10.4208/eajam.070213.280513a
  6. Chen, W., Poirier, B., 10.1016/j.jcp.2006.03.031, J. Comput. Phys. 219 (2006), 198-209. (2006) Zbl1106.65025MR2273374DOI10.1016/j.jcp.2006.03.031
  7. Ciarlet, P. G., (eds.), J. L. Lions, Handbook of Numerical Analysis. Volume II: Finite Element Methods (Part 1), North-Holland, Amsterdam (1991). (1991) Zbl0712.65091MR1115235
  8. Crouzeix, M., Philippe, B., Sadkane, M., 10.1137/0915004, SIAM J. Sci. Comput. 15 62-76 (1994). (1994) Zbl0803.65042MR1257154DOI10.1137/0915004
  9. Davidson, E. R., 10.1016/0021-9991(75)90065-0, J. Comput. Phys. 17 87-94 (1975). (1975) Zbl0293.65022MR0381271DOI10.1016/0021-9991(75)90065-0
  10. Genseberger, M., Sleijpen, G. L. G., 10.1002/(SICI)1099-1506(199904/05)6:3<235::AID-NLA166>3.0.CO;2-8, Numer. Linear Algebra Appl. 6 (1999), 235-253. (1999) Zbl0983.65047MR1706333DOI10.1002/(SICI)1099-1506(199904/05)6:3<235::AID-NLA166>3.0.CO;2-8
  11. Golub, G. H., Vorst, H. A. van der, 10.1016/S0377-0427(00)00413-1, J. Comput. Appl. Math. 123 (2000), 35-65. (2000) MR1798518DOI10.1016/S0377-0427(00)00413-1
  12. Golub, G. H., Loan, C. F. van, Matrix Computations, The Johns Hopkins Univ. Press Baltimore (1996). (1996) MR1417720
  13. Győrffy, W., Seidler, P., Christiansen, O., 10.1063/1.3154382, J. Chem. Phys. 131 (2009), 024108. (2009) DOI10.1063/1.3154382
  14. Jia, Z., Stewart, G. W., 10.1090/S0025-5718-00-01208-4, Math. Comput. 70 637-647 (2001). (2001) Zbl0968.65020MR1697647DOI10.1090/S0025-5718-00-01208-4
  15. Lanczos, C., 10.6028/jres.045.026, J. Research Nat. Bur. Standards 45 (1950), 255-282. (1950) MR0042791DOI10.6028/jres.045.026
  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. (2005) 
  17. Morgan, R. B., Scott, D. S., 10.1137/0907054, SIAM J. Sci. Stat. Comput. 7 (1986), 817-825. (1986) Zbl0602.65020MR0848565DOI10.1137/0907054
  18. Paige, C. C., Saunders, M. S., 10.1137/0712047, SIAM J. Numer. Anal. 12 (1975), 617-629. (1975) Zbl0319.65025MR0383715DOI10.1137/0712047
  19. Parlett, B. N., The Symmetric Eigenvalue Problem, Classics in Applied Mathematics 20 SIAM, Philadelphia (1998). (1998) Zbl0885.65039MR1490034
  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. (2005) 
  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. (2001) Zbl0986.65027MR1857613
  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). (2003) MR1942726
  23. Sleijpen, G. L. G., Vorst, H. A. van der, 10.1137/S0895479894270427, SIAM J. Matrix Anal. Appl. 17 (1996), 401-425. (1996) MR1384515DOI10.1137/S0895479894270427
  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. (1996) 
  25. Sleijpen, G. L. G., Vorst, H. A. van der, 10.1137/S0036144599363084, SIAM Rev. 42 267-293 (2000). (2000) MR1778354DOI10.1137/S0036144599363084
  26. Sorensen, D. C., 10.1137/0613025, SIAM J. Matrix Anal. Appl. 13 (1992), 357-385. (1992) Zbl0763.65025MR1146670DOI10.1137/0613025
  27. Stewart, G. W., Matrix Algorithms. Vol. 2: Eigensystems, SIAM, Philadelphia (2001). (2001) Zbl0984.65031MR1853468
  28. Stewart, G. W., 10.1137/S0895479800371529, SIAM J. Matrix Anal. Appl. 23 (2002), 601-614 addendum ibid. 24 599-601 (2002). (2002) MR1896808DOI10.1137/S0895479800371529
  29. Stewart, G. W., Sun, J. G., Matrix Perturbation Theory, Computer Science and Scientific Computing Academic Press, Boston (1990). (1990) Zbl0706.65013MR1061154
  30. Wrobel, L. C., Aliabadi, M. H., The Boundary Element Method. Vol. 1: Applications in Thermo-Fluids and Acoustics, Wiley, Chichester (2002). (2002) Zbl0994.74002
  31. Zhou, Y., Shepard, R., Minkoff, M., 10.1016/j.cpc.2004.12.013, Comput. Phys. Commun. 167 (2005), 90-102. (2005) Zbl1196.15007MR2124799DOI10.1016/j.cpc.2004.12.013

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.