×

Superior properties of the PRESB preconditioner for operators on two-by-two block form with square blocks. (English) Zbl 1451.65025

Summary: Matrices or operators in two-by-two block form with square blocks arise in numerous important applications, such as in optimal control problems for PDEs. The problems are normally of very large scale so iterative solution methods must be used. Thereby the choice of an efficient and robust preconditioner is of crucial importance. Since some time a very efficient preconditioner, the preconditioned square block, PRESB method has been used by the authors and coauthors in various applications, in particular for optimal control problems for PDEs. It has been shown to have excellent properties, such as a very fast and robust rate of convergence that outperforms other methods. In this paper the fundamental and most important properties of the method are stressed and presented with new and extended proofs. Under certain conditions, the condition number of the preconditioned matrix is bounded by 2 or even smaller. Furthermore, under certain assumptions the rate of convergence is superlinear.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
49M41 PDE constrained optimization (numerical aspects)

Software:

MinRes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Varga, RS, Matrix Iterative Analysis (1962), Englewood Cliffs: Prentice-Hall Inc., Englewood Cliffs · Zbl 0133.08602
[2] Young, DM, Iterative Solution of Large Linear Systems (1971), New York: Academic Press, New York · Zbl 0231.65034
[3] Axelsson, O., Barker, V.A.: Finite element solution of boundary value problems. Theory and Computation. Academic Press, Inc. Orlanda (1984). Reprinted in SIAM’s Classical series in Applied Mathematics, Philadelphia, PA, USA (2001) · Zbl 0537.65072
[4] Hageman, LA; Young, DM, Applied Iterative Methods (1981), San Diego: Academic Press, San Diego · Zbl 0459.65014
[5] Axelsson, O., Iterative Solution Methods (1994), Cambridge: Cambridge University Press, Cambridge · Zbl 0795.65014
[6] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), Boston: PWS Publishing Company, Boston · Zbl 1002.65042
[7] 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
[8] Bai, Z-Z, On preconditioned iteration methods for complex linear systems, J. Eng. Math., 93, 41-60 (2015) · Zbl 1360.65089
[9] Zhong, Z.; Zhang, G-F; Zhu, M-Z, A block alternating splitting iteration method for classical block two-by-two complex linear systems, J. Comput. Appl. Math., 288, 203-214 (2015) · Zbl 1328.65078
[10] Wang, J.; Guo, X.; Zhong, H., Accelerated GPMHSS method for solving complex systems of linear equations, East Asian J. Appl. Math., 7, 143-155 (2017) · Zbl 1392.65078
[11] Axelsson, O.; Vassilevski, PS, A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning, SIAM. J. Matrix Anal. Appl., 12, 625-644 (1991) · Zbl 0748.65028
[12] Saad, Y., A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14, 461-469 (1993) · Zbl 0780.65022
[13] Axelsson, O.; Farouq, S.; Neytcheva, M., Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems. Poisson and convection-diffusion control, Numer. Algorithms, 73, 631-663 (2016) · Zbl 1353.65059
[14] Axelsson, O., Neytcheva, M.: Operator splittings for solving nonlinear, coupled multiphysics problems with an application to the numerical solution of an interface problem. TR 2011-009, Department of Information Technology, Uppsala University (April 2011)
[15] 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
[16] Boyanova, P.; Do-Quang, M.; Neytcheva, M., Efficient preconditioners for large scale binary Cahn-Hilliard models, Comput Methods Appl Math, 12, 1-22 (2012) · Zbl 1284.65047
[17] Axelsson, O.; Boyanova, P.; Kronbichler, M.; Neytcheva, M.; Wu, X., Numerical and computational efficiency of solvers for two-phase problems, Comput. Math. Appl., 65, 301-314 (2013) · Zbl 1319.76025
[18] Boyanova, P.; Neytcheva, M., Efficient numerical solution of discrete multi-component Cahn-Hilliard systems, Comput. Math. Appl., 67, 106-121 (2014) · Zbl 1381.76155
[19] 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
[20] Axelsson, O., Lukáš, D.: Preconditioners for time-harmonic optimal control eddy-current problems. In: Lirkov I., Margenov S. (eds.), Large-Scale Scientific Computing, LSSC 2017, Lecture Notes in Computer Science, vol. 10665, pp. 47-54. Springer, Cham (2017) · Zbl 1476.65215
[21] Liang, Z-Z; Axelsson, O.; Neytcheva, M., A robust structured preconditioner for time-harmonic parabolic optimal control problems, Numer. Algorithms, 79, 575-596 (2018) · Zbl 1400.49041
[22] Axelsson, O.; Neytcheva, M.; Liang, Z-Z, Parallel solution methods and preconditioners for evolution equations, Math. Model Anal., 23, 287-308 (2018) · Zbl 1488.65064
[23] Pearson, J.; Wathen, A., A new approximation of the Schur complement in preconditioners for PDE-constrained optimization, Numer. Linear Algebra Appl., 19, 816-829 (2012) · Zbl 1274.65187
[24] Rees, T.; Stoll, M., Block-triangular preconditioners for PDE-constrained optimization, Numer. Linear Algebra Appl., 17, 977-996 (2010) · Zbl 1240.65097
[25] Bai, Z-Z, Block preconditioners for elliptic PDE-constrained optimization problems, Computing, 91, 379-395 (2011) · Zbl 1242.65121
[26] Stoll, M.; Wathen, A., Preconditioning for partial differential equation constrained optimization with control constraints, Numer. Linear Algebra Appl., 19, 53-71 (2012) · Zbl 1274.65189
[27] Simoncini, V., Reduced order solution of structured linear systems arising in certain PDE-constrained optimization problems, Comput. Optim. Appl., 53, 591-617 (2012) · Zbl 1266.49061
[28] Kolmbauer, M.; Langer, U., A robust preconditioned MINRES solver for distributed time-periodic eddy current optimal control problems, SIAM J. Sci. Comput., 34, B785-B809 (2012) · Zbl 1258.49059
[29] Kollmann, M.; Zulehner, W., A robust preconditioner for distributed optimal control for Stokes flow with control constraints, Numer. Math. Adv. Appl., 2011, 771-779 (2013) · Zbl 1311.76106
[30] Pearson, J-W; Stoll, M.; Wathen, A-J, Preconditioners for state-constrained optimal control problems with Moreau-Yosida penalty function, Numer. Linear Algebra Appl., 21, 81-97 (2014) · Zbl 1324.49026
[31] Morini, B.; Simoncini, V.; Tani, M., A comparison of reduced and unreduced KKT systems arising from interior point methods, Comput. Optim. Appl., 68, 1-27 (2017) · Zbl 1406.90088
[32] Ke, Y-F; Ma, Ch-F, Some preconditioners for elliptic PDE-constrained optimization problems, Comput. Math. Appl., 75, 2795-2813 (2018) · Zbl 1415.65248
[33] Zulehner, W.: Efficient solvers for saddle point problems with applications to PDE-constrained optimization. In: Advanced Finite Element Methods and Applications, Lect. Notes Appl. Comput. Mech., vol. 66, pp. 197-216. Springer, Heidelberg (2013) · Zbl 1263.65030
[34] Bai, Z-Z; Golub, G.; Ng, M., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032
[35] Dong, Y.; Gu, C., On PMHSS iteration methods for continuous Sylvester equations, J. Comput. Math., 35, 600-619 (2017) · Zbl 1413.65130
[36] Paige, CC; Saunders, MA, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025
[37] Bai, Z-Z; Benzi, M., Regularized HSS iteration methods for saddle-point linear systems, BIT Numer. Math., 57, 287-311 (2017) · Zbl 1367.65048
[38] 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
[39] Bai, Z-Z; Golub, G., Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27, 1-23 (2007) · Zbl 1134.65022
[40] 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
[41] 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
[42] Battermann, A., Sachs, E.: Block preconditioners for KKT systems in PDE-governed optimal control problems. In: Schulz, V. (eds.) Fast Solution of Discretized Optimization Problems. ISNM International Series of Numerical Mathematics, vol. 138, pp. 1-18. Birkhäuser, Basel (2000) · Zbl 0992.49022
[43] Pearson, J-W; Stoll, M.; Wathen, A-J, Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems, SIAM J. Matrix Anal. Appl., 33, 1126-1152 (2012) · Zbl 1263.65035
[44] Ke, Yi-Fen; Ma, Chang-Feng, Some preconditioners for elliptic PDE-constrained optimization problems, Comput. Math. Appl., 75, 2795-2813 (2018) · Zbl 1415.65248
[45] Becker, R.; Vexler, B., Optimal control of the convection-diffusion equation using stabilized finite element methods, Numer. Math., 106, 349-367 (2007) · Zbl 1133.65037
[46] 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
[47] Haber, E.; Ascher, UM, Preconditioned all-at-once methods for large, sparse parameter estimation problems, Inverse Prob., 17, 1847-1864 (2001) · Zbl 0995.65110
[48] Axelsson, O., Blaheta, R., Béreš, M.: A boundary optimal control identification problem (in preparation)
[49] Barker, AT; Rees, T.; Stoll, M., A fast solver for an \(H^1\) Regularized PDE-constrained optimization problems, Commun. Comput. Phys., 19, 143-167 (2016) · Zbl 1373.49028
[50] Axelsson, O.; Farouq, S.; Neytcheva, M., A preconditioner for optimal control problems constrained by Stokes equation with a time-harmonic control, J. Comput. Appl. Math., 310, 5-18 (2017) · Zbl 1347.49048
[51] Bai, Z-Z, Rotated block triangular preconditioning based on PMHSS, Sci. China Math., 56, 12, 2523-2538 (2013) · Zbl 1305.65114
[52] Rossi, T.; Toivanen, J., A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension, SIAM J. Sci. Comput., 20, 5, 1778-1796 (1999) · Zbl 0931.65020
[53] 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
[54] Axelsson, O.; Liang, Z-Z, Parameter modified versions of preconditioning and iterative inner product free refinement methods for two-by-two block matrices, Lin. Algebra Appl., 582, 403-429 (2019) · Zbl 1425.65047
[55] Wang, Z-Q, On a Chebyshev accelerated splitting iteration method with application to two-by-two block linear systems, Numer. Linear Algebra Appl., 25, e2172 (2018) · Zbl 1513.65087 · doi:10.1002/nla.2172
[56] Axelsson, O.; Salkuyeh, DK, A new version of a preconditioning method for certain two-by-two block matrices with square blocks, BIT Numer. Math., 59, 321-342 (2019) · Zbl 07074115
[57] Moret, I., A note on the superlinear convergence of GMRES, SIAM J. Numer. Anal., 34, 513-516 (1997) · Zbl 0873.65054
[58] van der Sluis, A.; van der Vorst, HA, The rate of convergence of Conjugate Gradients, Numer. Math., 48, 543-560 (1986) · Zbl 0596.65015
[59] van der Vorst, HA; Vuik, C., The superlinear convergence behaviour of GMRES, J. Comput. Appl. Math., 48, 327-341 (1993) · Zbl 0797.65026
[60] Winther, R., Some superlinear convergence results for the conjugate gradient method, SIAM J. Numer. Anal., 17, 14-17 (1980) · Zbl 0447.65021
[61] Axelsson, O.; Karátson, J., Mesh independent superlinear PCG rates via compact-equivalent operators, SIAM J. Numer. Anal., 45, 4, 1495-1516 (2007) · Zbl 1151.65081
[62] Axelsson, O.; Karátson, J., Superlinear convergence of the GMRES for PDE-constrained optimization problems, Numer. Funct. Anal. Optim., 39, 9, 921-936 (2018) · Zbl 1392.49035
[63] Axelsson, O.; Karátson, J.; Magoules, F., Superlinear convergence using block preconditioners for the real system formulation of complex Helmholtz equations, Comput. Appl. Math. (2018) · Zbl 1432.65035 · doi:10.1016/j.cam.2018.01.029
[64] Axelsson, O., Karátson, J., Magoules, F.: Superlinear convergence under complex shifted Laplace preconditioners for Helmholtz equations. www.cs.elte.hu/ karatson/Helmholtz-preprint.pdf · Zbl 1432.65035
[65] Gohberg, I., Goldberg, S., Kaashoek, M.A.: Classes of Linear Operators, Vol. I., Operator Theory: Advances and Applications, vol. 49, Birkhäuser Verlag, Basel (1990) · Zbl 0745.47002
[66] Goldstein, CI; Manteuffel, TA; Parter, SV, Preconditioning and boundary conditions without \(H_2\) estimates: \(L_2\) condition numbers and the distribution of the singular values, SIAM J. Numer. Anal., 30, 2, 343-376 (1993) · Zbl 0773.65033
[67] Axelsson, O.; Neytcheva, M.; Ström, A., An efficient preconditioning method for the state box-constrained optimal control problem, J. Numer. Math., 26, 185-207 (2018) · Zbl 1407.65036
[68] Herzog, R.; Sachs, E., Preconditioned conjugate gradient method for optimal control problems with control and state constraints, SIAM J. Matrix Anal. Appl., 31, 2291-2317 (2010) · Zbl 1209.49038
[69] Axelsson, O.; Karátson, J., Superlinearly convergent CG methods via equivalent preconditioning for nonsymmetric elliptic operators, Numer. Math., 99, 2, 197-223 (2004) · Zbl 1061.65043
[70] Axelsson, O.; Karátson, J., Equivalent operator preconditioning for linear elliptic problems, Numer. Algorithms, 50, 3, 297-380 (2009) · Zbl 1162.65024
[71] Ito, K.; Kunisch, K., Semi-smooth Newton methods for state-constrained optimal control problems, Syst. Control Lett., 50, 221-228 (2003) · Zbl 1157.49311
[72] Hintermüller, M.; Hinze, M., Moreau-Yosida regularization in state constrained elliptic control problems: error estimates and parameter adjustment, SIAM J. Numer. Anal., 47, 1666-1683 (2009) · Zbl 1191.49036
[73] Porcelli, M.; Simoncini, V.; Tani, M., Preconditioning of active-set Newton methods for PDE-constrained optimal control problems, SIAM J. Sci. Comput., 37, S472-S502 (2015) · Zbl 1325.65066
[74] Faber, V.; Manteuffel, T.; Parter, SV, On the theory of equivalent operators and application to the numerical solution of uniformly elliptic partial differential equations, Adv. Appl. Math., 11, 109-163 (1990) · Zbl 0718.65043
[75] Kolmbauer, M.: The multiharmonic finite element and boundary element method for simulation and control of eddy current problems. Ph.D. Thesis, Johannes Kepler Universität, Linz (2012) · Zbl 1290.49056
[76] Cao, S-M; Feng, W.; Wang, Z-Q, On a type of matrix splitting preconditioners for a class of block two-by-two linear systems, Appl. Math. Lett., 79, 205-210 (2018) · Zbl 1461.65036
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.