JCM
Journal of Computational Mathematics ›› 2013, Vol. 31 ›› Issue (4): 398-421.DOI: 10.4208/jcm.1304-m4209

Previous Articles     Next Articles

A RELAXED HSS PRECONDITIONER FOR SADDLE POINT PROBLEMS FROM MESHFREE DISCRETIZATION

Yang Cao, Linquan Yao, Meiqun Jiang, Qiang Niu   

  1. 1. School of Transportation, Nantong University, Nantong 226019, China;
    2. School of Urban Rail Transportation, Soochow University, Suzhou 215006, China;
    3. School of Mathematical Sciences, Soochow University, Suzhou, 215006, China;
    4. Mathematics and Physics Center, Xi'an Jiaotong-Liverpool University, Suzhou 215123, China
  • Received:2012-07-05 Revised:2013-04-16 Online:2013-07-15 Published:2013-07-09
  • Supported by:

    This work is supported by the National Natural Science Foundation of China(11172192) and the National Natural Science Pre-Research Foundation of Soochow University (SDY2011B01).

PDF ( 97 ) Cited

Yang Cao, Linquan Yao, Meiqun Jiang, Qiang Niu. A RELAXED HSS PRECONDITIONER FOR SADDLE POINT PROBLEMS FROM MESHFREE DISCRETIZATION[J]. Journal of Computational Mathematics, 2013, 31(4): 398-421.

In this paper, a relaxed Hermitian and skew-Hermitian splitting (RHSS) preconditioner is proposed for saddle point problems from the element-free Galerkin (EFG) discretization method. The EFG method is one of the most widely used meshfree methods for solving partial differential equations. The RHSS preconditioner is constructed much closer to the coefficient matrix than the well-known HSS preconditioner, resulting in a RHSS fixed-point iteration. Convergence of the RHSS iteration is analyzed and an optimal parameter, which minimizes the spectral radius of the iteration matrix is described. Using the RHSS preconditioner to accelerate the convergence of some Krylov subspace methods (like GMRES) is also studied. Theoretical analyses show that the eigenvalues of the RHSS preconditioned matrix are real and located in a positive interval. Eigenvector distribution and an upper bound of the degree of the minimal polynomial of the preconditioned matrix are obtained. A practical parameter is suggested in implementing the RHSS preconditioner. Finally, some numerical experiments are illustrated to show the effectiveness of the new preconditioner.
Key words: Meshfree method, Element-free Galerkin method, Saddle point problems, Preconditioning, HSS preconditioner, Krylov subspace method

CLC Number: 

[1] Z. -Z. Bai, Optimal parameters in the HSS-like methods for saddle point problems, Numer. Linear Algebra Appl., 16 (2009), 447-479.

[2] Z. -Z. Bai and G. H. Golub, Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27 (2007), 1-23.

[3] Z. -Z. Bai, G. H. Golub, C. -K. Li, Convergence properties of preconditioned Hermitian and skew- Hermitian splitting methods for non-Hermitian positive semidefinite matrices, Math. Comput., 76 (2007), 287-298.

[4] Z. -Z. Bai, G. H. Golub and M. K. Ng, Hermitian and skew-Hermitian splitting methods for non- Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24 (2003), 603-626.

[5] Z. -Z. Bai, G. H. Golub and M. K. Ng, On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 14 (2007), 319-335.

[6] Z. -Z. Bai, G. H. Golub and J. -Y. Pan, Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., 98 (2004), 1-32.

[7] Z. -Z. Bai and M. K. Ng, On inexact preconditioners for nonsymmetric matrices, SIAM J. Sci. Comput., 26 (2005), 1710-1724.

[8] Z. -Z. Bai, M. K. Ng and Z. -Q. Wang, Constraint preconditioners for symmetric indefinite matrices, SIAM J. Matrix Anal. Appl., 31 (2009), 410-433.

[9] Z. -Z. Bai, B. N. Parlett and Z. -Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102 (2005) 1-38.

[10] Z. -Z. Bai and Z. -Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl., 428 (2008), 2900-2932.

[11] T. Belytschko, Y. Y. Lu and L. Gu, Element-free Galerkin methods, Int. J. Numer. Meth. Engrg., 37 (1994), 229-256.

[12] M. Benzi, M. J. Gander and G. H. Golub, Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems, BIT, 43 (2003), 881-900.

[13] M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), 20-41.

[14] M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), 1-137.

[15] M. Benzi, and X. -P. Guo, A dimensional split preconditioner for Stokes and linearized Navier- Stokes equations, Appl. Numer. Math., 61 (2011), 66-76.

[16] M. Benzi, M. K. Ng, Q. Niu and Z. Wang, A relaxed dimensional fractorization preconditioner for the incompressible Navier-Stokes equations, J. Comput. Phys., 230 (2011), 6185-6202.

[17] S. L. Borne, S. Oliveira and F. Yang, H-matrix preconditioners for symmetric saddle-point systems from meshfree discretization, Numer. Linear Algebra Appl., 15 (2008), 911-924.

[18] Y. Cao, M. -Q. Jiang and L. -Q. Yao, New choices of preconditioning matrices for generalized inexact parameterized iterative methods, J. Comput. Appl. Math., 235 (2010), 263-269.

[19] Y. Cao, M. -Q. Jiang and Y. -L. Zheng, A splitting preconditioner for saddle point problems, Numer. Linear Algebra Appl., 18 (2011), 875-895.

[20] Y. Cao, M. -Q. Jiang and Y. -L. Zheng, A note on the positive stable block triangular preconditioner for generalized saddle point problems, Appl. Math. Comput., 218 (2012) 11075-11082.

[21] Y. Cao, W. -W. Tan and M. -Q. Jiang, A generalization of the positive-definite and skew-Hermitian splitting iteration, Numer. Algebra Control Optimization, 2 (2012), 811-821.

[22] Y. Cao, L. -Q. Yao and Y. Yin, New treatment of essential boundary conditions in EFG method by coupling with RPIM, Acta Mech. Solida Sinica, To appear.

[23] M. -Q. Jiang and Y. Cao, On local Hermitian and skew-Hermitian splitting iteration methods for generalized saddle point problems, J. Comput. Appl. Math., 231 (2009), 973-982.

[24] M. -Q. Jiang, Y. Cao and L. -Q. Yao, On parameterized block triangular preconditioners for generalized saddle point problems, Appl. Math. Comput., 216 (2010), 1777-1789.

[25] C. Keller, N. I. M. Gould and A. J. Wathen, Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21 (2000), 1300-1317.

[26] K. H. Leem, S. Oliveira and D. E. Stewart, Algebraic multigrid (AMG) for saddle point systems from meshfree discretizations, Numer. Linear Algebra Appl., 11 (2004) 293-308.

[27] G. -R. Liu and Y. -T. Gu, An introduction to meshfree methods and their programming, Netherland: Springer; 2005.

[28] F. Z. Louaï, N. Naït-Saïd and S. Drid, Implementation of an efficient element-free Galerkin method for electromagnetic computation, Eng. Anal. Boundary Elem., 31 (2007), 191-199.

[29] Y. Saad, Iterative Methods for Sparse Linear Systems(2nd edn), SIAM: Philadelphia, 2003.

[30] V. Simoncini and M. Benzi, Spectral properties of the Hermitian and skew-Hermitian splitting preconditioner for saddle point problems, SIAM J. Numer. Anal., 27 (2007), 1-23.

[31] G. Ventura, An augmented Lagrangian approach to essential boundary conditions in meshless methods, Int. J. Numer. Meth. Engng., 53 (2002), 825-842.

[32] H. Zheng and J. -L. Li, A practical solution for KKT systems, Numer. Algor., 46 (2007) 105-119.

[33] T. Zhu and S. N. Atluri, A modified collocation method and a penalty formulation for enforcing the essential boundary conditions in the element free Galerkin method, Comput. Mech., 21 (1998), 211-222.
[1] Davod Hezari, Vahid Edalatpour, Hadi Feyzollahzadeh, Davod Khojasteh Salkuyeh. ON THE GENERALIZED DETERIORATED POSITIVE SEMI-DEFINITE AND SKEW-HERMITIAN SPLITTING PRECONDITIONER [J]. Journal of Computational Mathematics, 2019, 37(1): 18-32.
[2] Yang Cao, Zhiru Ren, Linquan Yao. IMPROVED RELAXED POSITIVE-DEFINITE AND SKEW-HERMITIAN SPLITTING PRECONDITIONERS FOR SADDLE POINT PROBLEMS [J]. Journal of Computational Mathematics, 2019, 37(1): 95-111.
[3] Yunfeng Cai, Zhaojun Bai, John E. Pask, N. Sukumar. CONVERGENCE ANALYSIS OF A LOCALLY ACCELERATED PRECONDITIONED STEEPEST DESCENT METHOD FOR HERMITIAN-DEFINITE GENERALIZED EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2018, 36(5): 739-760.
[4] Xinhui Shao, Chen Li, Tie Zhang, Changjun Li. A MODIFIED PRECONDITIONER FOR PARAMETERIZED INEXACT UZAWA METHOD FOR INDEFINITE SADDLE POINT PROBLEMS [J]. Journal of Computational Mathematics, 2018, 36(4): 579-590.
[5] Yongxin Dong, Chuanqing Gu. ON PMHSS ITERATION METHODS FOR CONTINUOUS SYLVESTER EQUATIONS [J]. Journal of Computational Mathematics, 2017, 35(5): 600-619.
[6] Minli Zeng, Guofeng Zhang, Zhong Zheng. GENERALIZED AUGMENTED LAGRANGIAN-SOR ITERATION METHOD FOR SADDLE-POINT SYSTEMS ARISING FROM DISTRIBUTED CONTROL PROBLEMS [J]. Journal of Computational Mathematics, 2016, 34(2): 174-185.
[7] Xin He, Maya Neytcheva, Cornelis Vuik. ON PRECONDITIONING OF INCOMPRESSIBLE NON-NEWTONIAN FLOW PROBLEMS [J]. Journal of Computational Mathematics, 2015, 33(1): 33-58.
[8] Séraphin M. Mefire. STATIC REGIME IMAGING OF LOCATIONS OF CERTAIN 3D ELECTROMAGNETIC IMPERFECTIONS FROM A BOUNDARY PERTURBATION FORMULA [J]. Journal of Computational Mathematics, 2014, 32(4): 412-441.
[9] Qingbing Liu, Guoliang Chen, Caiqin Song. PRECONDITIONED HSS-LIKE ITERATIVE METHOD FOR SADDLE POINT PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 442-455.
[10] Tatiana S. Martynova. ON AUGMENTED LAGRANGIAN METHODS FOR SADDLE-POINT LINEAR SYSTEMS WITH SINGULAR OR SEMIDEFINITE (1, 1) BLOCKS [J]. Journal of Computational Mathematics, 2014, 32(3): 297-305.
[11] Minli Zeng, Guofeng Zhang. A NEW PRECONDITIONING STRATEGY FOR SOLVING A CLASS OF TIME-DEPENDENT PDE-CONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(3): 215-232.
[12] Hongtao Fan, Bing Zheng. THE GENERALIZED LOCAL HERMITIAN AND SKEW-HERMITIAN SPLITTING ITERATION METHODS FOR THE NON-HERMITIAN GENERALIZED SADDLE POINT PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(3): 312-331.
[13] Guofeng Zhang, Zhong Zheng. BLOCK-SYMMETRIC AND BLOCK-LOWER-TRIANGULAR PRECONDITIONERS FOR PDE-CONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2013, 31(4): 370-381.
[14] F. Alouges, J. Bourguignon-Mirebeau, D. P. Levadoux. A SIMPLE PRECONDITIONED DOMAIN DECOMPOSITION METHOD FOR ELECTROMAGNETIC SCATTERING PROBLEMS [J]. Journal of Computational Mathematics, 2013, 31(1): 1-21.
[15] Xin He, Maya Neytcheva. PRECONDITIONING THE INCOMPRESSIBLE NAVIER-STOKESEQUATIONS WITH VARIABLE VISCOSITY [J]. Journal of Computational Mathematics, 2012, 30(5): 461-482.
Viewed
Full text


Abstract

Journal of Computational Mathematics
Contact Us
Editor-in-Chief: Zhiming Chen
Electronic: 1991-7139
ISSN Print: 0254-9409
Issues: 6 / year
Institute of Computational Mathematics and Scientific/ Engineering Computing
Chinese Academy of Sciences
Zhongguancun East Rd. No.55
Beijing 100190, China
Phone: 86-10-82541418
Email: jcm@lsec.cc.ac.cn
×

扫码分享

京公网安备11010802040203号      京ICP备05002806号-10　　The journal is sponsored by ICMSEC　　Copyrights © ICMSEC