American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Projection-based model reduction for time-varying descriptor systems: New results
  • NACO Home
  • This Issue
  • Next Article
    A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities
2016, 6(1): 55-71. doi: 10.3934/naco.2016.6.55

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, United States, United States

Received  June 2015 Revised  December 2015 Published  January 2016

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: Generalized eigenvalue problem, Krylov subspace, deflation..
Mathematics Subject Classification: Primary: 65F1.
Citation: Qiao Liang, Qiang Ye. Deflation by restriction for the inverse-free preconditioned Krylov subspace method. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 55-71. doi: 10.3934/naco.2016.6.55
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, (2000). doi: 10.1137/1.9780898719581. Google Scholar

[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. doi: 10.1002/(SICI)1099-1506(200004/05)7:3<99::AID-NLA188>3.3.CO;2-X. Google Scholar

[3]

J. Bramble, J. Pasciak and A. Knyazev, A subspace preconditioning algorithm for eigenvector/eigenvalue computation,, Adv. Comp. Math., 6 (1996), 150. doi: 10.1007/BF02127702. Google Scholar

[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. doi: 10.1137/S1064827596300073. Google Scholar

[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. doi: 10.1137/S1064827500382579. Google Scholar

[6]

A. V. Knyazev, Preconditioned eigensolvers-an oxymoron,, Electronic Transactions on Numerical Analysis, 7 (1998), 104. Google Scholar

[7]

A. V. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient,, SIAM Journal on Scientific Computing, 23 (2001), 517. doi: 10.1137/S1064827500366124. Google Scholar

[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. Google Scholar

[9]

R. B. Lehoucq, Analysis And Implementation of An Implicitly Restarted Arnoldi Iteration,, Ph.D Thesis, (1995). Google Scholar

[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. doi: 10.1137/S0895479895281484. Google Scholar

[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, (1998). doi: 10.1137/1.9780898719628. Google Scholar

[12]

R. Lehoucq and K. Meerbergen, The inexact rational Krylov sequence method,, SIAM J. Matrix Anal. Appl., 20 (1998), 131. doi: 10.1137/S0895479896311220. Google Scholar

[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. doi: 10.1137/S0895479894274255. Google Scholar

[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. doi: 10.1145/1067967.1067973. Google Scholar

[15]

R. Morgan and D. Scott, Preconditioning the Lanczos algorithm for sparse symmetric eigenvalue problems,, SIAM J. Sci. Stat. Comput., 14 (1993), 585. doi: 10.1137/0914037. Google Scholar

[16]

Y. Notay, Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem,, Numerical Linear Algebra and its Applications, 9 (2002), 21. doi: 10.1002/nla.246. Google Scholar

[17]

B. N. Parlett, The Symmetric Eigenvalue Problem,, Classics in Applied Mathematics, (1998). doi: 10.1137/1.9781611971163. Google Scholar

[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. doi: 10.1016/j.cam.2008.10.071. Google Scholar

[19]

Y. Saad, Numerical methods for large eigenvalue problems,, Revised Edition, (2011). doi: 10.1137/1.9781611970739.ch1. Google Scholar

[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. doi: 10.1137/S0895479894270427. Google Scholar

[21]

A. Stathopoulos and J. R. McCombs, PRIMME: PReconditioned Iterative MultiMethod Eigensolver: Methods and software description,, ACM Transaction on Mathematical Software, 37 (2010), 1. Google Scholar

[22]

A. Stathopoulos, Y. Saad and C. Fisher, Robust preconditioning of large sparse symmetric eigenvalue problems,, J. Comp. Appl. Math., 64 (1995), 197. doi: 10.1016/0377-0427(95)00141-7. Google Scholar

[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. Google Scholar

[24]

E. Vecharynski, C. Yang and F. Xue, Generalized preconditioned locally harmonic residual method for non-Hermitian eigenproblems,, Preprint., (). Google Scholar

[25]

J. H. Wilkinson, The Algebraic Eigenvalue Problem,, Oxford University Press, (1965). Google Scholar

[26]

C. Yang, Convergence analysis of an inexact truncated RQ iterations,, Elec. Trans. Numer. Anal., 7 (1998), 40. Google Scholar

show all references

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, (2000). doi: 10.1137/1.9780898719581. Google Scholar

[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. doi: 10.1002/(SICI)1099-1506(200004/05)7:3<99::AID-NLA188>3.3.CO;2-X. Google Scholar

[3]

J. Bramble, J. Pasciak and A. Knyazev, A subspace preconditioning algorithm for eigenvector/eigenvalue computation,, Adv. Comp. Math., 6 (1996), 150. doi: 10.1007/BF02127702. Google Scholar

[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. doi: 10.1137/S1064827596300073. Google Scholar

[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. doi: 10.1137/S1064827500382579. Google Scholar

[6]

A. V. Knyazev, Preconditioned eigensolvers-an oxymoron,, Electronic Transactions on Numerical Analysis, 7 (1998), 104. Google Scholar

[7]

A. V. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient,, SIAM Journal on Scientific Computing, 23 (2001), 517. doi: 10.1137/S1064827500366124. Google Scholar

[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. Google Scholar

[9]

R. B. Lehoucq, Analysis And Implementation of An Implicitly Restarted Arnoldi Iteration,, Ph.D Thesis, (1995). Google Scholar

[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. doi: 10.1137/S0895479895281484. Google Scholar

[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, (1998). doi: 10.1137/1.9780898719628. Google Scholar

[12]

R. Lehoucq and K. Meerbergen, The inexact rational Krylov sequence method,, SIAM J. Matrix Anal. Appl., 20 (1998), 131. doi: 10.1137/S0895479896311220. Google Scholar

[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. doi: 10.1137/S0895479894274255. Google Scholar

[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. doi: 10.1145/1067967.1067973. Google Scholar

[15]

R. Morgan and D. Scott, Preconditioning the Lanczos algorithm for sparse symmetric eigenvalue problems,, SIAM J. Sci. Stat. Comput., 14 (1993), 585. doi: 10.1137/0914037. Google Scholar

[16]

Y. Notay, Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem,, Numerical Linear Algebra and its Applications, 9 (2002), 21. doi: 10.1002/nla.246. Google Scholar

[17]

B. N. Parlett, The Symmetric Eigenvalue Problem,, Classics in Applied Mathematics, (1998). doi: 10.1137/1.9781611971163. Google Scholar

[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. doi: 10.1016/j.cam.2008.10.071. Google Scholar

[19]

Y. Saad, Numerical methods for large eigenvalue problems,, Revised Edition, (2011). doi: 10.1137/1.9781611970739.ch1. Google Scholar

[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. doi: 10.1137/S0895479894270427. Google Scholar

[21]

A. Stathopoulos and J. R. McCombs, PRIMME: PReconditioned Iterative MultiMethod Eigensolver: Methods and software description,, ACM Transaction on Mathematical Software, 37 (2010), 1. Google Scholar

[22]

A. Stathopoulos, Y. Saad and C. Fisher, Robust preconditioning of large sparse symmetric eigenvalue problems,, J. Comp. Appl. Math., 64 (1995), 197. doi: 10.1016/0377-0427(95)00141-7. Google Scholar

[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. Google Scholar

[24]

E. Vecharynski, C. Yang and F. Xue, Generalized preconditioned locally harmonic residual method for non-Hermitian eigenproblems,, Preprint., (). Google Scholar

[25]

J. H. Wilkinson, The Algebraic Eigenvalue Problem,, Oxford University Press, (1965). Google Scholar

[26]

C. Yang, Convergence analysis of an inexact truncated RQ iterations,, Elec. Trans. Numer. Anal., 7 (1998), 40. Google Scholar

[1]

Jean-Michel Rakotoson. Generalized eigenvalue problem for totally discontinuous operators. Discrete & Continuous Dynamical Systems - A, 2010, 28 (1) : 343-373. doi: 10.3934/dcds.2010.28.343
[2]

VicenŢiu D. RǍdulescu, Somayeh Saiedinezhad. A nonlinear eigenvalue problem with $ p(x) $-growth and generalized Robin boundary value condition. Communications on Pure & Applied Analysis, 2018, 17 (1) : 39-52. doi: 10.3934/cpaa.2018003
[3]

Mihai Mihăilescu. An eigenvalue problem possessing a continuous family of eigenvalues plus an isolated eigenvalue. Communications on Pure & Applied Analysis, 2011, 10 (2) : 701-708. doi: 10.3934/cpaa.2011.10.701
[4]

Yansheng Zhong, Yongqing Li. On a p-Laplacian eigenvalue problem with supercritical exponent. Communications on Pure & Applied Analysis, 2019, 18 (1) : 227-236. doi: 10.3934/cpaa.2019012
[5]

Giacomo Bocerani, Dimitri Mugnai. A fractional eigenvalue problem in $\mathbb{R}^N$. Discrete & Continuous Dynamical Systems - S, 2016, 9 (3) : 619-629. doi: 10.3934/dcdss.2016016
[6]

David Colton, Yuk-J. Leung. On a transmission eigenvalue problem for a spherically stratified coated dielectric. Inverse Problems & Imaging, 2016, 10 (2) : 369-378. doi: 10.3934/ipi.2016004
[7]

Huan Gao, Zhibao Li, Haibin Zhang. A fast continuous method for the extreme eigenvalue problem. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1587-1599. doi: 10.3934/jimo.2017008
[8]

Giuseppina Barletta, Roberto Livrea, Nikolaos S. Papageorgiou. A nonlinear eigenvalue problem for the periodic scalar $p$-Laplacian. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1075-1086. doi: 10.3934/cpaa.2014.13.1075
[9]

Isabeau Birindelli, Stefania Patrizi. A Neumann eigenvalue problem for fully nonlinear operators. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 845-863. doi: 10.3934/dcds.2010.28.845
[10]

Lei-Hong Zhang, Li-Zhi Liao. A generalized projective dynamic for solving extreme and interior eigenvalue problems. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 997-1019. doi: 10.3934/dcdsb.2008.10.997
[11]

Fioralba Cakoni, Houssem Haddar, Isaac Harris. Homogenization of the transmission eigenvalue problem for periodic media and application to the inverse problem. Inverse Problems & Imaging, 2015, 9 (4) : 1025-1049. doi: 10.3934/ipi.2015.9.1025
[12]

Xing-Bin Pan. An eigenvalue variation problem of magnetic Schrödinger operator in three dimensions. Discrete & Continuous Dynamical Systems - A, 2009, 24 (3) : 933-978. doi: 10.3934/dcds.2009.24.933
[13]

Jonathan E. Rubin. A nonlocal eigenvalue problem for the stability of a traveling wave in a neuronal medium. Discrete & Continuous Dynamical Systems - A, 2004, 10 (4) : 925-940. doi: 10.3934/dcds.2004.10.925
[14]

Chiu-Yen Kao, Yuan Lou, Eiji Yanagida. Principal eigenvalue for an elliptic problem with indefinite weight on cylindrical domains. Mathematical Biosciences & Engineering, 2008, 5 (2) : 315-335. doi: 10.3934/mbe.2008.5.315
[15]

Aixia Qian, Shujie Li. Multiple sign-changing solutions of an elliptic eigenvalue problem. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 737-746. doi: 10.3934/dcds.2005.12.737
[16]

Nikolaos S. Papageorgiou, Vicenţiu D. Rădulescu, Dušan D. Repovš. Positive solutions for perturbations of the Robin eigenvalue problem plus an indefinite potential. Discrete & Continuous Dynamical Systems - A, 2017, 37 (5) : 2589-2618. doi: 10.3934/dcds.2017111
[17]

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529
[18]

Bruce Geist and Joyce R. McLaughlin. Eigenvalue formulas for the uniform Timoshenko beam: the free-free problem. Electronic Research Announcements, 1998, 4: 12-17.

[19]

Huan Gao, Yu-Hong Dai, Xiao-Jiao Tong. Barzilai-Borwein-like methods for the extreme eigenvalue problem. Journal of Industrial & Management Optimization, 2015, 11 (3) : 999-1019. doi: 10.3934/jimo.2015.11.999
[20]

Monika Laskawy. Optimality conditions of the first eigenvalue of a fourth order Steklov problem. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1843-1859. doi: 10.3934/cpaa.2017089

 Impact Factor: 

Tools

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences