×

Parameterized approximate block LU preconditioners for generalized saddle point problems. (English) Zbl 1382.65080

Summary: In this paper, we are concerned with the iteration solution of generalized saddle point problems. Based on the exact block LU factorization of the coefficient matrix, we construct a class of parameterized approximate block LU factorization preconditioners, which rely on suitable approximations of the Schur complement of the \((1,1)\) block of the coefficient matrix. Convergence of the corresponding iteration methods is analyzed and the optimal iteration parameters minimizing the spectral radii are deduced. Algebraic characteristics of the related preconditioned matrices are discussed, including eigenvalue and eigenvector distributions and upper bounds for degree of the minimal polynomial. The established results extend those of the approximate factorization and variants of the Hermitian and skew-Hermitian splitting and positive and skew-Hermitian splitting preconditioners for saddle point problems. Numerical experiments are demonstrated to illustrate the efficiency of the new preconditioners.

MSC:

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

Software:

IFISS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benzi, M.; Golub, G.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 1-137 (2005) · Zbl 1115.65034
[2] Simoncin, V.; Benzi, M., Specrtal properities of the Hermitian and skew-Hermitian splitting preconditioner for saddle point problems, SIAM J. Matrix Anal. Appl., 26, 2, 377-389 (2004) · Zbl 1083.65047
[3] Saad, Y.; Schultz, M., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018
[4] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM Philadephia · Zbl 1002.65042
[5] Van der Vorst, H. A., Iterative Krylov methods for large linear systems, Vol. 13 (2003), Cambridge University Press · Zbl 1023.65027
[6] Benzi, M.; Olshanskii, A., An augmented Lageangian-based approach to the Ossen problem, SIAM J. Sci. Comput., 28, 2095-2113 (2006) · Zbl 1126.76028
[7] Golub, G.; Greif, C., On solving block-structured indefinite linear systems, SIAM J. Sci. Comput., 24, 2076-2092 (2003) · Zbl 1036.65033
[8] Shen, S.-Q.; Huang, T.-Z.; Zhang, J.-S., Augmentation block triangular preconditioners for regularized saddle point problems, SIAM J. Matrix Anal. Appl., 33, 3, 721-741 (2012) · Zbl 1261.65033
[9] Shen, S.-Q.; Bao, W.-D.; Jian, L., On augmentation block triangular preconditioners for regularized saddle point problems, Comput. Math. Appl., 69, 8, 828-837 (2015) · Zbl 1443.65038
[10] Benzi, M.; Simoncini, V., On the eigenvalues of a class of saddle point matrices, Numer. Math., 103, 2, 173-196 (2006) · Zbl 1103.65033
[11] Bai, Z.-Z.; Golub, G. H.; Pan, J.-Y., Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., 98, 1, 1-32 (2004) · Zbl 1056.65025
[12] Bai, Z.-Z.; Golub, G., Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27, 1, 1-23 (2007) · Zbl 1134.65022
[13] Cao, Y.; Yao, L.-Q.; Jiang, M.-Q., A relaxed HSS preconditioner for saddle point problems from meshfree discretization, J. Comput. Math., 31, 4, 398-421 (2013) · Zbl 1299.65043
[14] Cao, Y.; Ren, Z.-R.; Shi, Q., A simplified HSS preconditioner for generalized saddle point problems, BIT, 56, 2, 423-439 (2016) · Zbl 1347.65056
[15] Cao, Y.; Dong, J.-L.; Wang, Y.-M., A relaxed deteriorated PSS preconditioner for nonsymmetric saddle point problems from the steady Navier-Stokes equation, J. Comput. Appl. Math., 273, 41-60 (2015) · Zbl 1310.65034
[16] Liang, Z.-Z.; Zhang, G.-F., Two new variants of the HSS preconditioner for regularized saddle point problems, Comput. Math. Appl., 72, 603-619 (2016) · Zbl 1359.65043
[17] Liang, Z.-Z.; Zhang, G.-F., SIMPLE-like preconditioners for saddle point problems from the steady Navier-Stokes equations, J. Comput. Appl. Math., 302, 211-223 (2016) · Zbl 1337.65027
[18] Wang, R.-R.; Niu, Q.; Ma, F.; Lu, L.-Z., Spectral properties of a class of matrix splitting preconditioners for saddle point problems, J. Comput. Appl. Math., 298, 138-151 (2016) · Zbl 1331.65059
[19] Salkuyeh, D. K.; Masoudi, M., A new relaxed HSS preconditioner for saddle point problems, Numer. Algorithms, 74, 3, 781-795 (2017) · Zbl 1367.65044
[20] Zhang, J.-L.; Gu, C.-Q., A variant of the deteriorated PSS preconditioner for nonsymmetric saddle point problems, BIT, 56, 2, 587-604 (2016) · Zbl 1342.65106
[21] Murphy, M. F.; Golub, G. H.; Wathen, A. J., A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21, 6, 1969-1972 (2000) · Zbl 0959.65063
[22] Cao, Z.-H., A note on block diagonal and constraint preconditioners for non-symmetric indefinite linear systems, Int. J. Comput. Math., 83, 4, 383-395 (2006) · Zbl 1113.65045
[23] Phoon, K.-K.; Toh, K.-C.; Chan, S.-H.; Lee, F.-H., An efficient diagonal preconditioner for finite element solution of Biot’s consolidation equations, Int. J. Numer. Methods Engrg., 55, 4, 377-400 (2002) · Zbl 1076.74558
[24] Axelsson, O., Unified analysis of preconditioning methods for saddle point matrices, Numer. Linear Algebra Appl., 22, 2, 233-253 (2015) · Zbl 1363.65047
[25] Gould, N.; Simoncini, V., Spectral analysis of saddle point matrices with indefinite leading blocks, SIAM J. Matrix Anal. Appl., 31, 3, 1152-1171 (2009) · Zbl 1200.15007
[26] Axelsson, O.; Neytcheva, M., Eigenvalue estimates for preconditioned saddle point matrices, Numer. Linear Algebra Appl., 13, 4, 339-360 (2006) · Zbl 1224.65080
[27] Ipsen, I. C.F., A note on preconditioning nonsymmetric matrices, SIAM J. Sci. Comput., 23, 3, 1050-1051 (2001) · Zbl 0998.65049
[28] de Sturler, E., E.; Liesen, J., Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. Part I: Theory, SIAM J. Sci. Comput., 26, 5, 1598-1619 (2005) · Zbl 1078.65027
[29] Cao, Z.-H., Block triangular Schur complement preconditioners for saddle point problems and application to the Oseen equations, Appl. Numer. Math., 60, 3, 193-207 (2010) · Zbl 1191.65022
[30] Toh, K.-C.; Phoon, K.-K.; Chan, S.-H., Block preconditioners for symmetric indefinite linear systems, Int. J. Numer. Methods Engrg., 60, 8, 1361-1381 (2004) · Zbl 1065.65064
[31] Cao, Z.-H., Positive stable block triangular preconditioners for symmetric saddle point problems, Appl. Numer. Math., 57, 8, 899-910 (2007) · Zbl 1118.65021
[32] Simoncini, V., Block triangular preconditioners for symmetric saddle-point problems, Appl. Numer. Math., 49, 1, 63-80 (2004) · Zbl 1053.65033
[33] Jiang, M.-Q.; Cao, Y.; Yao, L.-Q., On parameterized block triangular preconditioners for generalized saddle point problems, Appl. Math. Comput., 216, 6, 1777-1789 (2010) · Zbl 1194.65049
[34] Cao, Y.; Jiang, M.-Q.; Zheng, Y.-L., A note on the positive stable block triangular preconditioner for generalized saddle point problems, Appl. Math. Comput., 218, 22, 11075-11082 (2012) · Zbl 1280.65028
[35] Wu, S.-L.; Huang, T.-Z.; Li, C.-X., Generalized block triangular preconditioner for symmetric saddle point problems, Computing, 84, 183-208 (2009) · Zbl 1184.65035
[36] Wu, S.-L.; Li, C.-X., Eigenvalue estimates of an indefinite block triangular preconditioner for saddle point problems, J. Comput. Appl. Math., 260, 349-355 (2014) · Zbl 1293.65044
[37] Notay, Y., A new analysis of block preconditioners for saddle point problems, SIAM J. Matrix Anal. Appl., 35, 1, 143-173 (2014) · Zbl 1297.65034
[38] Bergamaschi, L., On eigenvalue distribution of constraint-preconditioned symmetric saddle point matrices, Numer. Linear Algebra Appl., 19, 4, 754-772 (2012) · Zbl 1274.65084
[39] Shen, S.-Q.; Huang, T.-Z., A symmetric positive definite preconditioner for saddle-point problems, Int. J. Comput. Math., 88, 14, 2942-2954 (2011) · Zbl 1253.65050
[40] Golub, G. H.; Wathen, A. J., An iteration for indefinite systems and its application to the Navier-Stokes equations, SIAM J. Sci. Comput., 19, 2, 530-539 (1998) · Zbl 0912.76053
[41] Keller, C.; Gould, N. I.; Wathen, A., Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21, 4, 1300-1317 (2000) · Zbl 0960.65052
[42] Dollar, H., Constraint-style preconditioners for regularized saddle point problems, SIAM J. Matrix Anal. Appl., 29, 2, 672-684 (2007) · Zbl 1144.65032
[43] Botchev, M. A.; Golub, G. H., A class of nonsymmetric preconditioners for saddle point problems, SIAM J. Matrix Anal. Appl., 27, 4, 1125-1149 (2006) · Zbl 1104.65038
[44] Vuik, K.; Saghir, A.; Boerstoel, G., The Krylov accelerated SIMPLE(R) method for flow problems in industrial furnaces, Int. J. Numer. Methods Fluids, 33, 7, 1027-1040 (2000) · Zbl 0960.76054
[45] Li, C.-G.; Vuik, C., Eigenvalue analysis of the SIMPLE preconditioning for incompressible flow, Numer. Linear Algebra Appl., 11, 5-6, 511-523 (2004) · Zbl 1164.65398
[46] Elman, H.; Howle, V. E.; Shadid, J.; Shuttleworth, R.; Tuminaro, R., A taxonomy and comparison of parallel block multi-level preconditioners for the incompressible Navier-Stokes equations, J. Comput. Phys., 227, 3, 1790-1808 (2008) · Zbl 1290.76023
[47] Bellavia, S.; De Simone, V.; di Serafino, D.; Morini, B., Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections, SIAM J. Optim., 25, 3, 1787-1808 (2015) · Zbl 1323.65064
[48] Benzi, M.; Deparis, S.; Grandperrin, G.; Quarteroni, A., Parameter estimates for the relaxed dimensional factorization preconditioner and application to hemodynamics, Comput. Methods Appl. Mech. Engrg., 300, 129-145 (2016) · Zbl 1423.76212
[49] Bai, Z.-Z.; Parlett, B.; Wang, Z.-Q., On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102, 1, 1-38 (2005) · Zbl 1083.65034
[50] Elman, H.; Ramage, A.; Silvester, D., Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow, ACM Trans. Math. Softw., 33, 2, 14 (2007) · Zbl 1365.65326
[51] Cao, Y.; Wang, A.; Chen, Y.-J., A modified relaxed positive-semidefinite and skew-Hermitian splitting preconditioner for generalized saddle point problems, East Asian J. Appl. Math., 7, 1, 192-201 (2017) · Zbl 1392.65026
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.