American Institute of Mathematical Sciences

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

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

Xiao-Fei Peng 1, and  Wen Li 2,

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

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-523. doi: 10.1007/BF01389448.  Google Scholar

[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-580. doi: 10.1093/imanum/23.4.561.  Google Scholar

[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-17. doi: 10.1090/S0025-5718-1988-0917816-8.  Google Scholar

[4]

M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), 1-137. doi: 10.1017/S0962492904000212.  Google Scholar

[5]

M. Benzi and V. Simoncini, On the eigenvalues of a class of saddle point matrices, Numer. Math., 103 (2006), 173-196. doi: 10.1007/s00211-006-0679-9.  Google Scholar

[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-270. doi: 10.1137/080727129.  Google Scholar

[7]

H. C. Elman, D. J. Silvester and Andrew J. Wathen, "Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics," in "Numerical Mathematics and Scientific Computation," Oxford University Press, Oxford, 2005. Google Scholar

[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-268. Google Scholar

[9]

G. N. Gatica and N. Heuer, Conjugate gradient method for dual-dual mixed formulations, Math. Comp., 71 (2002), 1455-1472. doi: 10.1090/S0025-5718-01-01394-1.  Google Scholar

[10]

M. R. Hestenes and E. Stiefel, Methods of conjugate gradient for solving linear systems, J. Res. Nat. Bur. Stand., 49 (1952), 409-436.  Google Scholar

[11]

A. Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term, SIAM J. Sci. Comput., 19 (1998), 172-184. doi: 10.1137/S1064827596303624.  Google Scholar

[12]

J. Liesen and B. N. Parlett, On nonsymmetric saddle point matrices that allow conjugate gradient iterations, Numer. Math., 108 (2008), 605-624. doi: 10.1007/s00211-007-0131-9.  Google Scholar

[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-162.  Google Scholar

[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-46. doi: 10.1007/s00607-011-0150-3.  Google Scholar

[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-773. doi: 10.1137/060660977.  Google Scholar

[16]

M. Stoll and A. J. Wathen, Combination preconditioning and the Bramble-Pasciak+ preconditioner, SIAM J. Matrix Anal. Appl., 30 (2008), 582-608. doi: 10.1137/070688961.  Google Scholar

[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-162. doi: 10.1007/s10543-008-0160-5.  Google Scholar

[18]

W. Zulehner, Analysis of iterative methods for saddle point problems: A unified approach, Math. Comp., 71 (2002), 479-505. doi: 10.1090/S0025-5718-01-01324-2.  Google Scholar

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-523. doi: 10.1007/BF01389448.  Google Scholar

[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-580. doi: 10.1093/imanum/23.4.561.  Google Scholar

[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-17. doi: 10.1090/S0025-5718-1988-0917816-8.  Google Scholar

[4]

M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), 1-137. doi: 10.1017/S0962492904000212.  Google Scholar

[5]

M. Benzi and V. Simoncini, On the eigenvalues of a class of saddle point matrices, Numer. Math., 103 (2006), 173-196. doi: 10.1007/s00211-006-0679-9.  Google Scholar

[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-270. doi: 10.1137/080727129.  Google Scholar

[7]

H. C. Elman, D. J. Silvester and Andrew J. Wathen, "Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics," in "Numerical Mathematics and Scientific Computation," Oxford University Press, Oxford, 2005. Google Scholar

[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-268. Google Scholar

[9]

G. N. Gatica and N. Heuer, Conjugate gradient method for dual-dual mixed formulations, Math. Comp., 71 (2002), 1455-1472. doi: 10.1090/S0025-5718-01-01394-1.  Google Scholar

[10]

M. R. Hestenes and E. Stiefel, Methods of conjugate gradient for solving linear systems, J. Res. Nat. Bur. Stand., 49 (1952), 409-436.  Google Scholar

[11]

A. Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term, SIAM J. Sci. Comput., 19 (1998), 172-184. doi: 10.1137/S1064827596303624.  Google Scholar

[12]

J. Liesen and B. N. Parlett, On nonsymmetric saddle point matrices that allow conjugate gradient iterations, Numer. Math., 108 (2008), 605-624. doi: 10.1007/s00211-007-0131-9.  Google Scholar

[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-162.  Google Scholar

[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-46. doi: 10.1007/s00607-011-0150-3.  Google Scholar

[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-773. doi: 10.1137/060660977.  Google Scholar

[16]

M. Stoll and A. J. Wathen, Combination preconditioning and the Bramble-Pasciak+ preconditioner, SIAM J. Matrix Anal. Appl., 30 (2008), 582-608. doi: 10.1137/070688961.  Google Scholar

[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-162. doi: 10.1007/s10543-008-0160-5.  Google Scholar

[18]

W. Zulehner, Analysis of iterative methods for saddle point problems: A unified approach, Math. Comp., 71 (2002), 479-505. doi: 10.1090/S0025-5718-01-01324-2.  Google Scholar

[1]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020147
[2]

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
[3]

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
[4]

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
[5]

Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[6]

Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042
[7]

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
[8]

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
[9]

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
[10]

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
[11]

Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1503-1518. doi: 10.3934/jimo.2019013
[12]

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
[13]

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
[14]

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
[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]

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
[17]

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
[18]

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
[19]

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
[20]

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, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

 Impact Factor: 

Tools

Metrics

  • PDF downloads (46)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences