Parameter modified versions of preconditioning and iterative inner product free refinement methods for two-by-two block matrices. (English) Zbl 1425.65047
Summary: A special two-by-two block matrix form arises in many important applications. Extending earlier results it is shown that parameter modified versions of a very efficient preconditioner does not improve its rate of convergence. This holds also for iterative refinement methods corresponding to a few fixed steps of the Chebyshev accelerated method. The parameter version can improve the defect-correction method but the convergence of this method is slower than an iterative refinement method with an optimal parameter. The paper includes also a discussion of how one can save computer elapsed times by avoiding use of global inner products such as by use of a Chebyshev accelerated method instead of a Krylov subspace method. Since accurate and even sharp eigenvalue bounds are available, the Chebyshev iteration method converges as fast as the Krylov subspace method.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
References:
| [1] | Amestoy, P. R.; Davis, T. A.; Duff, I. S., An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl., 17, 4, 886-905 (1996) · Zbl 0861.65021 |
| [2] | Amestoy, P. R.; Davis, T. A.; Duff, I. S., Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Trans. Math. Software, 30, 3, 381-388 (2004) · Zbl 1070.65534 |
| [3] | Arioli, M.; Duff, I. S., Using FGMRES to obtain backward stability in mixed precision, Electron. Trans. Numer. Anal., 33, 31-44 (2009) · Zbl 1171.65018 |
| [4] | Arioli, M.; Duff, I. S.; Gratton, S.; Pralet, S., A note on GMRES preconditioned by a perturbed ldl̂t decomposition with static pivoting, SIAM J. Sci. Comput., 29, 5, 2024-2044 (2007) · Zbl 1161.65023 |
| [5] | Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press · Zbl 0795.65014 |
| [6] | Axelsson, O., Preconditioning of two-by-two block matrix systems with square matrix blocks, with applications, Appl. Math., 62, 537-559 (2017) · Zbl 1458.65025 |
| [7] | Axelsson, O.; Blaheta, R., Preconditioning of matrices partitioned in 2 × 2 block form: eigenvalue estimates and Schwarz DD for mixed FEM, Numer. Linear Algebra Appl., 17, 5, 787-810 (2010) · Zbl 1240.65090 |
| [8] | Axelsson, O.; Farouq, S.; Neytcheva, M., Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems. Stokes control, Numer. Algorithms, 74, 19-37 (2017) · Zbl 1365.65167 |
| [9] | Axelsson, O.; Kucherov, A., Real valued iterative methods for solving complex symmetric linear systems, Numer. Linear Algebra Appl., 7, 197-218 (2000) · Zbl 1051.65025 |
| [10] | Axelsson, O.; Lukáš, D., Preconditioning methods for eddy current optimally controlled time-harmonic electromagnetic problems, J. Numer. Math., 27, 1-21 (2019) · Zbl 1428.65040 |
| [11] | Axelsson, O.; Neytcheva, M.; Ahmad, B., A comparison of iterative methods to solve complex valued linear algebraic systems, Numer. Algorithms, 66, 811-841 (2014) · Zbl 1307.65034 |
| [12] | Bai, Z.-Z.; Benzi, M.; Chen, F., Modified HSS iteration methods for a class of complex symmetric linear systems, Computing, 87, 93-111 (2010) · Zbl 1210.65074 |
| [13] | Bai, Z.-Z.; Benzi, M.; Chen, F., On preconditioned MHSS iteration methods for complex symmetric linear systems, Numer. Algorithms, 56, 297-317 (2011) · Zbl 1209.65037 |
| [14] | Bai, Z.-Z.; Benzi, M.; Chen, F.; Wang, Z.-Q., Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems, IMA J. Numer. Anal., 33, 343-369 (2013) · Zbl 1271.65100 |
| [15] | Brooks, A. N.; Hughes, T. J., Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations, Comput. Methods Appl. Mech. Engrg., 32, 199-259 (1982) · Zbl 0497.76041 |
| [16] | P. Concus, G. Golub, A generalized conjugate gradient method for nonsymmetric systems of linear equations, Stanford University, 1976, Tech. Rep, STAN-CS-76-535.; P. Concus, G. Golub, A generalized conjugate gradient method for nonsymmetric systems of linear equations, Stanford University, 1976, Tech. Rep, STAN-CS-76-535. · Zbl 0344.65020 |
| [17] | Craig, E. J., The N-step iteration procedures, J. Math. Phys., 34, 1-4, 64-73 (1955) · Zbl 0065.10901 |
| [18] | Orban, D.; Arioli, M., Iterative Solution of Symmetric Quasi-Definite Linear Systems (2017), SIAM: SIAM Philadelphia, PA · Zbl 1409.65004 |
| [19] | Elman, H. C.; Silverster, D. J.; Wathen, A. J., Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics (2005), Oxford University Press: Oxford University Press New York · Zbl 1083.76001 |
| [20] | Elman, H. C.; Ramage, A.; Silvester, D. J., Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow, ACM Trans. Math. Software, 33, 2, 14 (2007) · Zbl 1365.65326 |
| [21] | Elman, H. C.; Ramage, A.; Silvester, D. J., IFISS: a computational laboratory for investigating incompressible flow problems, SIAM Rev., 56, 2, 261-273 (2014) · Zbl 1426.76645 |
| [22] | Fischer, B., Polynomial Based Iteration Methods for Symmetric Linear Systems (2011), SIAM: SIAM Philadephia, PA · Zbl 1223.65023 |
| [23] | Gill, P. E.; Saunders, M. A.; Shinnerl, J. R., On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Optim., 17, 35-46 (1996) · Zbl 0878.49020 |
| [24] | 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 |
| [25] | Kollmann, M.; Kolmbauer, M.; Langer, U.; Wolfmayr, M.; Zulehner, W., A robust finite element solver for a multiharmonic parabolic optimal control problem, Comput. Math. Appl., 65, 469-486 (2013) · Zbl 1319.49043 |
| [26] | Krendl, W.; Simoncini, V.; Zulehner, W., Stability estimates and structural spectral properties of saddle point problems, Numer. Math., 124, 1, 183-213 (2013) · Zbl 1269.65032 |
| [27] | Liang, Z.-Z.; Axelsson, O.; Neytcheva, M., A robust structured preconditioner for the time-harmonic parabolic optimal control problem, Numer. Algorithms, 79, 575-596 (2018) · Zbl 1400.49041 |
| [28] | Napov, A.; Notay, Y., An algebraic multigrid method with guaranteed convergence rate, SIAM J. Sci. Comput., 34, 2, A1079-A1109 (2012) · Zbl 1248.65037 |
| [29] | Y. Notay, AGMG software and documentation, see http://agmg.eu/; Y. Notay, AGMG software and documentation, see http://agmg.eu/ |
| [30] | Notay, Y., Aggregation-based algebraic multigrid for convection-diffusion equations, SIAM J. Sci. Comput., 34, 4, A2288-A2316 (2012) · Zbl 1250.76139 |
| [31] | Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 4, 617-629 (1975) · Zbl 0319.65025 |
| [32] | Paige, C. C.; Saunders LSQR, M. A., An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 1, 43-71 (1982) · Zbl 0478.65016 |
| [33] | Pearson, J. W.; Wathen, A. J., A new approximation of the Schur complement in preconditioners for PDE-constrained optimization, Numer. Linear Algebra Appl., 19, 5, 816-829 (2012) · Zbl 1274.65187 |
| [34] | Pearson, J. W.; Wathen, A. J., Fast iterative solvers for convection-diffusion control problems, Electron. Trans. Numer. Anal., 40, 294-310 (2013) · Zbl 1287.49031 |
| [35] | 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 |
| [36] | Saad, Y., A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14, 2, 461-469 (1993) · Zbl 0780.65022 |
| [37] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM · Zbl 1002.65042 |
| [38] | Saad, Y.; Schultz GMRES, M. H., A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018 |
| [39] | Vanderbei, R. J., Symmetric quasidefinite matrices, SIAM J. Optim., 5, 100-113 (1995) · Zbl 0822.65017 |
| [40] | Widlund, O., A Lanczos method for a class of nonsymmetric systems of equations, SIAM J. Numer. Anal., 15, 801-812 (1978) · Zbl 0398.65030 |
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.
