×

Optimal left and right additive Schwarz preconditioning for minimal residual methods with Euclidean and energy norms. (English) Zbl 1173.65366

Summary: For the solution of non-symmetric or indefinite linear systems arising from discretizations of elliptic problems, two-level additive Schwarz preconditioners are known to be optimal in the sense that convergence bounds for the preconditioned problem are independent of the mesh and the number of subdomains. These bounds are based on some kind of energy norm. However, in practice, iterative methods which minimize the Euclidean norm of the residual are used, despite the fact that the usual bounds are non-optimal, i.e., the quantities appearing in the bounds may depend on the mesh size [see X.-C. Cai, J. Zou, Numer. Linear Algebra Appl. 9, No. 5, 379–397 (2002; Zbl 1071.65529)]. In this paper, iterative methods are presented which minimize the same energy norm in which the optimal Schwarz bounds are derived, thus maintaining the Schwarz optimality. As a consequence, bounds for the Euclidean norm minimization are also derived, thus providing a theoretical justification for the practical use of Euclidean norm minimization methods preconditioned with additive Schwarz. Both left and right preconditioners are considered, and relations between them are derived. Numerical experiments illustrate the theoretical developments.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs

Citations:

Zbl 1071.65529

Software:

PETSc
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arioli, Mario; Loghin, Daniel; Wathen, Andrew J., Stopping criteria in finite element problems, Numer. Math., 99, 381-410 (2005) · Zbl 1069.65124
[2] Ashby, Steven F.; Manteuffel, Thomas A.; Saylor, Paul E., A taxonomy for conjugate gradient methods, SIAM J. Numer. Anal., 27, 1542-1568 (1990) · Zbl 0723.65018
[3] Axelsson, Owe, Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge and New York · Zbl 0795.65014
[4] Satish Balay, Kris Buschelman, Victor Eijkhout, William D. Gropp, Dinesh Kaushik, Matthew G. Knepley, Lois Curfman McInnes, Barry F. Smith, Hong Zhang. PETSc Users Manual, Technical Report ANL-95/11 - Revision 2.1.5, Argonne National Laboratory, 2004. Available from: <http://www.mcs.anl.gov/petsc>; Satish Balay, Kris Buschelman, Victor Eijkhout, William D. Gropp, Dinesh Kaushik, Matthew G. Knepley, Lois Curfman McInnes, Barry F. Smith, Hong Zhang. PETSc Users Manual, Technical Report ANL-95/11 - Revision 2.1.5, Argonne National Laboratory, 2004. Available from: <http://www.mcs.anl.gov/petsc>
[5] Barrett, Richard; Berry, Michael W.; Chan, Tony F.; Demmel, James; Donato, June; Dongarra, Jack; Eijkhout, Victor; Pozo, Roldán; Romine, Charles; van der Vorst, Henk, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1993), SIAM: SIAM Philadelphia · Zbl 0814.65030
[6] Benzi, Michele; Frommer, Andreas; Nabben, Reinhard; Szyld, Daniel B., Algebraic theory of multiplicative Schwarz methods, Numer. Math., 89, 605-639 (2001) · Zbl 0991.65037
[7] Braess, Dietrich, Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics (2001), Cambridge University Press: Cambridge University Press Cambridge and New York · Zbl 0976.65099
[8] Brenner, Susanne C.; Ridgway Scott, L., The mathematical theory of finite element methods, Springer Series Texts in Applied Mathematics, vol. 15 (1994), Springer: Springer New York · Zbl 0804.65101
[9] Cai, Xiao-Chuan; Dryja, Maksymilian; Sarkis, Marcus, Restricted additive Schwarz preconditioner with harmonic overlap for symmetric positive definite linear systems, SIAM J. Numer. Anal., 41, 1209-1231 (2003) · Zbl 1052.65036
[10] Cai, Xiao-Chuan; Widlund, Olof B., Domain decomposition algorithms for indefinite elliptic problems, SIAM J. Sci. Stat. Comput., 13, 243-258 (1992) · Zbl 0746.65085
[11] Cai, Xiao-Chuan; Olof, B., Widlund. Multiplicative Schwarz algorithms for some non-symmetric and indefinite problems, SIAM J. Numer. Anal., 30, 936-952 (1993) · Zbl 0787.65016
[12] Cai, X.-C.; Zou, J., Some observations on the \(l^2\) convergence of the additive Schwarz preconditioned GMRES method, Numer. Linear Algebra Appl., 9, 379-397 (2002) · Zbl 1071.65529
[13] Eiermann, Michael; Ernst, Oliver G., Geometric aspects in the theory of Krylov subspace methods, Acta Numer., 10, 251-312 (2001) · Zbl 1105.65328
[14] Eisenstat, Stanley C.; Elman, Howard C.; Schultz, Martin H., Variational iterative methods for non-symmetric systems of linear equations, SIAM J. Numer. Anal., 20, 345-357 (1983) · Zbl 0524.65019
[15] Howard C. Elman, Iterative Methods for Large, Sparse, Nonsymmetric Systems of Linear Equations, Ph.D. Thesis, Department of Computer Science, Yale Univeristy, Research Report #229, April 1982.; Howard C. Elman, Iterative Methods for Large, Sparse, Nonsymmetric Systems of Linear Equations, Ph.D. Thesis, Department of Computer Science, Yale Univeristy, Research Report #229, April 1982.
[16] Essai, Azeddine, Weighted FOM and GMRES for solving non-symmetric linear systems, Numer. Algorithms, 18, 277-292 (1998) · Zbl 0926.65036
[17] Frommer, Andreas; Szyld, Daniel B., Weighted max norms, splittings, and overlapping additive Schwarz iterations, Numer. Math., 83, 259-278 (1999) · Zbl 0934.65035
[18] Greenbaum, Anne, Iterative methods for solving linear systems, Frontiers in Applied Mathematics, vol. 17 (1997), SIAM: SIAM Philadelphia · Zbl 0883.65022
[19] Gutknecht, Martin H., Changing the norm in conjugate gradient type algorithms, SIAM J. Numer. Anal., 30, 40-56 (1993) · Zbl 0851.65017
[20] Gutknecht, Martin H.; Rozložník, Miroslav, A framework for generalized conjugate gradient methods-with special emphasis on contributions by Rüdiger Weiss, Appl. Numer. Math., 41, 7-22 (2002) · Zbl 0996.65034
[21] Hackbusch, Wolfgang, Iterative solution of large sparse systems of equations, Springer Series in Applied Mathematical Sciences, vol. 95 (1994), Springer: Springer New York, Berlin, Heidelberg · Zbl 0789.65017
[22] Quarteroni, Alfio; Valli, Alberto, Domain Decomposition Methods for Partial Differential Equations (1999), Oxford Science Publications, Clarendon Press: Oxford Science Publications, Clarendon Press Oxford · Zbl 0931.65118
[23] Saad, Yousef, Iterative methods for sparse linear systems (1996), The PWS Publishing Company: The PWS Publishing Company Boston, second ed., SIAM, Philadelphia, 2003 · Zbl 1031.65047
[24] Saad, Yousef; Schultz, Martin H., GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[25] Sarkis, Marcus, Partition of unity coarse space and Schwarz methods with harmonic overlap, (Pavarino, Luca F.; Toselli, Andrea, Recent Developments in Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering, 23 (2002), Springer: Springer Heidelberg, New York), 75-92 · Zbl 1009.65075
[26] Sarkis, Marcus, A coarse space for elasticity: partition of unity rigid body motions coarse space, (Drmač, Zlatko; Hari, Vjeran; Sopta, Luka; Tutek, Zvonimir; Veselić, Krešimir, Applied Mathematics and Scientific Computing (2003), Kluwer Academic/Plenum: Kluwer Academic/Plenum New York, Boston, Dordrecht), 253-265 · Zbl 1128.74338
[27] Marcus Sarkis, Partition of unity coarse spaces: enhanced versions, discontinuous coefficients and applications to elasticity, in: Ismael Herrera et al. (Eds.), Domain Decomposition Methods in Science and Engineering, Publised by the National Autonomous University of Mexico (UNAM), ISBN 970-32-0859-2, Proceedings of the 14th International Conference on Domain Decomposition Methods in Cocoyoc, México, 2003, pp. 149-158.; Marcus Sarkis, Partition of unity coarse spaces: enhanced versions, discontinuous coefficients and applications to elasticity, in: Ismael Herrera et al. (Eds.), Domain Decomposition Methods in Science and Engineering, Publised by the National Autonomous University of Mexico (UNAM), ISBN 970-32-0859-2, Proceedings of the 14th International Conference on Domain Decomposition Methods in Cocoyoc, México, 2003, pp. 149-158.
[28] Smith, Barry F.; Bjørstad, Peter E.; Gropp, William. D., Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations (1996), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0857.65126
[29] Starke, Gerhard, Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems, Numer. Math., 78, 103-117 (1997) · Zbl 0888.65037
[30] Toselli, Andrea; Widlund, Olof B., Domain decomposition: Algorithms and theory, Springer Series in Computational Mathematics, 34 (2005), Springer: Springer Berlin, Heidelberg, New York · Zbl 1069.65138
[31] Weiss, Rüdiger, Error-minimizing Krylov subspace methods, SIAM J. Sci. Comput., 15, 511-527 (1994) · Zbl 0798.65048
[32] Weiss, Rüdiger, Minimization properties and short recurrences for Krylov subspace method, Electron. Trans. Numer. Anal., 4, 57-75 (1994) · Zbl 0809.65027
[33] Weiss, Rüdiger, Parameter-free iterative linear solvers, Mathematical Research Series, vol. 97 (1996), Akademie: Akademie Berlin · Zbl 0858.65031
[34] Xu, Jinchao; Cai, Xiao-Chuan, A preconditioned GMRES method for non-symmetric or indefinite problems, Math. Comput., 59, 311-319 (1992) · Zbl 0766.65034
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.