American Institute of Mathematical Sciences

Advanced
2012, 2(4): 811-821. doi: 10.3934/naco.2012.2.811

A generalization of the positive-definite and skew-Hermitian splitting iteration

Yang Cao 1, , Wei- Wei Tan 2, and  Mei-Qun Jiang 2,

1. 

School of Transportation, Nantong University, Nantong, 226019, China
2. 

School of Mathematical Sciences, Soochow University, Suzhou, 215006, China, China

Received  December 2011 Revised  September 2012 Published  November 2012

In this paper, a generalization of the positive-definite and skew-Hermitian splitting (GPSS) iteration is considered for solving non-Hermitian and positive definite systems of linear equations. Theoretical analysis shows that the GPSS method converges unconditionally to the exact solution of the linear system, with the upper bound of its convergence factor dependent only on the spectrum of the positive-definite splitting matrices. In some situations, this new scheme can outperform the Hermitian and skew-Hermitian splitting (HSS) method, the positive-definite and skew-Hermitian splitting (PSS) method, and the generalized HSS method (GHSS) and can be used as an efficient preconditioner. Numerical experiments using discretization of convection-diffusion-reaction equations demonstrate the effectiveness of the new method.
Keywords: preconditioning., PSS iteration, HSS iteration, Positive-definite matrix.
Mathematics Subject Classification: 65F10, 65N2.
Citation: Yang Cao, Wei- Wei Tan, Mei-Qun Jiang. A generalization of the positive-definite and skew-Hermitian splitting iteration. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 811-821. doi: 10.3934/naco.2012.2.811
References:
[1]

Z.-Z. Bai, Optimal parameters in the HSS-like methods for saddle point problems, Numer. Linear Algebra Appl., 16 (2009), 447-479. doi: 10.1002/nla.626.  Google Scholar

[2]

Z.-Z. Bai, On semi-convergence of Hermitian and skew-Hermitian splitting methods for singular linear systems, Computing, 89 (2010), 171-197. doi: 10.1007/s00607-010-0101-.  Google Scholar

[3]

Z.-Z. Bai, M. Benzi and F. Chen, Modified HSS iteration methods for a class of complex symmetric linear systems, Computing, 87 (2010), 93-111. doi: 10.1007/s00607-010-0077-0.  Google Scholar

[4]

Z.-Z. Bai, M. Benzi and F. Chen, On preconditioned MHSS iteration methods for complex symmetric linear systems, Numer. Algor., 56 (2011), 297-317. doi: 10.1007/s11075-010-9441-6.  Google Scholar

[5]

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

[6]

Z.-Z. Bai, G. H. Golub and C.-K. Li, Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices, SIAM J. Sci. Comput., 28 (2006), 583-603. doi: 10.1137/050623644.  Google Scholar

[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., 23 (2005), 844-863. doi: 10.1137/S1064827503428114.  Google Scholar

[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. Appl., 24 (2003), 603-626. doi: 10.1137/S0895479801395458.  Google Scholar

[9]

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. doi: 10.1002/nla.517.  Google Scholar

[10]

Z.-Z. Bai, G. H. Golub and M. K. Ng, On inexact Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, Linear Algebra Appl., 428 (2008), 413-440. doi: 10.1016/j.laa.2007.02.018.  Google Scholar

[11]

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

[12]

M. Benzi, A generalization of the Hermitian and skew-Hermitian splitting iteration, SIAM J. Matrix Anal. Appl., 31 (2009), 360-374. doi: 10.1137/080723181.  Google Scholar

[13]

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. doi: 10.1023/B:BITN.0000014548.26616.65.  Google Scholar

[14]

M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), 20-41. doi: 10.1137/S0895479802417106.  Google Scholar

[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. doi: 10.1016/j.apnum.2010.08.005.  Google Scholar

[16]

L. C. Chan, M. K. Ng and N. K. Tsing, Spectral Analysis for HSS Preconditioners, Numer. Math. Theor. Meth. Appl., 1 (2008), 57-77.  Google Scholar

[17]

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. doi: 10.1016/j.cam.2009.05.012.  Google Scholar

[18]

L. Li, T.-Z. Huang and X.-P. Liu, Asymmetric Hermitian and skew-Hermitian splitting methods for positive definite linear systems, Comput. Math. Appl., 54 (2007), 147-159. doi: 10.1016/j.camwa.2006.12.024.  Google Scholar

[19]

J.-Y. Pan, M. K. Ng and Z.-Z. Bai, New preconditioners for saddle point problems, Appl. Math. Comput., 172 (2006), 762-771. doi: 10.1016/j.amc.2004.11.016.  Google Scholar

[20]

D. W. Peaceman and H. H. Rachford Jr., The numerical solution of parabolic and elliptic differential equations, J. Soc. Indust. Appl.Math., 3 (1955), 28-41. doi: 10.1137/0103003.  Google Scholar

[21]

Y. Saad, "Iterative Methods for Sparse Linear Systems," 2nd edition, SIAM, Philadelphia, 2003. doi: 10.1137/1.9780898718003.  Google Scholar

[22]

A.-L Yang, J. An and Y.-J. Wu, A generalized preconditioned HSS method for non-Hermitian positive definite linear systems, Appl. Math. Comput., 216 (2010), 1715-1722. doi: 10.1016/j.amc.2009.12.032.  Google Scholar

show all references

References:
[1]

Z.-Z. Bai, Optimal parameters in the HSS-like methods for saddle point problems, Numer. Linear Algebra Appl., 16 (2009), 447-479. doi: 10.1002/nla.626.  Google Scholar

[2]

Z.-Z. Bai, On semi-convergence of Hermitian and skew-Hermitian splitting methods for singular linear systems, Computing, 89 (2010), 171-197. doi: 10.1007/s00607-010-0101-.  Google Scholar

[3]

Z.-Z. Bai, M. Benzi and F. Chen, Modified HSS iteration methods for a class of complex symmetric linear systems, Computing, 87 (2010), 93-111. doi: 10.1007/s00607-010-0077-0.  Google Scholar

[4]

Z.-Z. Bai, M. Benzi and F. Chen, On preconditioned MHSS iteration methods for complex symmetric linear systems, Numer. Algor., 56 (2011), 297-317. doi: 10.1007/s11075-010-9441-6.  Google Scholar

[5]

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

[6]

Z.-Z. Bai, G. H. Golub and C.-K. Li, Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices, SIAM J. Sci. Comput., 28 (2006), 583-603. doi: 10.1137/050623644.  Google Scholar

[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., 23 (2005), 844-863. doi: 10.1137/S1064827503428114.  Google Scholar

[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. Appl., 24 (2003), 603-626. doi: 10.1137/S0895479801395458.  Google Scholar

[9]

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. doi: 10.1002/nla.517.  Google Scholar

[10]

Z.-Z. Bai, G. H. Golub and M. K. Ng, On inexact Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, Linear Algebra Appl., 428 (2008), 413-440. doi: 10.1016/j.laa.2007.02.018.  Google Scholar

[11]

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

[12]

M. Benzi, A generalization of the Hermitian and skew-Hermitian splitting iteration, SIAM J. Matrix Anal. Appl., 31 (2009), 360-374. doi: 10.1137/080723181.  Google Scholar

[13]

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. doi: 10.1023/B:BITN.0000014548.26616.65.  Google Scholar

[14]

M. Benzi and G. H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), 20-41. doi: 10.1137/S0895479802417106.  Google Scholar

[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. doi: 10.1016/j.apnum.2010.08.005.  Google Scholar

[16]

L. C. Chan, M. K. Ng and N. K. Tsing, Spectral Analysis for HSS Preconditioners, Numer. Math. Theor. Meth. Appl., 1 (2008), 57-77.  Google Scholar

[17]

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. doi: 10.1016/j.cam.2009.05.012.  Google Scholar

[18]

L. Li, T.-Z. Huang and X.-P. Liu, Asymmetric Hermitian and skew-Hermitian splitting methods for positive definite linear systems, Comput. Math. Appl., 54 (2007), 147-159. doi: 10.1016/j.camwa.2006.12.024.  Google Scholar

[19]

J.-Y. Pan, M. K. Ng and Z.-Z. Bai, New preconditioners for saddle point problems, Appl. Math. Comput., 172 (2006), 762-771. doi: 10.1016/j.amc.2004.11.016.  Google Scholar

[20]

D. W. Peaceman and H. H. Rachford Jr., The numerical solution of parabolic and elliptic differential equations, J. Soc. Indust. Appl.Math., 3 (1955), 28-41. doi: 10.1137/0103003.  Google Scholar

[21]

Y. Saad, "Iterative Methods for Sparse Linear Systems," 2nd edition, SIAM, Philadelphia, 2003. doi: 10.1137/1.9780898718003.  Google Scholar

[22]

A.-L Yang, J. An and Y.-J. Wu, A generalized preconditioned HSS method for non-Hermitian positive definite linear systems, Appl. Math. Comput., 216 (2010), 1715-1722. doi: 10.1016/j.amc.2009.12.032.  Google Scholar

[1]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[2]

Inês Cruz, M. Esmeralda Sousa-Dias. Reduction of cluster iteration maps. Journal of Geometric Mechanics, 2014, 6 (3) : 297-318. doi: 10.3934/jgm.2014.6.297
[3]

Erchuan Zhang, Lyle Noakes. Riemannian cubics and elastica in the manifold $ \operatorname{SPD}(n) $ of all $ n\times n $ symmetric positive-definite matrices. Journal of Geometric Mechanics, 2019, 11 (2) : 277-299. doi: 10.3934/jgm.2019015
[4]

David Maxwell. Kozlov-Maz'ya iteration as a form of Landweber iteration. Inverse Problems & Imaging, 2014, 8 (2) : 537-560. doi: 10.3934/ipi.2014.8.537
[5]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[6]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61
[7]

Sihem Guerarra. Positive and negative definite submatrices in an Hermitian least rank solution of the matrix equation AXA*=B. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 15-22. doi: 10.3934/naco.2019002
[8]

Mark Comerford, Todd Woodard. Orbit portraits in non-autonomous iteration. Discrete & Continuous Dynamical Systems - S, 2019, 12 (8) : 2253-2277. doi: 10.3934/dcdss.2019144
[9]

Plamen Stefanov, Yang Yang. Multiwave tomography with reflectors: Landweber's iteration. Inverse Problems & Imaging, 2017, 11 (2) : 373-401. doi: 10.3934/ipi.2017018
[10]

Óscar Vega-Amaya, Joaquín López-Borbón. A perturbation approach to a class of discounted approximate value iteration algorithms with borel spaces. Journal of Dynamics & Games, 2016, 3 (3) : 261-278. doi: 10.3934/jdg.2016014
[11]

Xijun Hu, Li Wu. Decomposition of spectral flow and Bott-type iteration formula. Electronic Research Archive, 2020, 28 (1) : 127-148. doi: 10.3934/era.2020008
[12]

Gemma Huguet, Rafael de la Llave, Yannick Sire. Fast iteration of cocycles over rotations and computation of hyperbolic bundles. Conference Publications, 2013, 2013 (special) : 323-333. doi: 10.3934/proc.2013.2013.323
[13]

Rich Stankewitz, Hiroki Sumi. Random backward iteration algorithm for Julia sets of rational semigroups. Discrete & Continuous Dynamical Systems, 2015, 35 (5) : 2165-2175. doi: 10.3934/dcds.2015.35.2165
[14]

Rich Stankewitz, Hiroki Sumi. Backward iteration algorithms for Julia sets of Möbius semigroups. Discrete & Continuous Dynamical Systems, 2016, 36 (11) : 6475-6485. doi: 10.3934/dcds.2016079
[15]

Xiaoman Liu, Jijun Liu. Image restoration from noisy incomplete frequency data by alternative iteration scheme. Inverse Problems & Imaging, 2020, 14 (4) : 583-606. doi: 10.3934/ipi.2020027
[16]

Jiulong Liu, Nanguang Chen, Hui Ji. Learnable Douglas-Rachford iteration and its applications in DOT imaging. Inverse Problems & Imaging, 2020, 14 (4) : 683-700. doi: 10.3934/ipi.2020031
[17]

Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855
[18]

Helmut Rüssmann. KAM iteration with nearly infinitely small steps in dynamical systems of polynomial character. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 683-718. doi: 10.3934/dcdss.2010.3.683
[19]

Scott Crass. New light on solving the sextic by iteration: An algorithm using reliable dynamics. Journal of Modern Dynamics, 2011, 5 (2) : 397-408. doi: 10.3934/jmd.2011.5.397
[20]

Tahereh Salimi Siahkolaei, Davod Khojasteh Salkuyeh. A preconditioned SSOR iteration method for solving complex symmetric system of linear equations. Numerical Algebra, Control & Optimization, 2019, 9 (4) : 483-492. doi: 10.3934/naco.2019033

 Impact Factor: 

Tools

Metrics

  • PDF downloads (227)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy