A parameterized shift-splitting preconditioner for saddle point problems

Li-Tao Zhang; Chao-Qian Li; Yao-Tang Li; Li-Tao Zhang; Chao-Qian Li; Yao-Tang Li

doi:10.3934/mbe.2019048

Mathematical Biosciences and Engineering

2019, Volume 16, Issue 2: 1021-1033. doi: 10.3934/mbe.2019048

Previous Article Next Article

Research article Special Issues

A parameterized shift-splitting preconditioner for saddle point problems

1.
College of Science, Zhengzhou University of Aeronautics, Zhengzhou, Henan, 450015, P. R. China
2.
College of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan, 453007, P. R. China
3.
Henan province Synergy Innovation Center of Aviation economic development, Zhengzhou, Henan, 450015, P. R. China
4.
School of Mathematics and Statistics, Yunnan University, Kunming, Yunnan, 650091, P. R. China

Received: 06 November 2018 Accepted: 31 December 2018 Published: 30 January 2019

Recently, Chen and Ma [A generalized shift-splitting preconditioner for saddle point problems, Applied Mathematics Letters, 43 (2015) 49-55] introduced a generalized shift-splitting preconditioner for saddle point problems with symmetric positive definite (1, 1)-block. In this paper, I establish a parameterized shift-splitting preconditioner for solving the large sparse augmented systems of linear equations. Furthermore, the preconditioner is based on the parameterized shift-splitting of the saddle point matrix, resulting in an unconditional convergent fixed-point iteration, which has the intersection with the generalized shift-splitting preconditioner. In final, one example is provided to confirm the effectiveness.
- saddle point problem,
- parameterized shift-splitting,
- convergence,
- preconditioner,
- Eigenvalue
Citation: Li-Tao Zhang, Chao-Qian Li, Yao-Tang Li. A parameterized shift-splitting preconditioner for saddle point problems[J]. Mathematical Biosciences and Engineering, 2019, 16(2): 1021-1033. doi: 10.3934/mbe.2019048

Related Papers:

Abstract

Recently, Chen and Ma [A generalized shift-splitting preconditioner for saddle point problems, Applied Mathematics Letters, 43 (2015) 49-55] introduced a generalized shift-splitting preconditioner for saddle point problems with symmetric positive definite (1, 1)-block. In this paper, I establish a parameterized shift-splitting preconditioner for solving the large sparse augmented systems of linear equations. Furthermore, the preconditioner is based on the parameterized shift-splitting of the saddle point matrix, resulting in an unconditional convergent fixed-point iteration, which has the intersection with the generalized shift-splitting preconditioner. In final, one example is provided to confirm the effectiveness.

References

[1]	M. Arioli, I. S. Du and P. P. M. de Rijk, On the augmented system approach to sparse leastsquares problems, Numer. Math., 55 (1989), 667–684.
[2]	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.
[3]	Z. Z. Bai and Z. Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl., 428 (2008), 2900–2932.
[4]	Z. Z. Bai and X. Yang, On HSS-based iteration methods for weakly nonlinear systems, Appl. Numer. Math., 59 (2009), 2923–2936.
[5]	Z. Z. Bai, G. H. Golub and K. N. Michael, On inexact hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, Linear Algebra Appl., 284 (2008), 413–440.
[6]	Z. Z. Bai, Several splittings for non-Hermitian linear systems, Science in China, Series A: Math., 51 (2008), 1339–1348.
[7]	Z. Z. Bai, G. H. Golub, L. Z. Lu and J. F. Yin, Block-Triangular and skew-Hermitian splitting methods for positive definite linear systems, SIAM J. Sci. Comput., 26 (2005), 844–863.
[8]	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. A., 24 (2003), 603–626.
[9]	Z. Z. Bai, G. H. Golub and M. K. Ng, On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iteration. Available from: http://www.sccm.stanford.edu/wrap/pubtech. html.
[10]	Z. Z. Bai, G. H. Golub and C. K. Li, Optimal parameter in Hermitian and skew-Hermitian splitting method for certain twoby- two block matrices, SIAM J. Sci. Comput., 28 (2006), 28:583–603.
[11]	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.
[12]	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.
[13]	Z. Z. Bai and M. K. Ng, On inexact preconditioners for nonsymmetric matrices, SIAM J. Sci. Comput., 26 (2005), 1710–1724.
[14]	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.
[15]	Z. Z. Bai, Optimal parameters in the HSS-like methods for saddle-point problems, Numer. Linear Algebra Appl., 16 (2009), 447–479.
[16]	Z. Z. Bai, J. F. Yin and Y. F. Su, A shift-splitting preconditioner for non-Hermitian positive definite matrices, J. Comput. Math., 24 (2006), 539–552.
[17]	Z. Z. Bai, G. H. Golub and J. Y. Pan, Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Technical Report SCCM-02-12, Scientific Computing and Computational Mathematics Program, Department of Computer Science, Stanford University, Stanford, CA, 2002.
[18]	Z. Z. Bai, M. Benzi and F. Chen, Modified HSS iteration methods for a class of complex symmetric linear systems, Comput., 87 (2010), 93–111.
[19]	Y. Cao, J. Du and Q. Niu, Shift-splitting preconditioners for saddle point problems, J. Comput. Appl. Math., 272 (2014), 239–250.
[20]	Y. Cao, L. Q. Yao and M. Q. Jiang, A modified dimensional split preconditioner for generalized saddle point problems, J. Comput. Appl. Math., 250 (2013), 70–82.
[21]	Y. Cao, L. Q. Yao, M. Q. Jiang and Q. Niu, A relaxed HSS preconditioner for saddle point problems from meshfree discretization, J. Comput. Math., 31 (2013), 398–421.
[22]	C. R. Chen and C. F. Ma, A generalized shift-splitting preconditioner for saddle point problems, Appl. Math. Lett., 43 (2015), 49–55.
[23]	F. Chen and Y. L. Jiang, A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput., 206 (2008), 765–771.
[24]	L. B. Cui, C. Chen, W. Li and M.K. Ng, An eigenvalue problem for even order tensors with its applications, Linear Multilinear Algebra, 64 (2016), 602–621.
[25]	L. B. Cui, W. Li and M. K. Ng, Primitive tensors and directed hypergraphs, Linear Algebra Appl., 471 (2015), 96–108.
[26]	L. B. Cui, C. X. Li and S. L. Wu, The relaxation convergence of multisplitting AOR method for linear complementarity problem, Linear Multilinear Algebra, DOI: 10.1080/03081087.2018.1511680.
[27]	L. B. Cui and Y. S. Song, On the uniqueness of the positive Z-eigenvector for nonnegative tensors, J. Comput. Appl. Math., 352 (2019), 72C78.
[28]	M. T. Darvishi and P. Hessari, Symmetric SOR method for augmented systems, Appl. Math. Comput., 183 (2006), 409–415.
[29]	H. Elman and D. Silvester, Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations, SIAM J. Sci. Comput., 17 (1996), 33–46.
[30]	H. Elman and G. H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31 (1994), 1645–1661.
[31]	B. Fischer, A. Ramage, D. J. Silvester and A. J.Wathen, Minimum residual methods for augmented systems, BIT, 38 (1998), 527–543.
[32]	G. H. Golub, X. Wu and J. Y. Yuan, SOR-like methods for augmented systems, BIT, 55 (2001), 71–85.
[33]	M. Q. Jiang and Y. Cao, On local Hermitian skew-Hermitian splitting iteration methods for generalized saddle point problems, J. Comput. Appl. Math., 231 (2009), 973–982.
[34]	X.Y. Li, L. Gao, Q. K. Pan, L. Wan and K. M. Chao, An e ective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop, IEEE Transactions on Systems, Man and Cybernetics: Systems, 2018, DOI 10.1109/TSMC.2018.2881686.
[35]	X. Y. Li, C. Lu, L. Gao, S. Q. Xiao and L.Wen, An E ective Multi-Objective Algorithm for Energy Efficient Scheduling in a Real-Life Welding Shop, IEEE T. Ind. Inform., 14 (2018), 5400–5409.
[36]	X. Y. Li and L. Gao, An E ective Hybrid Genetic Algorithm and Tabu Search for Flexible Job Shop Scheduling Problem, Int. J. Prod. Econ., 174 (2016), 93–110.
[37]	X. F. Peng and W. Li, On unsymmetric block overrelaxation-type methods for saddle point, Appl. Math. Comput., 203 (2008), 660–671.
[38]	C. H. Santos, B. P. B. Silva and J. Y. Yuan, Block SOR methods for rank deficient least squares problems, J. Comput. Appl. Math., 100 (1998), 1–9.
[39]	H. A. Van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge, UK, 2003.
[40]	L. Wang and Z. Z. Bai, Convergence conditions for splitting iteration methods for non-Hermitian linear systems, Linear Algebra Appl., 428 (2008), 453–468.
[41]	S. Wright, Stability of augmented system factorizations in interior-point methods, SIAM J. Matrix Anal. Appl., 18 (1997), 191–222.
[42]	S. L.Wu, T. Z. Huang and X. L. Zhao, A modified SSOR iterative method for augmented systems, J. Comput. Appl. Math., 228 (2009), 424–433.
[43]	D. M. Young, Iteratin Solution for Large Systems, Academic Press, New York, 1971.
[44]	J. Y. Yuan, Numerical methods for generalized least squares problems, J. Comput. Appl. Math., 66 (1996), 571–584.
[45]	J. Y. Yuan and A. N. Iusem, Preconditioned conjugate gradient method for generalized least squares problems, J. Comput. Appl. Math., 71 (1996), 287–297.
[46]	G. F. Zhang and Q. H. Lu, On generalized symmetric SOR method for augmented systems, J. Comput. Appl. Math., 1 (2008), 51–58.
[47]	L. T. Zhang, A new preconditioner for generalized saddle matrices with highly singular(1,1) blocks, Int. J. Comput. Math., 91 (2014), 2091–2101.
[48]	L. T. Zhang, T. Z. Huang, S. H. Cheng and Y. P. Wang, Convergence of a generalized MSSOR method for augmented systems, J. Comput. Appl. Math., 236 (2012), 1841–1850.
[49]	B. Zheng, Z. Z. Bai and X. Yang, On semi-convergence of parameterized Uzawa methods for singular saddle point problems, Linear Algebra Appl., 431 (2009), 808–817.
[50]	Y. Z. Zhou, W. C. Yi, L. Gao and X. Y. Li, Adaptive di erential evolution with sorting crossover rate for continuous optimization problems, IEEE T. Cybernetics, 47 (2017), 2742–2753.

Reader Comments

Your name:*

Email:*
© 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)