research-article

Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods

Authors:

Andreas Stathopoulos,

Kesheng WuAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 19, Issue 1

Pages 227 - 245

https://doi.org/10.1137/S1064827596304162

Published: 01 January 1998 Publication History

Abstract

The Davidson method is a popular preconditioned variant of the Arnoldi method for solving large eigenvalue problems. For theoretical as well as practical reasons the two methods are often used with restarting. Frequently, information is saved through approximated eigenvectors to compensate for the convergence impairment caused by restarting. We call this scheme of retaining more eigenvectors than needed "thick restarting" and prove that thick restarted, nonpreconditioned Davidson is equivalent to the implicitly restarted Arnoldi. We also establish a relation between thick restarted Davidson and a Davidson method applied on a deflated system. The theory is used to address the question of which and how many eigenvectors to retain and motivates the development of a dynamic thick restarting scheme for the symmetric case, which can be used in both Davidson and implicit restarted Arnoldi. Several experiments demonstrate the efficiency and robustness of the scheme.

References

[1]

Z. Bai, D. Day, J. Demmel, and J. Dongarra, A test matrix collection for non‐hermitian eigenvalue problems, tech. report, Department of Mathematics, University of Kentucky, September 30, 1996.

[2]

D. Calvetti, L. Reichel, D. Sorensen, An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electron. Trans. Numer. Anal., 2 (1994), 1–21

[3]

Andrew Chapman, Yousef Saad, Deflated and augmented Krylov subspace techniques, Numer. Linear Algebra Appl., 4 (1997), 43–66

[4]

Edmond Chow, Yousef Saad, Approximate inverse preconditioners via sparse‐sparse iterations, SIAM J. Sci. Comput., 19 (1998), 995–1023

Digital Library

[5]

P. Concus, G. H. Golub, and D. P. O’Leary, A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, Academic Press, New York, NY, 1976.

[6]

M. Crouzeix, B. Philippe, M. Sadkane, The Davidson method, SIAM J. Sci. Comput., 15 (1994), 62–76

Digital Library

[7]

J. Cullum and R. A. Willoughby, Lanczos algorithms for large symmetric eigenvalue computations, vol. 2: Programs of Progress in Scientific Computing; v. 4, Birkhauser, Boston, 1985.

[8]

E. 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), p. 87.

[9]

I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse matrix test problems, ACM Trans. Math. Soft., (1989), pp. 1–14.

[10]

D. R. Fokkema, G. L. G. Sleijpen, and H. A. Van der Vorst, Jacobi‐Davidson style QR and QZ algorithms for the partial reduction of matrix pencils, Tech. Report 941, Department of Mathematics, University of Utrecht, 1996.

To appear in SISC.

[11]

N. Kosugi, Modification of the Liu‐Davidson method for obtaining one or simultaneously several eigensolutions of a large real‐symmetric matrix, J. Comput. Phys., 55 (1984), pp. 426–436.

[12]

R. B. Lehoucq, Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration, PhD thesis, Department of Computational and Applied Mathematics, Rice University, 1995.

TR95‐13.

[13]

R. B. Lehoucq, D. C. Sorensen, and P. Vu, An implementation of the implicitly restarted Arnoldi iteration that computes some of the eigenvalues and eigenvectors of a large sparse matrix, tech. report, University of Tennessee, Netlib, 1995.

[14]

Ronald Morgan, A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl., 16 (1995), 1154–1171

Digital Library

[15]

Ronald Morgan, On restarting the Arnoldi method for large nonsymmetric eigenvalue problems, Math. Comp., 65 (1996), 1213–1230

Digital Library

[16]

Ronald Morgan, David Scott, Generalizations of Davidson’s method for computing eigenvalues of sparse symmetric matrices, SIAM J. Sci. Statist. Comput., 7 (1986), 817–825

Digital Library

[17]

C. W. Murray, S. C. Racine, and E. R. Davidson, Improved algorithms for the lowest eigenvalues and associated eigenvectors of large matrices, J. Comput. Phys., 103 (1992), pp. 382–389.

[18]

Youcef Saad, Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comp., 42 (1984), 567–588

[19]

Youcef Saad, Numerical methods for large eigenvalue problems, Algorithms and Architectures for Advanced Scientific Computing, Manchester University Press, 1992xii+346

[20]

Yousef Saad, Analysis of augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 18 (1997), 435–449

Digital Library

[21]

Miloud Sadkane, Block‐Arnoldi and Davidson methods for unsymmetric large eigenvalue problems, Numer. Math., 64 (1993), 195–211

Digital Library

[22]

D. Scott, The advantages of inverted operators in Rayleigh‐Ritz approximations, SIAM J. Sci. Statist. Comput., 3 (1982), 68–75

Digital Library

[23]

Gerard Sleijpen, Henk Van der Vorst, A Jacobi‐Davidson iteration method for linear eigenvalue problems, SIAM Rev., 42 (2000), 267–293

Digital Library

[24]

D. Sorensen, Implicit application of polynomial filters in a

k

‐step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), 357–385

Digital Library

[25]

A. Stathopoulos and C. Fischer, A Davidson program for finding a few selected extreme eigenpairs of a large, sparse, real, symmetric matrix, Computer Physics Communications, 79 (1994), pp. 268–290.

[26]

Andreas Stathopoulos, Yousef Saad, Charlotte Fischer, Robust preconditioning of large, sparse, symmetric eigenvalue problems, J. Comput. Appl. Math., 64 (1995), 197–215

Digital Library

[27]

A. van der Sluis, H. van der Vorst, The rate of convergence of conjugate gradients, Numer. Math., 48 (1986), 543–560

Digital Library

[28]

H. A. Van der Vorst and C. Vuik, The superlinear convergence behavior of GMRES, Journal of computational and applied mathematics, 48 (1993), pp. 327–341.

Digital Library

[29]

Johan van Lenthe, Peter Pulay, A space‐saving modification of Davidson’s eigenvector algorithm, J. Comput. Chem., 11 (1990), 1164–1168

Digital Library

Cited By

Huang JJia Z(2023)A Cross-Product Free Jacobi–Davidson Type Method for Computing a Partial Generalized Singular Value Decomposition of a Large Matrix PairJournal of Scientific Computing10.1007/s10915-022-02053-w94:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s10915-022-02053-w
Huang JJia Z(2022)Two Harmonic Jacobi–Davidson Methods for Computing a Partial Generalized Singular Value Decomposition of a Large Matrix PairJournal of Scientific Computing10.1007/s10915-022-01993-793:2Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10915-022-01993-7
Shahzadeh Fazeli SEmad NLiu Z(2015)A key to choose subspace size in implicitly restarted Arnoldi methodNumerical Algorithms10.1007/s11075-014-9954-570:2(407-426)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s11075-014-9954-5
Show More Cited By

Index Terms

Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Partial differential equations
    2. Numerical analysis
      1. Computations on matrices

Index terms have been assigned to the content through auto-classification.

Recommendations

Implicitly Restarted GMRES and Arnoldi Methods for Nonsymmetric Systems of Equations

The generalized minimum residual method (GMRES) is well known for solving large nonsymmetric systems of linear equations. It generally uses restarting, which slows the convergence. However, some information can be retained at the time of the restart ...
Deflation Techniques for an Implicitly Restarted Arnoldi Iteration

A deflation procedure is introduced that is designed to improve the convergence of an implicitly restarted Arnoldi iteration for computing a few eigenvalues of a large matrix. As the iteration progresses, the Ritz value approximations of the ...
Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization
Numerical algorithms, parallelism and applications

A matrix-free algorithm, IRLANB, for the efficient computation of the smallest singular triplets of large and possibly sparse matrices is described. Key characteristics of the approach are its use of Lanczos bidiagonalization, implicit restarting, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 19, Issue 1

^* Special Issue on Iterative Methods for Solving Systems of Algebraic Equations

Jan 1998

319 pages

ISSN:1064-8275

Issue’s Table of Contents

Copyright © 1998 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1998

Author Tag

65F15

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang JJia Z(2023)A Cross-Product Free Jacobi–Davidson Type Method for Computing a Partial Generalized Singular Value Decomposition of a Large Matrix PairJournal of Scientific Computing10.1007/s10915-022-02053-w94:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s10915-022-02053-w
Huang JJia Z(2022)Two Harmonic Jacobi–Davidson Methods for Computing a Partial Generalized Singular Value Decomposition of a Large Matrix PairJournal of Scientific Computing10.1007/s10915-022-01993-793:2Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10915-022-01993-7
Shahzadeh Fazeli SEmad NLiu Z(2015)A key to choose subspace size in implicitly restarted Arnoldi methodNumerical Algorithms10.1007/s11075-014-9954-570:2(407-426)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s11075-014-9954-5
Liu ZEmad NAmor SLamure M(2015)PageRank Computation Using a Multiple Implicitly Restarted Arnoldi Method for Modeling Epidemic SpreadInternational Journal of Parallel Programming10.1007/s10766-014-0344-343:6(1028-1053)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s10766-014-0344-3
Romero ERoman J(2014)A parallel implementation of Davidson methods for large-scale eigenvalue problems in SLEPcACM Transactions on Mathematical Software10.1145/254369640:2(1-29)Online publication date: 5-Mar-2014
https://dl.acm.org/doi/10.1145/2543696
Zhou YChelikowsky JSaad Y(2014)Chebyshev-filtered subspace iteration method free of sparse diagonalization for solving the Kohn-Sham equationJournal of Computational Physics10.1016/j.jcp.2014.06.056274(770-782)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1016/j.jcp.2014.06.056
Aminikhah HJamalian A(2011)A new algorithm for computing eigenpairs of matricesMathematical and Computer Modelling: An International Journal10.1016/j.mcm.2011.01.04354:1-2(119-130)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1016/j.mcm.2011.01.043
Yamazaki IBai ZSimon HWang LWu K(2010)Adaptive Projection Subspace Dimension for the Thick-Restart Lanczos MethodACM Transactions on Mathematical Software10.1145/1824801.182480537:3(1-18)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1824801.1824805
Stathopoulos AMcCombs J(2010)PRIMMEACM Transactions on Mathematical Software10.1145/1731022.173103137:2(1-30)Online publication date: 23-Apr-2010
https://dl.acm.org/doi/10.1145/1731022.1731031
Li YYu SLi Y(2008)Parallel solution of large-scale eigenvalue problem for master equation in protein folding dynamicsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2007.09.00268:5(678-685)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.jpdc.2007.09.002
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents