Preconditioned global GPBiCG method for solving saddle point problems with multiple right-hand sides and its convergence analysis

Document Type : Research Article

Authors

• A. Taherian ¹
• F. Toutounian ²

¹ Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, Iran.

² Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, Iran and The Center of Excellence on Modeling and Control Systems, Ferdowsi University of Mashhad, Iran.

10.22067/ijnao.2021.71036.1044

Abstract

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.
 

Keywords

• Saddle point problems
• Preconditioned global GPBiCG
• Indefinite preconditioning
• Multiple right-hand sides
• Convergence analysis

20.1001.1.24236977.2022.12.1.5.9

Main Subjects

• Numerical linear algebra and its applications

---

References

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.
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.
3. Bai Z.-Z. and Benzi, M. Regularized HSS iteration methods for saddlepoint linear systems, BIT Numerical Mathematics, 57 (2017), 287–311.
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.
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.
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.
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.
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.
9. Benzi M. and Golub, G.H. A preconditioner for generalized saddle point problems,SIAM J. Matrix Anal. Appl. 26 (2004), 20–41.
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.
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.
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.
13. Brezzi, F. and Fortin, M. Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, 15. Springer-Verlag, New York, 1991.
14. Cao, Z.-H. Positive stable block triangular preconditioners for symmetric saddle point problems, Appl. Numer. Math 57 (2007), 899–910.
15. Cao, Y., Du, J. and Niu, Q. Shift-splitting preconditioners for saddle point problems, J. Comput. Appl. Math. 272 (2014), 239–250.
16. Chen, C. and Ma, C. A generalized shift-splitting preconditioner for saddle point problems, Appl. Math. Lett. 43 (2015), 49–55.
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.
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.
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.
20. Golub, G.H., Wu, X. and Yuan, J.-Y. SOR-like methods for augmented systems, BIT 41 (2001), 71–85.
21. Gould, N., Orban D. and Rees, T. Projected Krylov methods for saddle point systems, SIAM J. Matrix Anal. Appl. 35 (2014), 1329–1343.
22. Guo, C. and Li, J., A new preconditioner for solving weighted Toeplitzl east squares problems, Math. Appl. (Wuhan) 33 (2020), no. 1, 172–185.
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.
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.
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.
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.
 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.
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.
29. Nocedal, J. and Wright, S.J. Numerical optimization, Springer Series in Operations Research, Springer, Berlin 1999.
30. Pan, J.-Y., Ng, M.K. and Bai, Z.-Z. New preconditioners for saddle point problems, Appl. Math. Comput. 172 (2006), 762–771.
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.
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.
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.
34. Saad, Y. Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003.
35. Salkuyeh, D.K. and Masoudi, M. A new relaxed HSS preconditioner for saddle point problems, Numer. Algor. 74 (2017), 781–795.
36. Simoncini, V. Block triangular preconditioners for symmetric saddle-point problems, Appl. Numer. Math. 49 (2004), 63–80.
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.
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.
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/s11075-021-01097-7.
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.
 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.
43. Wright, S.J. Primal-dual interior point methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
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.
45. Yun, J.H. Variants of the Uzawa method for saddle point problem, Comput. Math. Appl. 65(2013), 1037–1046.
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.
47. Zheng, Q. and Ma, C. A new SOR-Like method for the saddle point problems, Appl. Math. Comput. 233 (2014), 421–429.