×

GMRES with multiple preconditioners. (English) Zbl 1383.65026

Summary: We propose a variant of the generalized minimal residual (GMRES) method, where multiple (two or more) preconditioners are applied simultaneously, while maintaining minimal residual optimality properties. To accomplish this, a block version of Flexible GMRES is used, but instead of considering blocks associated with multiple right hand sides, we consider a single right-hand side and grow the space by applying each of the preconditioners to all current search directions, minimizing the residual norm over the resulting larger subspace. To alleviate the difficulty of rapidly increasing storage requirements, we present a heuristic limited-memory selective algorithm, and demonstrate the effectiveness of this approach.

MSC:

65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods

Software:

HSL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ayuso de Dios, B., Barker, A.T., Vassilevski, P.S.: A combined preconditioning strategy for nonsymmetric systems. SIAM J. Sci. Comput. 36, A2533G-A2556 (2014) · Zbl 1308.65043 · doi:10.1137/120888946
[2] Bakhos, T., Ladenheim, S., Kitanidis, P.K., Saibaba, A.K., Szyld D.B.: Multipreconditioned GMRES for shifted systems. In: Research Report (2016), Department of Mathematics, Temple University (2016). Accessed 31 Mar 2016 · Zbl 1392.65043
[3] Bai, Z.-Z.: Block preconditioners for elliptic PDE-constrained optimization problems. Computing 91, 379-395 (2011) · Zbl 1242.65121 · doi:10.1007/s00607-010-0125-9
[4] Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418-477 (2002) · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176
[5] Birkhof, G., Varga, R.S., Young Jr., D.M.: Alternating direction implicit methods. Adv. Comput. 3, 189-273 (1962) · Zbl 0111.31402 · doi:10.1016/S0065-2458(08)60620-8
[6] Bridson, R., Greif, C.: A multipreconditioned conjugate gradient algorithm. SIAM J. Matrix Anal. Appl. 27, 1056-1068 (2006) · Zbl 1104.65027 · doi:10.1137/040620047
[7] Calandra, H., Gratton, S., Langou, J., Pinel, X., Vasseur, X.: Flexible variants of block restarted GMRES methods with application to geophysics. SIAM J. Sci. Comput. 34, A714-A736 (2012) · Zbl 1248.65036 · doi:10.1137/10082364X
[8] de Sturler, E.: Nested Krylov methods based on GCR. J. Comput. Appl. Math. 67, 15-41 (1996) · Zbl 0854.65026 · doi:10.1016/0377-0427(94)00123-5
[9] Elbouyahyaoui, L., Messaoudi, A., Sadok, H.: Algebraic properties of the block GMRES and block Arnoldi methods. Electr. Trans. Num. Anal. 33, 207-220 (2008-2009) · Zbl 1188.65031
[10] Elman, H., Howle, V.E., Shadid, J., Shuttleworth, R., Tuminaro, R.: Block preconditioners based on approximate commutators. SIAM J. Sci. Comput. 27, 1651-1668 (2006) · Zbl 1100.65042 · doi:10.1137/040608817
[11] Elman, H., Silvester, D., Wathen, A.: Finite elements and fast iterative solvers, Second Edition, Oxford University Press, Oxford (2014) · Zbl 1304.76002
[12] Freund, R.W.: Model reduction methods based on Krylov subspaces. Acta Num. 12, 267-319 (2003) · Zbl 1046.65021 · doi:10.1017/S0962492902000120
[13] Gaul, A., Gutknecht, M.H., Liesen, J., Nabben, R.: A framework for deflated and augmented Krylov subspace methods. SIAM J. Matrix Anal. Appl. 34, 495-518 · Zbl 1273.65049
[14] Greenbaum, A., Pták, V., Strakoš, Z.: Any nonincreasing convergence curve is possible for GMRES. SIAM J. Matrix Anal. Appl. 17, 465-469 (1996) · Zbl 0857.65029 · doi:10.1137/S0895479894275030
[15] Greif, C.; Rees, T.; Szyld, DB; Erhel, J. (ed.); Gander, M. (ed.); Halpern, L. (ed.); Pichot, G. (ed.); Sassi, T. (ed.); Widlund, O. (ed.), Additive Schwarz with variable weights, domain decomposition methods in science and engineering XXI, No. 98, 655-662 (2014), Berlin
[16] Gutknecht, M.H.: Block Krylov space methods for linear systems with multiple right-hand sides: an introduction. In: Siddiqi, A.H., Duff, I.S., Christensen, O. (eds.) Modern mathematical models, methods and algorithms for real world systems, pp. 420-447. Anamaya, New Delhi (2007) · Zbl 0426.65011
[17] Hinze, M., Pinnau, R., Ulbrich, M., Ulbrich, S.: Optimization with PDE constraints. Mathematical modelling: theory and applications. Springer, New York (2008) · Zbl 1167.49001
[18] HSL (2013). A collection of Fortran codes for large scale scientific computation. http://www.hsl.rl.ac.uk · Zbl 1167.65358
[19] Johnsson, S.L., Saad, Y., Schultz, M.H.: Alternating direction methods on multiprocessors. SIAM J. Stat. Sci. Comput. 8, 686-700 (1987) · Zbl 0625.65105 · doi:10.1137/0908060
[20] Kay, D., Loghin, D., Wathen, A.J.: A preconditioner for the steady-state Navier-Stokes equations. SIAM J. Sci. Comput. 24, 237-256 (2002) · Zbl 1013.65039 · doi:10.1137/S106482759935808X
[21] Keller, C., Gould, N.I.M., Wathen, A.J.: Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21, 1300-1317 (2000) · Zbl 0960.65052 · doi:10.1137/S0895479899351805
[22] Langou, J.: Iterative methods for solving linear systems with multiple right hand sides. Ph.D. thesis, INSA, Toulouse, June 2003. CERFACS Report TH/PA/03/24 (2003) · Zbl 1112.65028
[23] Lukšan, L., Vlček, J.: Indefinitely preconditioned inexact Newton method for large sparse equality constrained nonlinear programming problems. Num. Linear Algebra Appl. 5, 219-247 (1998) · Zbl 0937.65066 · doi:10.1002/(SICI)1099-1506(199805/06)5:3<219::AID-NLA134>3.0.CO;2-7
[24] O’Leary, D.P.: The block conjugate gradient algorithm and related methods. Linear Algebra Appl. 29, 293-322 (1980) · Zbl 0426.65011 · doi:10.1016/0024-3795(80)90247-5
[25] O’Leary, D.P., White, R.E.: Multi-splittings of matrices and parallel solution of linear systems. SIAM J. Algebraic Discret. Methods 6, 630-640 (1985) · Zbl 0582.65018 · doi:10.1137/0606062
[26] Pearson, J.W., Wathen, A.J.: A new approximation of the Schur complement in preconditioners for PDE-constrained optimization. Linear Algebra Appl. 19, 816-829 (2012) · Zbl 1274.65187 · doi:10.1002/nla.814
[27] Pestana, J.: Nonstandard inner products and preconditioned iterative methods. D.Phil. thesis, University of Oxford (2011) · Zbl 0111.31402
[28] Pestana, J., Wathen, A.J.: Combination preconditioning of saddle point systems for positive definiteness. Num. Linear Algebra Appl. 20, 785-808 (2013) · Zbl 1313.65052 · doi:10.1002/nla.1843
[29] Rees, T., Dollar, H.S., Wathen, A.J.: Optimal solvers for PDE-constrained optimization. SIAM J. Sci. Comput. 32, 271-298 (2010) · Zbl 1208.49035 · doi:10.1137/080727154
[30] Robbé, M., Sadkane, M.: Exact and inexact breakdowns in the block GMRES method. Linear Algebra Appl. 419, 265-285 (2006) · Zbl 1112.65028 · doi:10.1016/j.laa.2006.04.018
[31] Ruhe, A.: Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices. Math. Comput. 33, 680-687 (1979) · Zbl 0443.65022 · doi:10.1090/S0025-5718-1979-0521282-9
[32] Rui, P.-L., Yong, H., Chen, R.-S.: Multipreconditioned GMRES method for electromagnetic wave scattering problems. Microw. Opt. Technol. Lett. 50, 150-152 (2008) · doi:10.1002/mop.23004
[33] Saad, Y.: A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput. 14, 461-469 (1993) · Zbl 0780.65022 · doi:10.1137/0914028
[34] Saad, Y.: Iterative methods for sparse linear systems, 2nd edn. SIAM, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[35] 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 · doi:10.1137/0907058
[36] Sadkane, M.: A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices. Num. Math. 23, 181-193 (2009) · Zbl 0791.65020
[37] Sadkane, M.: Block Arnoldi and Davidson methods for unsymmetric large eigenvalue problems. Num. Math. 64, 687-706 (1993) · Zbl 0791.65021
[38] Sarkis, M., Szyld, D.B.: Optimal left and right additive Schwarz preconditioning for minimal residual methods with Euclidean and energy norms. Comput. Methods Appl. Mech. Eng. 196, 1612-1621 (2007) · Zbl 1173.65366 · doi:10.1016/j.cma.2006.03.027
[39] Schöberl, J., Zulehner, W.: Symmetric indefinite preconditioners for saddle point problems with applications to PDE-constrained optimization problems. SIAM J. Matrix Anal. Appl. 29, 752-773 (2007) · Zbl 1154.65029 · doi:10.1137/060660977
[40] Silvester, D., Elman, H., Kay, D., Wathen, A.: Efficient preconditioning of the linearized Navier-Stokes equations for incompressible flow. J. Comput. Appl. Math. 128, 261-279 (2001) · Zbl 0983.76051 · doi:10.1016/S0377-0427(00)00515-X
[41] Simoncini, V., Gallopouolos, E.: Convergence properties of block GMRES and matrix polynomials. Linear Algebra Appl. 47, 97-119 (1996) · Zbl 0861.65023 · doi:10.1016/0024-3795(95)00093-3
[42] 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 · doi:10.1137/S0036144503424439
[43] Simoncini, V., Szyld, D.B.: Recent computational developments in Krylov subspace methods for linear systems. Num. Linear Algebra Appl. 14, 1-59 (2007) · Zbl 1199.65112 · doi:10.1002/nla.499
[44] Sleijpen, G.L., van der Vorst, H.A., Modersitzki, J.: Differences in the effects of rounding errors in Krylov solvers for symmetric indefinite linear systems. SIAM J. Matrix Anal. Appl. 22, 726-751 (2000) · Zbl 0983.65046 · doi:10.1137/S0895479897323087
[45] Stoll, M., Wathen, A.J.: Combination preconditioning and the Bramble-Pasciak \[^+\]+ preconditioner. SIAM J. Matrix Anal. Appl. 30, 582-608 (2008) · Zbl 1167.65358 · doi:10.1137/070688961
[46] Tröltzsch, F.: Optimal control of partial differential equations: Theory, methods and applications. American Mathematical Society, Providence (2010) · Zbl 1195.49001 · doi:10.1090/gsm/112
[47] Vital, B.: Etude de quelques méthodes de résolution de problèmes linéaires de grande taille sur multiprocessor. Ph. D. thesis, Université de Rennes (1990) · Zbl 0983.65046
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.