Krylov subspace recycling for sequences of shifted linear systems. (English) Zbl 1291.65108
Summary: We study the use of Krylov subspace recycling for the solution of a sequence of slowly-changing families of linear systems, where each family consists of shifted linear systems that differ in the coefficient matrix only by multiples of the identity. Our aim is to explore the simultaneous solution of each family of shifted systems within the framework of subspace recycling, using one augmented subspace to extract candidate solutions for all the shifted systems. The ideal method would use the same augmented subspace for all systems and have fixed storage requirements, independent of the number of shifted systems per family. We show that a method satisfying both requirements cannot exist in this framework.
As an alternative, we introduce two schemes. One constructs a separate deflation space for each shifted system but solves each family of shifted systems simultaneously. The other builds only one recycled subspace and constructs approximate corrections to the solutions of the shifted systems at each cycle of the iterative linear solver while only minimizing the base system residual. At convergence of the base system solution, we apply the method recursively to the remaining unconverged systems. We present numerical examples involving systems arising in lattice quantum chromodynamics.
As an alternative, we introduce two schemes. One constructs a separate deflation space for each shifted system but solves each family of shifted systems simultaneously. The other builds only one recycled subspace and constructs approximate corrections to the solutions of the shifted systems at each cycle of the iterative linear solver while only minimizing the base system residual. At convergence of the base system solution, we apply the method recursively to the remaining unconverged systems. We present numerical examples involving systems arising in lattice quantum chromodynamics.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 81V05 | Strong interaction, including quantum chromodynamics |
Keywords:
Krylov subspace methods; subspace recycling; shifted linear systems; convergence; numerical examples; lattice quantum chromodynamicsSoftware:
SparseMatrixReferences:
| [1] | Adbel-Rehim, A.; Morgan, R. B.; Wilcox, W., Seed methods for linear equations in lattice QCD problems with multiple right-hand sides, (Proceedings of Science, Lattice 2008 (2008)), paper 038 |
| [2] | Ahmad, M. I.; Szyld, D. B.; van Gijzen, M. B., Preconditioned multishift BiCG for \(H_2\)-optimal model reduction (Jun. 2012), Department of Mathematics, Temple University, Research Report 12-06-15 |
| [3] | Baker, A. H.; Jessup, E. R.; Manteuffel, T., A technique for accelerating the convergence of restarted GMRES, SIAM J. Matrix Anal. Appl., 26, 962-984 (2005) · Zbl 1086.65025 |
| [4] | Campbell, S. L.; Ipsen, I. C.F.; Kelley, C. T.; Meyer, C. D., GMRES and the minimal polynomial, BIT Numer. Math., 36, 664-675 (1996) · Zbl 0865.65017 |
| [5] | Celis, M. R.; Dennis, J. E.; Tapia, R. A., A trust region strategy for nonlinear equality constrained optimization, (Boggs, P. T.; Byrd, R. H.; Schnabel, R. B., Numerical Optimization. Numerical Optimization, Boulder, Colo., 1984 (1985), SIAM: SIAM Philadelphia), 71-82 · Zbl 0566.65048 |
| [6] | Chan, T. F.; Wan, W. L., Analysis of projection methods for solving linear systems with multiple right-hand sides, SIAM J. Sci. Comput., 18, 1698-1721 (1997) · Zbl 0888.65033 |
| [7] | Darnell, D.; Morgan, R. B.; Wilcox, W., Deflated GMRES for systems with multiple shifts and multiple right-hand sides, Linear Algebra Appl., 429, 2415-2434 (2008) · Zbl 1153.65032 |
| [8] | Davis, T. A.; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1:1-1:25 (2011) · Zbl 1365.65123 |
| [9] | Eiermann, M.; Ernst, O. G.; Schneider, O., Analysis of acceleration strategies for restarted minimal residual methods, J. Comput. Appl. Math., 123, 261-292 (2000) · Zbl 0968.65016 |
| [10] | Frommer, A., \(BiCGStab(l)\) for families of shifted linear systems, Computing, 70, 87-109 (2003) · Zbl 1239.65022 |
| [11] | Frommer, A.; Glässner, U., Restarted GMRES for shifted linear systems, SIAM J. Sci. Comput., 19, 15-26 (1998) · Zbl 0912.65023 |
| [12] | Frommer, A.; Maass, P., Fast CG-based methods for Tikhonov-Phillips regularization, SIAM J. Sci. Comput., 20, 1831-1850 (1999) · Zbl 0943.65068 |
| [13] | Frommer, A.; Güsken, S.; Lippert, T.; Nöckel, B.; Schilling, K., Many masses on one stroke: economic computation of quark propagators, Int. J. Mod. Phys. C, 6, 627-638 (1995) |
| [14] | Hansen, P. C., Discrete Inverse Problems: Insight and Algorithms (2010), SIAM: SIAM Philadelphia · Zbl 1197.65054 |
| [15] | Jegerlehner, B., Krylov space solvers for sparse linear systems (1996), Indiana University, Tech. Rep. IUHET-353 |
| [16] | Kilmer, M. E.; de Sturler, E., Recycling subspace information for diffuse optical tomography, SIAM J. Sci. Comput., 27, 2140-2166 (2006) · Zbl 1103.65036 |
| [17] | Kirchner, S., IDR-Verfahren zur Lösung von Familien geshifteter linearer Gleichungssysteme (2011), Bergische Universität Wuppertal, Department of Mathematics: Bergische Universität Wuppertal, Department of Mathematics Wuppertal, Germany, Master’s thesis |
| [19] | Lehoucq, R. B.; Sorensen, D. C., Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM J. Matrix Anal. Appl., 17, 789-821 (1996) · Zbl 0863.65016 |
| [20] | Meerbergen, K., The solution of parametrized symmetric linear systems, SIAM J. Matrix Anal. Appl., 24, 1038-1059 (2003) · Zbl 1044.65029 |
| [21] | Morgan, R. B., Implicitly restarted GMRES and Arnoldi methods for nonsymmetric systems of equations, SIAM J. Matrix Anal. Appl., 21, 1112-1135 (2000) · Zbl 0963.65038 |
| [22] | Morgan, R. B., GMRES with deflated restarting, SIAM J. Sci. Comput., 24, 20-37 (2002) · Zbl 1018.65042 |
| [23] | Parks, M. L.; de Sturler, E.; Mackey, G.; Johnson, D. D.; Maiti, S., Recycling Krylov subspaces for sequences of linear systems, SIAM J. Sci. Comput., 28, 1651-1674 (2006) · Zbl 1123.65022 |
| [24] | Saad, Y., Analysis of augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 18, 435-449 (1997) · Zbl 0871.65026 |
| [25] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042 |
| [26] | Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [27] | Simoncini, V., Restarted full orthogonalization method for shifted linear systems, BIT Numer. Math., 43, 459-466 (2003) · Zbl 1033.65015 |
| [28] | Simoncini, V.; Szyld, D. B., On the occurrence of superlinear convergence of exact and inexact Krylov subspace methods, SIAM Rev., 47, 247-272 (2005) · Zbl 1079.65034 |
| [29] | Simoncini, V.; Szyld, D. B., Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14, 1-59 (2007) · Zbl 1199.65112 |
| [30] | Simoncini, V.; Szyld, D. B., Interpreting IDR as a Petrov-Galerkin method, SIAM J. Sci. Comput., 32, 1898-1912 (2010) · Zbl 1219.65039 |
| [31] | Smith, C. F.; Peterson, A. F.; Mittra, R., A conjugate gradient algorithm for treatment of multiple incident electromagnetic fields, IEEE Trans. Antennas Propag., 37, 1490-1493 (1989) |
| [32] | Sonneveld, P.; van Gijzen, M. B., \(IDR(s)\): a family of simple and fast algorithms for solving large nonsymmetric systems of linear equations, SIAM J. Sci. Comput., 31, 1035-1062 (2008) · Zbl 1190.65053 |
| [33] | Soodhalter, K. M.; Szyld, D. B.; Xue, F., Krylov subspace recycling for sequences of shifted linear systems (2013), Arxiv Preprint |
| [34] | Stathopoulos, A.; Orginos, K., Computing and deflating eigenvalues while solving multiple right-hand side linear systems with an application to quantum chromodynamics, SIAM J. Sci. Comput., 32, 439-462 (2010) · Zbl 1209.65046 |
| [35] | de Sturler, E., Nested Krylov methods based on GCR, J. Comput. Appl. Math., 67, 15-41 (1996) · Zbl 0854.65026 |
| [36] | de Sturler, E., Truncation strategies for optimal Krylov subspace methods, SIAM J. Numer. Anal., 36, 864-889 (1999) · Zbl 0960.65031 |
| [37] | de Sturler, E., Convergence bounds for approximate invariant subspace recycling for sequences of linear systems, (Program of the Householder Symposium XVIII on Numerical Linear Algebra (2011)), 51-52 |
| [38] | van der Vorst, H. A.; Vuik, K., The superlinear convergence behaviour of GMRES, J. Comput. Appl. Math., 48, 327-341 (1993) · Zbl 0797.65026 |
| [39] | Wu, G.; Wang, Y.-C.; Jin, X.-Q., A preconditioned and shifted GMRES algorithm for the PageRank problem with multiple damping factors, SIAM J. Sci. Comput., 34, A2558-A2575 (2012) · Zbl 1263.65037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
