Preconditioned global GPBiCG method for solving saddle point problems with multiple right-hand sides and its convergence analysis. (English) Zbl 1482.65056
Summary: We propose the preconditioned global generalized product-type method based on the preconditioned global BiCG method to solve nonsymmetric saddle point problems with multiple right-hand sides. We apply an indefinite preconditioner to enhance the convergence rate of the method. We also present some theoretical analysis and discuss the convergence of the PGl-GPBiCG method. Some useful properties of the preconditioned matrix are established. Moreover, we present the bounds for the residual norm of the PGl-GPBiCG method according to the residual norm of the global GMRES method that guarantees convergence. Finally, some numerical examples are presented to show the effciency of the new method in comparison with the preconditioned global BiCGSTAB method, and a comparison with another preconditioner is also provided.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
Keywords:
saddle point problems; preconditioned global GPBiCG; indefinite preconditioning; multiple right-hand sides; convergence analysisSoftware:
SparseMatrixReferences:
| [1] | Badahmane, A., Bentbib, A.H., and Sadok, H.Preconditioned global Krylov subspace methods for solving saddle point problems with multiple right-hand sides, Electron. Trans. Numer. Anal. 51 (2019), 495-511. · Zbl 1431.65028 |
| [2] | Badahmane, A., Bentbib, A.H. and Sadok, H.Preconditioned Krylov subspace and GMRHSS iteration methods for solving the nonsymmetric saddle point problems,Numer. Algorithms, 84 (2020), 1295-1312. · Zbl 1452.65055 |
| [3] | Bai Z.-Z. and Benzi, M.Regularized HSS iteration methods for saddlepoint linear systems,BIT Numerical Mathematics, 57 (2017), 287-311. · Zbl 1367.65048 |
| [4] | Bai, Z.-Z., Golub, G.H., Lu, L.-Z. and Yin, J.-F.Block triangular skewHermitian splitting methods for positive-definite linear systems,SIAM J. Sci. Comput. 26 (2004), 844-863. · Zbl 1079.65028 |
| [5] | Bai, Z.-Z., Golub, G.H. and Pan, J.-Y.Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems,Numer. Math. 98 (2004), 1-32. · Zbl 1056.65025 |
| [6] | Bai, Z.-Z., Ng, M.K. and Wang, Z.-Q.Constraint preconditioners for symmetric indefinite matrices,SIAM J. Matrix Anal. Appl. 31 (2009), 410-433. · Zbl 1195.65033 |
| [7] | Bai, Z.-Z., Parlett, B.N. and Wang, Z.-Q.On generalized successive overrelaxation methods for augmented linear systems,Numer. Math. 102 (2005), 1-38. · Zbl 1083.65034 |
| [8] | Bellalij, M., Jbilou, K. and Sadok, H.New convergence results on the global GMRES method for diagonalizable matrices,J. Comput. Appl. Math. 219 (2008), 350-358. · Zbl 1196.65068 |
| [9] | Benzi M. and Golub, G.H.A preconditioner for generalized saddle point problems,SIAM J. Matrix Anal. Appl. 26 (2004), 20-41. · Zbl 1082.65034 |
| [10] | Benzi, M. and Wathen, A.J. Some preconditioning techniques for saddle point problems. Model order reduction: theory, research aspects and applications, 195-211, Math. Ind., 13, Eur. Consort. Math. Ind. (Berl.), Springer, Berlin, 2008. · Zbl 1152.65425 |
| [11] | Bramble, J.H., Pasciak, J.E. and Vassilev, A.T.Analysis of the inexact Uzawa algorithm for saddle point problems,SIAM J. Numer. Anal. 34 (1997), 1072-1092. · Zbl 0873.65031 |
| [12] | Bramble, J.H., Pasciak, J.E. and Vassilev, A.T.Uzawa type algorithms for nonsymmetric saddle point problems,Math. Comp. 69 (2000), 667- 689. · Zbl 0951.65122 |
| [13] | Brezzi, F. and Fortin, M.Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, 15. Springer-Verlag, New York, 1991. · Zbl 0788.73002 |
| [14] | Cao, Z.-H.Positive stable block triangular preconditioners for symmetric saddle point problems,Appl. Numer. Math 57 (2007), 899-910. · Zbl 1118.65021 |
| [15] | Cao, Y., Du, J. and Niu, Q.Shift-splitting preconditioners for saddle point problems,J. Comput. Appl. Math. 272 (2014), 239-250. · Zbl 1303.65012 |
| [16] | Chen, C. and Ma, C.A generalized shift-splitting preconditioner for saddle point problems,Appl. Math. Lett. 43 (2015), 49-55. · Zbl 1315.65030 |
| [17] | Davis, T. and Hu, Y.The university of Florida sparse matrix collection, ACM Trans. Math. Software 38 (2011), no. 1, Art. 1, 25 pp. · Zbl 1365.65123 |
| [18] | Elman, H.C., Silvester, D.J. and Wathen, A.J.Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics, Numerical Mathematics and Scientific Computation. Oxford University Press, New York, 2005. · Zbl 1083.76001 |
| [19] | Feng, T.T., Chen, G.L. and Guo, X.P.An accelerated SOR-Like method for generalized saddle point problems,East Asian J. Appl. Math. 8 (2018), 70-81. · Zbl 1478.65019 |
| [20] | Golub, G.H., Wu, X. and Yuan, J.-Y.SOR-like methods for augmented systems, BIT 41 (2001), 71-85. · Zbl 0991.65036 |
| [21] | Gould, N., Orban D. and Rees, T.Projected Krylov methods for saddle point systems,SIAM J. Matrix Anal. Appl. 35 (2014), 1329-1343. · Zbl 1312.65043 |
| [22] | Guo, C. and Li, J.,A new preconditioner for solving weighted Toeplitz least squares problems,Math. Appl. (Wuhan) 33 (2020), no. 1, 172-185. · Zbl 1449.65043 |
| [23] | Jbilou, K., Sadok, H. and Tinzefte, A.Oblique projection methods for linear systems with multiple right-hand sides,Electron Trans. Numer. Anal. 20 (2005), 119-138. · Zbl 1121.65313 |
| [24] | Jiang, M.-Q., Cao, Y. and Yao, L.-Q.On parametrized block triangular preconditioners for generalized saddle point problems,Appl. Math. Comput. 216 (2010), 1777-1789. · Zbl 1194.65049 |
| [25] | Keller, C., Gould, N.I.M. and Wathen, A.J.Constraint preconditioning for indefinite linear systems,SIAM J. Matrix Anal. Appl. 21 (2000), 1300-1317. · Zbl 0960.65052 |
| [26] | Li, C., Li, Z., Evans, D.J. and Zhang, T.A note on an SOR-like method for augmented systems,IMA J. Numer. Anal. 23 (2003), 581-592. · Zbl 1053.65020 |
| [27] | Luksˇan, L. and Vlcˇcek, J.Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems,Numer. Linear Algebra Appl., 5 (1998), 219-247. · Zbl 0937.65066 |
| [28] | Murphy, M.F., Golub, G.H. and Wathen, G.H.A note on preconditioning for indefinite linear systems,SIAM J. Sci. Comput 21 (2000), 1969-1972. · Zbl 0959.65063 |
| [29] | Nocedal, J. and Wright, S.J.Numerical optimization,Springer Series in Operations Research, Springer, Berlin 1999. · Zbl 0930.65067 |
| [30] | Pan, J.-Y., Ng, M.K. and Bai, Z.-Z.New preconditioners for saddle point problems,Appl. Math. Comput. 172 (2006), 762-771. · Zbl 1088.65040 |
| [31] | Perugia, I. and Simoncini, V.Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations,Numer. Linear Algebra Appl. 7 (2000), 585-616. · Zbl 1051.65038 |
| [32] | Perugia, I., Simoncini, V. and Arioli, M.Linear algebra methods in a mixed approximation of magnetostatic problems,SIAM J. Sci. Comput. 21 (1999), 1085-1101. · Zbl 1040.78012 |
| [33] | Rozloˇzn´ik, M. and Simoncini, V.Krylov subspace methods for saddle point problems with indefinite preconditioning,SIAM J. Matrix Anal. Appl. 24 (2002), 368-391. · Zbl 1021.65016 |
| [34] | Saad, Y.Iterative Methods for Sparse Linear Systems,SIAM, Philadelphia, 2003. · Zbl 1031.65046 |
| [35] | Salkuyeh, D.K. and Masoudi, M.A new relaxed HSS preconditioner for saddle point problems,Numer. Algor. 74 (2017), 781-795. · Zbl 1367.65044 |
| [36] | Simoncini, V.Block triangular preconditioners for symmetric saddle-point problems,Appl. Numer. Math. 49 (2004), 63-80. · Zbl 1053.65033 |
| [37] | Simoncini, V. and Benzi, D.M.Spectral properties of the Hermitian and skew-Hermitian splitting preconditioner for saddle point problems,SIAM J. Matrix Anal. Appl. 26 (2004/05), 377-389. · Zbl 1083.65047 |
| [38] | Sturler, E.D. and Liesen, J.Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems,SIAM J. Sci. Comput 26 (2005), 598-619. · Zbl 1078.65027 |
| [39] | Taherian, A. and Toutounian, F.Block GPBi-CG method for solving nonsymmetric linear systems with multiple right-hand sides and its convergence analysis,J Numer. Algor. (2021), https://doi.org/10.1007/s11075021-01097-7. · Zbl 1482.65055 |
| [40] | Wen, R., Wu R. and Guan, J.Some generalizations of the new SOR-like method for solving symmetric Saddle point problems,J. Inequal. Appl. 2018, Paper No. 145, 12 pp. · Zbl 1498.65051 |
| [41] | Wesseling, P.Principles of computational fluid dynamics,Vol. 29 of Springer Series in Computational Mathematics, Springer, Berlin 2001. |
| [42] | Wright, M.H.Interior methods for constrained optimization,Acta numerica, 1992, 341-407, Acta Numer., Cambridge Univ. Press, Cambridge, 1992. · Zbl 0766.65053 |
| [43] | Wright, S.J.Primal-dual interior point methods,Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. · Zbl 0863.65031 |
| [44] | Wu, X.-N., Golub, G.H., Cuminato, J.A. and Yuan, J.-Y.Symmetrictriangular decomposition and its applications Part II: Preconditioners for indefinite systems.BIT 48(2008), 139-162. · Zbl 1151.65027 |
| [45] | Yun, J.H.Variants of the Uzawa method for saddle point problem,Comput. Math. Appl. 65(2013), 1037-1046. · Zbl 1266.65057 |
| [46] | Zhang, J. and Dai, H.Global GPBiCG method for complex non-Hermitian linear systems with multiple right-hand sides,Comput. Appl. Math. 35 (2016), 171-185. · Zbl 1339.65051 |
| [47] | Zheng, Q. and Ma, C.A new SOR-Like method for the saddle point problems,Appl. Math. Comput. 233 (2014), 421-429 · Zbl 1336.65050 |
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.
