Deflation by restriction for the inverse-free preconditioned Krylov subspace method

Qiao  Liang; Qiang  Ye

doi:10.3934/naco.2016.6.55

Article Contents

2016, Volume 6, Issue 1: 55-71. Doi: 10.3934/naco.2016.6.55

This issue Previous Article A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities Next Article Projection-based model reduction for time-varying descriptor systems: New results

Deflation by restriction for the inverse-free preconditioned Krylov subspace method

Qiao Liang^1, and
Qiang Ye^1,

1.
Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027

Received: June 2015

Revised: December 2015

Published: January 2016

Abstract / Introduction Related Papers Cited by

Abstract

A deflation by restriction scheme is developed for the inverse-free preconditioned Krylov subspace method for computing a few extreme eigenvalues of the definite symmetric generalized eigenvalue problem $Ax = \lambda Bx$. The convergence theory for the inverse-free preconditioned Krylov subspace method is generalized to include this deflation scheme and numerical examples are presented to demonstrate the convergence properties of the algorithm with the deflation scheme.

Keywords:

Mathematics Subject Classification: Primary: 65F15.

Citation:

Related Papers

Cited by

References

[1]	Z. Bai, J. Demmel, J. Dongarra, A. Ruhe and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, PA, 2000.doi: 10.1137/1.9780898719581.
[2]	L. Bergamaschi, G. Pini and F. Sartoretto, Approximate inverse preconditioning in the parallel solution of sparse eigenproblems, Numer. Linear Alg. Appl., 7 (2000), 99-116.doi: 10.1002/(SICI)1099-1506(200004/05)7:3<99::AID-NLA188>3.3.CO;2-X.
[3]	J. Bramble, J. Pasciak and A. Knyazev, A subspace preconditioning algorithm for eigenvector/eigenvalue computation, Adv. Comp. Math., 6 (1996), 150-189.doi: 10.1007/BF02127702.
[4]	D. Fokkema, G. Sleijpen and H. Van der Vorst, Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. Sci. Comput, 20 (1999), 94-125.doi: 10.1137/S1064827596300073.
[5]	G. H. Golub and Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM Journal on Scientific Computing, 24 (2002), 312-334.doi: 10.1137/S1064827500382579.
[6]	A. V. Knyazev, Preconditioned eigensolvers-an oxymoron, Electronic Transactions on Numerical Analysis, 7 (1998), 104-123.
[7]	A. V. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient, SIAM Journal on Scientific Computing, 23 (2001), 517-541.doi: 10.1137/S1064827500366124.
[8]	Q. Liang and Q. Ye, Computing singular values of large matrices with an inverse-free preconditioned krylov subspace method, Electronic Transactions on Numerical Analysis, 42 (2014), 197-221.
[9]	R. B. Lehoucq, Analysis And Implementation of An Implicitly Restarted Arnoldi Iteration, Ph.D Thesis, Rice University, 1995.
[10]	R. B. Lehoucq and D. C. Sorensen, Deflation techniques within an implicitly restarted Arnoldi iteration, SIAM Journal on Matrix Analysis and Applications, 17 (1996), 789-821.doi: 10.1137/S0895479895281484.
[11]	R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK Users' Guides, Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Method, SIAM, Philadelphia, 1998.doi: 10.1137/1.9780898719628.
[12]	R. Lehoucq and K. Meerbergen, The inexact rational Krylov sequence method, SIAM J. Matrix Anal. Appl., 20 (1998), 131-148.doi: 10.1137/S0895479896311220.
[13]	K. Meerbergen and D. Roose, The restarted Arnoldi method applied to iterative linear solvers for the computation of rightmost eigenvalues, SIAM J. Matrix Anal. Appl., 20 (1999), 1-20.doi: 10.1137/S0895479894274255.
[14]	J. H. Money and Q. Ye, Algorithm 845: EIGIFP: A MATLAB program for solving large symmetric generalized eigenvalue problems, ACM Transactions on Mathematical Software, 31 (2005), 270-279.doi: 10.1145/1067967.1067973.
[15]	R. Morgan and D. Scott, Preconditioning the Lanczos algorithm for sparse symmetric eigenvalue problems, SIAM J. Sci. Stat. Comput., 14 (1993), 585-593.doi: 10.1137/0914037.
[16]	Y. Notay, Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem, Numerical Linear Algebra and its Applications, 9 (2002), 21-44.doi: 10.1002/nla.246.
[17]	B. N. Parlett, The Symmetric Eigenvalue Problem, Classics in Applied Mathematics, SIAM, Philadelphia, PA, 1998.doi: 10.1137/1.9781611971163.
[18]	P. Quillen and Q. Ye, A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, J. Comp. Appl. Math, 233 (2010), 1298-1313.doi: 10.1016/j.cam.2008.10.071.
[19]	Y. Saad, Numerical methods for large eigenvalue problems, Revised Edition, Classics in Applied Mathematics, SIAM, Philadelphia, 2011.doi: 10.1137/1.9781611970739.ch1.
[20]	G. Sleijpen and H. van der Vorst, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM Journal on Matrix Analysis and Applications, 17 (1996), 401-425.doi: 10.1137/S0895479894270427.
[21]	A. Stathopoulos and J. R. McCombs, PRIMME: PReconditioned Iterative MultiMethod Eigensolver: Methods and software description, ACM Transaction on Mathematical Software, 37 (2010), 21:1-21:30.
[22]	A. Stathopoulos, Y. Saad and C. Fisher, Robust preconditioning of large sparse symmetric eigenvalue problems, J. Comp. Appl. Math., 64 (1995), 197-215.doi: 10.1016/0377-0427(95)00141-7.
[23]	H. van der Vorst, G. Sleijpen and M. van Gijzen, Efficient expansion of subspaces in the Jacobi-Davison method for standard and generalized eigenproblems, Electronic Transactions on Numerical Analysis, 7 (1998), 75-89.
[24]	E. Vecharynski, C. Yang and F. Xue, Generalized preconditioned locally harmonic residual method for non-Hermitian eigenproblems, Preprint.
[25]	J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, New York, 1965.
[26]	C. Yang, Convergence analysis of an inexact truncated RQ iterations, Elec. Trans. Numer. Anal., 7 (1998), 40-55.