Portal de Periódicos da CAPES

Flexible and multi-shift induced dimension reduction algorithms for solving large sparse linear systems

2014; Wiley; Volume: 22; Issue: 1 Linguagem: Inglês

10.1002/nla.1935

1099-1506

Martin B. van Gijzen, Gérard L. G. Sleijpen, Jens‐Peter M. Zemke,

Advanced Numerical Methods in Computational Mathematics

Numerical Linear Algebra with ApplicationsVolume 22, Issue 1 p. 1-25 Research Article Flexible and multi-shift induced dimension reduction algorithms for solving large sparse linear systems Martin B. van Gijzen, Martin B. van Gijzen Delft Institute of Applied Mathematics, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The NetherlandsSearch for more papers by this authorGerard L. G. Sleijpen, Gerard L. G. Sleijpen Mathematical Institute, Utrecht University, P.O. Box 80010, 3508 TA Utrecht, The NetherlandsSearch for more papers by this authorJens-Peter M. Zemke, Corresponding Author Jens-Peter M. Zemke orcid.org/0000-0002-5748-8727 Institut für Mathematik, Technische Universität Hamburg-Harburg, Schwarzenbergstr. 95, D-21073 Hamburg, Germany Correspondence to: Jens-Peter M. Zemke, Institut für Mathematik, Technische Universität Hamburg-Harburg, Schwarzenbergstr. 95, D-21073 Hamburg, Germany. E-mail: [email protected]Search for more papers by this author Martin B. van Gijzen, Martin B. van Gijzen Delft Institute of Applied Mathematics, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The NetherlandsSearch for more papers by this authorGerard L. G. Sleijpen, Gerard L. G. Sleijpen Mathematical Institute, Utrecht University, P.O. Box 80010, 3508 TA Utrecht, The NetherlandsSearch for more papers by this authorJens-Peter M. Zemke, Corresponding Author Jens-Peter M. Zemke orcid.org/0000-0002-5748-8727 Institut für Mathematik, Technische Universität Hamburg-Harburg, Schwarzenbergstr. 95, D-21073 Hamburg, Germany Correspondence to: Jens-Peter M. Zemke, Institut für Mathematik, Technische Universität Hamburg-Harburg, Schwarzenbergstr. 95, D-21073 Hamburg, Germany. E-mail: [email protected]Search for more papers by this author First published: 01 May 2014 https://doi.org/10.1002/nla.1935Citations: 13Read the full textAboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat SUMMARY We give two generalizations of the induced dimension reduction (IDR) approach for the solution of linear systems. We derive a flexible and a multi-shift quasi-minimal residual IDR variant. These variants are based on a generalized Hessenberg decomposition. We present a new, more stable way to compute basis vectors in IDR. Numerical examples are presented to show the effectiveness of these new IDR variants and the new basis compared with existing ones and to other Krylov subspace methods. Copyright © 2014 John Wiley & Sons, Ltd. REFERENCES 1 Sonneveld P, van Gijzen MB. IDR (s): a family of simple and fast algorithms for solving large nonsymmetric systems of linear equations. SIAM Journal on Scientific Computing 2008/09; 31(2): 1035–1062. 2 Van Gijzen MB, Sonneveld P. Algorithm 913: an elegant IDR(s) variant that efficiently exploits biorthogonality properties. ACM Transactions on Mathematical Software December 2011; 38(1): 5:1–5:19. 3 Gutknecht MH. IDR explained. Electronic Transactions on Numerical Analysis 2009/10; 36: 126–148. 4 Onoue Y, Nakashima N, Fujino S. A difference between easy and profound preconditionings of IDR (s) method. Transactions of the Japan Society for Computational Engineering and Science 2008; 20080023. (in Japanese). 5 Onoue Y, Nakashima N, Fujino S. An overview of a family of new iterative methods based on IDR theorem and its estimation. Proceedings of the international multi-conference of engineers and computer scientists 2009, 2009 March 18; 129–2134. 6 Gutknecht MH, Zemke JPM. Eigenvalue computations based on IDR. SIAM Journal on Matrix Analysis and Applications 2013; 34(2): 283–311. 7 Sleijpen GL, Sonneveld P, van Gijzen MB. Bi-CGSTAB as an induced dimension reduction method. Applied Numerical Mathematics 2010; 60(11): 1100–1114. 8 Simoncini V, Szyld DB. Interpreting IDR as a Petrov-Galerkin method. SIAM Journal on Scientific Computing 2010; 32(4): 1898–1912. 9 Sleijpen GL, van Gijzen MB. Exploiting BiCGstab (ℓ) strategies to induce dimension reduction. SIAM Journal on Scientific Computing 2010; 32(5): 2687–2709. 10 Sonneveld P. On the convergence behavior of IDR (s) and related methods. SIAM Journal on Scientific Computing 2012; 34(5): A2576–A2598. 11 Simoncini V, Szyld DB. Recent computational developments in Krylov subspace methods for linear systems. Numerical Linear Algebra with Applications 2007; 14(1): 1–59. 12 Paige CC, Saunders MA. Solutions of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis 1975; 12(4): 617–629. 13 Saad Y, Schultz MH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing 1986; 7(3): 856–869. 14 Freund RW, Nachtigal NM. QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numerische Mathematik 1991; 60(3): 315–339. 15 Hestenes MR, Stiefel E. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards 1952; 49: 409–436 (1953). 16 Saad Y. Krylov subspace methods for solving large unsymmetric linear systems. Mathematics of Computation 1981; 37(155): 105–126. 17 van der Vorst HA, Sonneveld P. CGSTAB, a more smoothly converging variant of CG-S. Technical Report Report 90-50, Department of Mathematics and Informatics, Delft University of Technology, 1990. 18 van der Vorst HA. Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM Journal of Scientific and Statistical Computing 1992; 13(2): 631–644. 19 Chan TF, Gallopoulos E, Simoncini V, Szeto T, Tong CH. A quasi-minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems. SIAM Journal on Scientific Computing 1994; 15(2): 338–347. Iterative methods in numerical linear algebra (Copper Mountain Resort, CO, 1992). 20 Du L, Sogabe T, Zhang SL. Quasi-minimal residual smoothing technique for the IDR (s) method. JSIAM Letters 2011; 3: 13–16. 21 Du L, Sogabe T, Zhang SL. A variant of the IDR (s) method with the quasi-minimal residual strategy. Journal of Computational and Applied Mathematics 2011; 236: 621–630. 22 Kirchner S. IDR-Verfahren zur Lösung von Familien geshifteter linearer Gleichungssysteme. Diplomarbeit, Bergische Universität Wuppertal, Fachbereich Mathematik, Mai, 2011. 23 Saad Y. Iterative Methods for Sparse Linear Systems ( Second edition). Society for Industrial and Applied Mathematics: Philadelphia, PA, 2003. 24 Rendel O, Rizvanolli A, Zemke JPM. IDR: A new generation of Krylov subspace methods? Linear Algebra and its Applications 2013; 439(4): 1040–1061. 25 Sleijpen GL, van der Vorst HA. Maintaining convergence properties of BiCGstab methods in finite precision arithmetic. Numerical Algorithms 1995; 10(3-4): 203–223. 26 Saad Y. A flexible inner-outer preconditioned GMRES algorithm. SIAM Journal on Scientific Computing 1993; 14(2): 461–469. 27 van der Vorst HA, Vuik C. GMRESR: a family of nested GMRES methods. Numerical Linear Algebra with Applications 1994; 1(4): 369–386. 28 Notay Y. Flexible conjugate gradients. SIAM Journal on Scientific Computing 2000; 22(4): 1444–1460 (electronic). 29 Szyld DB, Vogel JA. FQMR: a flexible quasi-minimal residual method with inexact preconditioning. SIAM Journal on Scientific Computing 2001; 23(2): 363–380. Copper Mountain Conference (2000). 30 Vogel JA. Flexible BiCG and flexible Bi-CGSTAB for nonsymmetric linear systems. Applied Mathematics and Computation 2007; 188(1): 226–233. 31 Datta BN, Saad Y. Arnoldi methods for large Sylvester-like observer matrix equations, and an associated algorithm for partial spectrum assignment. Linear Algebra and its Applications 1991; 154/156: 225–244. 32 Gear CW, Saad Y. Iterative solution of linear equations in ODE codes. SIAM Journal on Scientific and Statistical Computing 1983; 4(4): 583–601. 33 Freund RW. Solution of shifted linear systems by quasi-minimal residual iterations. In Numerical Linear Algebra (Kent, OH, 1992). de Gruyter, Berlin, 1993; 101–121. 34 Jegerlehner B. Krylov space solvers for shifted linear systems. Technical Report IUHET-353, Indiana University, Department of Physics, 1996. (Available from: arXiv.org: http://arXiv.org/abs/hep-lat/9612014, see also http://cdsweb.cern.ch/record/316892/files/9612014.pdf). 35 Frommer A, Glässner U. Restarted GMRES for shifted linear systems. SIAM Journal on Scientific Computing 1998; 19(1): 15–26 (electronic). Special issue on iterative methods (Copper Mountain, CO, 1996). 36 Simoncini V. Restarted full orthogonalization method for shifted linear systems. BIT 2003; 43(2): 459–466. 37 Frommer A. BiCGStab (ℓ) for families of shifted linear systems. Computing 2003; 70(2): 87–109. 38 van den Eshof J, Sleijpen GL. Accurate conjugate gradient methods for families of shifted systems. Applied Numerical Mathematics 2004; 49(1): 17–37. 39 Cullum J, Greenbaum A. Relations between Galerkin and norm-minimizing iterative methods for solving linear systems. SIAM Journal on Matrix Analysis and Applications 1996; 17(2): 223–247. 40 Boisvert RF, Pozo R, Remington K, Barrett RF, Dongarra JJ. Matrix market: a Web resource for test matrix collections. In Quality of Numerical Software: Assessment and Enhancement, RF Boisvert (ed.)., IFIP Advances in Information and Communication Technology. Chapman and Hall: London, 1997; 125–137. 41 Schönauer W. Scientific Computing on Vector Computers. Elsevier: Amsterdam, 1987. 42 Weiß R. Convergence behavior of generalized conjugate gradient methods. Dissertation, Universität Karlsruhe, 1990. 43 Erlangga YA, Oosterlee CW, Vuik C. A novel multigrid based preconditioner for heterogeneous Helmholtz problems. SIAM Journal on Scientific Computing 2006; 27(4): 1471–1492 (electronic). 44 van Gijzen MB, Erlangga YA, Vuik C. Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian. SIAM Journal on Scientific Computing 2007; 29(5): 1942–1958 (electronic). 45 Notay Y. An aggregation-based algebraic multigrid method. Electronic Transactions on Numerical Analysis 2010; 37: 123–146. 46 Yeung MC, Chan TF. ML (k)BiCGSTAB: a BiCGSTAB variant based on multiple Lanczos starting vectors. SIAM Journal on Scientific Computing 1999/00; 21(4): 1263–1290 (electronic). Citing Literature Volume22, Issue1January 2015Pages 1-25 ReferencesRelatedInformation