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 and 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.

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

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

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

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

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

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

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

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

[10]

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

[10]

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

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

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

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

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

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

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

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

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

[1]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021150
[2]

Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022008
[3]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (1) : 157-172. doi: 10.3934/jimo.2020147
[4]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial and Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193
[5]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[6]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[7]

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

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

Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507
[10]

Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial and Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739
[11]

Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems and Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195
[12]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025
[13]

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

Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395
[15]

Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems and Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815
[16]

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[17]

Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial and Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565
[18]

Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial and Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199
[19]

Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic and Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[20]

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 and Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy