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.  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.  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.  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.  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.  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.  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, (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.   Google Scholar

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

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

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

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

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

[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.  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.   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.  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.  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.  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.  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.  doi: 10.1090/S0025-5718-01-01324-2.  Google Scholar

[1]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[2]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020178
[3]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139
[4]

Elena Nozdrinova, Olga Pochinka. Solution of the 33rd Palis-Pugh problem for gradient-like diffeomorphisms of a two-dimensional sphere. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1101-1131. doi: 10.3934/dcds.2020311
[5]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304
[6]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[7]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345
[8]

Larissa Fardigola, Kateryna Khalina. Controllability problems for the heat equation on a half-axis with a bounded control in the Neumann boundary condition. Mathematical Control & Related Fields, 2021, 11 (1) : 211-236. doi: 10.3934/mcrf.2020034
[9]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018
[10]

Manxue You, Shengjie Li. Perturbation of Image and conjugate duality for vector optimization. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020176
[11]

Waixiang Cao, Lueling Jia, Zhimin Zhang. A $ C^1 $ Petrov-Galerkin method and Gauss collocation method for 1D general elliptic problems and superconvergence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 81-105. doi: 10.3934/dcdsb.2020327
[12]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127
[13]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054
[14]

Riccarda Rossi, Ulisse Stefanelli, Marita Thomas. Rate-independent evolution of sets. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 89-119. doi: 10.3934/dcdss.2020304
[15]

Héctor Barge. Čech cohomology, homoclinic trajectories and robustness of non-saddle sets. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020381
[16]

Joel Kübler, Tobias Weth. Spectral asymptotics of radial solutions and nonradial bifurcation for the Hénon equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3629-3656. doi: 10.3934/dcds.2020032
[17]

Bopeng Rao, Zhuangyi Liu. A spectral approach to the indirect boundary control of a system of weakly coupled wave equations. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 399-414. doi: 10.3934/dcds.2009.23.399
[18]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[19]

Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016
[20]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences