A new Bramble-Pasciak-like preconditioner for saddle point problems

Previous Article
A generalization of the positive-definite and skew-Hermitian splitting iteration
NACO Home
This Issue
Next Article
Newton-MHSS methods for solving systems of nonlinear equations with complex symmetric Jacobian matrices

2012, 2(4): 823-838. doi: 10.3934/naco.2012.2.823

A new Bramble-Pasciak-like preconditioner for saddle point problems

1.	Nanhai College, South China Normal University, Foshan 528225, China
2.	School of Mathematical Sciences, South China Normal University, Guangzhou, 510631, China

Received December 2011 Revised October 2012 Published November 2012

Abstract
Related Papers

A new Bramble-Pasciak-like preconditioner with parameter is proposed for solving a linear system in the saddle point form. The system can be reformulated as a symmetric positive definite system with respect to some inner product and thus can be solved by the Bramble-Pasciak conjugate gradient (BPCG) method. Based on the spectral condition number of the associated system, the quasi-optimal parameters can be obtained to improve the convergence rate of the BPCG method. Numerical experiments on the Stokes problem are given to illustrate our theoretical results.

Keywords: convergence rate., spectral condition number, Bramble-Pasciak conjugate gradient method, Bramble-Pasciak-like preconditioner, Saddle point problems.

Mathematics Subject Classification: Primary: 65F10, 65F1.

Citation: Xiao-Fei Peng, Wen Li. A new Bramble-Pasciak-like preconditioner for saddle point problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 823-838. doi: 10.3934/naco.2012.2.823

References:

[1]	O. Axelsson and G. Lindskog, On the rate of convergence of the preconditioned conjugate gradient method,, Numer. Math., 48 (1986), 499. doi: 10.1007/BF01389448.
[2]	Z. Z. Bai and G. Q. Li, Restrictively preconditioned conjugate gradient methods for systems of linear equations,, IMA J. Numer. Anal., 23 (2003), 561. doi: 10.1093/imanum/23.4.561.
[3]	J. H. Bramble and J. E. Pasciak, A preconditioning technique for indefinite systems resulting from mixed approximations of ellipstic problems,, Math. Comp., 50 (1988), 1. doi: 10.1090/S0025-5718-1988-0917816-8.
[4]	M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems,, Acta Numer., 14 (2005), 1. doi: 10.1017/S0962492904000212.
[5]	M. Benzi and V. Simoncini, On the eigenvalues of a class of saddle point matrices,, Numer. Math., 103 (2006), 173. doi: 10.1007/s00211-006-0679-9.
[6]	H. S. Dollar, N. I. M Gould, M. Stoll and A. J. Wathen, Preconditioning saddle-point systems with applications in optimization,, SIAM J. Sci. Comput., 32 (2010), 249. doi: 10.1137/080727129.
[7]	H. C. Elman, D. J. Silvester and Andrew J. Wathen, "Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics,", in, (2005).
[8]	H. C. Elman, A. Ramage and D. J. Silvester, Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow,, ACM Trans. Math. Softw., 33 (2007), 251.
[9]	G. N. Gatica and N. Heuer, Conjugate gradient method for dual-dual mixed formulations,, Math. Comp., 71 (2002), 1455. doi: 10.1090/S0025-5718-01-01394-1.
[10]	M. R. Hestenes and E. Stiefel, Methods of conjugate gradient for solving linear systems,, J. Res. Nat. Bur. Stand., 49 (1952), 409.
[11]	A. Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term,, SIAM J. Sci. Comput., 19 (1998), 172. doi: 10.1137/S1064827596303624.
[12]	J. Liesen and B. N. Parlett, On nonsymmetric saddle point matrices that allow conjugate gradient iterations,, Numer. Math., 108 (2008), 605. doi: 10.1007/s00211-007-0131-9.
[13]	J. A. Meijerink and H. A. Van der vorst, An iterative solution method for linear equation systems of which the coefficient matrix is symmetric M-matrix,, Math. Comp., 31 (1977), 148.
[14]	X. F. Peng, W. Li and S. H. Xiang, New preconditioners based on symmetric-triangular decomposition for saddle point problems,, Computing, 93 (2011), 27. doi: 10.1007/s00607-011-0150-3.
[15]	J. Schöberl and W. Zulehner, Symmetric indefinite preconditioners for saddle point problems with applications to pde-constrained optimization problems,, SIAM J. Matrix Anal. Appl., 29 (2007), 752. doi: 10.1137/060660977.
[16]	M. Stoll and A. J. Wathen, Combination preconditioning and the Bramble-Pasciak⁺ preconditioner,, SIAM J. Matrix Anal. Appl., 30 (2008), 582. doi: 10.1137/070688961.
[17]	X. N. Wu, G. H. Golub, J. A. Cuminato and J. Y. Yuan, Symmetric-triangular decomposition and its applications - Part Π: Preconditioners for indefinite systems,, BIT Numer. Math., 48 (2008), 139. doi: 10.1007/s10543-008-0160-5.
[18]	W. Zulehner, Analysis of iterative methods for saddle point problems: A unified approach,, Math. Comp., 71 (2002), 479. doi: 10.1090/S0025-5718-01-01324-2.

show all references

References:

[1]	O. Axelsson and G. Lindskog, On the rate of convergence of the preconditioned conjugate gradient method,, Numer. Math., 48 (1986), 499. doi: 10.1007/BF01389448.
[2]	Z. Z. Bai and G. Q. Li, Restrictively preconditioned conjugate gradient methods for systems of linear equations,, IMA J. Numer. Anal., 23 (2003), 561. doi: 10.1093/imanum/23.4.561.
[3]	J. H. Bramble and J. E. Pasciak, A preconditioning technique for indefinite systems resulting from mixed approximations of ellipstic problems,, Math. Comp., 50 (1988), 1. doi: 10.1090/S0025-5718-1988-0917816-8.
[4]	M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems,, Acta Numer., 14 (2005), 1. doi: 10.1017/S0962492904000212.
[5]	M. Benzi and V. Simoncini, On the eigenvalues of a class of saddle point matrices,, Numer. Math., 103 (2006), 173. doi: 10.1007/s00211-006-0679-9.
[6]	H. S. Dollar, N. I. M Gould, M. Stoll and A. J. Wathen, Preconditioning saddle-point systems with applications in optimization,, SIAM J. Sci. Comput., 32 (2010), 249. doi: 10.1137/080727129.
[7]	H. C. Elman, D. J. Silvester and Andrew J. Wathen, "Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics,", in, (2005).
[8]	H. C. Elman, A. Ramage and D. J. Silvester, Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow,, ACM Trans. Math. Softw., 33 (2007), 251.
[9]	G. N. Gatica and N. Heuer, Conjugate gradient method for dual-dual mixed formulations,, Math. Comp., 71 (2002), 1455. doi: 10.1090/S0025-5718-01-01394-1.
[10]	M. R. Hestenes and E. Stiefel, Methods of conjugate gradient for solving linear systems,, J. Res. Nat. Bur. Stand., 49 (1952), 409.
[11]	A. Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term,, SIAM J. Sci. Comput., 19 (1998), 172. doi: 10.1137/S1064827596303624.
[12]	J. Liesen and B. N. Parlett, On nonsymmetric saddle point matrices that allow conjugate gradient iterations,, Numer. Math., 108 (2008), 605. doi: 10.1007/s00211-007-0131-9.
[13]	J. A. Meijerink and H. A. Van der vorst, An iterative solution method for linear equation systems of which the coefficient matrix is symmetric M-matrix,, Math. Comp., 31 (1977), 148.
[14]	X. F. Peng, W. Li and S. H. Xiang, New preconditioners based on symmetric-triangular decomposition for saddle point problems,, Computing, 93 (2011), 27. doi: 10.1007/s00607-011-0150-3.
[15]	J. Schöberl and W. Zulehner, Symmetric indefinite preconditioners for saddle point problems with applications to pde-constrained optimization problems,, SIAM J. Matrix Anal. Appl., 29 (2007), 752. doi: 10.1137/060660977.
[16]	M. Stoll and A. J. Wathen, Combination preconditioning and the Bramble-Pasciak⁺ preconditioner,, SIAM J. Matrix Anal. Appl., 30 (2008), 582. doi: 10.1137/070688961.
[17]	X. N. Wu, G. H. Golub, J. A. Cuminato and J. Y. Yuan, Symmetric-triangular decomposition and its applications - Part Π: Preconditioners for indefinite systems,, BIT Numer. Math., 48 (2008), 139. doi: 10.1007/s10543-008-0160-5.
[18]	W. Zulehner, Analysis of iterative methods for saddle point problems: A unified approach,, Math. Comp., 71 (2002), 479. doi: 10.1090/S0025-5718-01-01324-2.

[1]	C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193
[2]	Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[3]	El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[4]	Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[5]	Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507
[6]	Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial & Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739
[7]	Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems & Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195
[8]	Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025
[9]	Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395
[10]	Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019013
[11]	Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems & Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815
[12]	Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[13]	Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199
[14]	Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[15]	Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial & Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565
[16]	Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038
[17]	Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[18]	Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2018149
[19]	Maurizio Grasselli, Morgan Pierre. Convergence to equilibrium of solutions of the backward Euler scheme for asymptotically autonomous second-order gradient-like systems. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2393-2416. doi: 10.3934/cpaa.2012.11.2393
[20]	Fabio Camilli, Claudio Marchi. On the convergence rate in multiscale homogenization of fully nonlinear elliptic problems. Networks & Heterogeneous Media, 2011, 6 (1) : 61-75. doi: 10.3934/nhm.2011.6.61

Impact Factor:

American Institute of Mathematical Sciences