2012, 2(4): 863-873. doi: 10.3934/naco.2012.2.863

On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems

1. 

Department of Mathematics, Changzhi University, Changzhi 046011, Shanxi Province, China

2. 

Department of Mathematics, Taiyuan Normal University, Taiyuan 030012, Shanxi Province, China, China

Received  January 2012 Revised  October 2012 Published  November 2012

In this paper, we present the generalized stationary and nonstationary multisplitting iterative methods for positive semidefinite linear systems. We study the convergence theories of new methods and show that the quotient convergence and convergence of stationary parallel multisplitting method are equivalent under a concise condition. Finally, we prove that the generalized nonstationary parallel multisplitting method is quotient convergence with general weighting matrices.
Citation: Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
References:
[1]

Z.-Z. Bai and D.-R. Wang, Generalized matrix multisplitting relaxation methods and their convergence,, Numer. Math. J. Chinese Univ. (English Ser.), 2 (1993), 87.   Google Scholar

[2]

Z.-Z. Bai, On the convergence of the generalized matrix multisplitting relaxed methods,, Commun. Numer. Methods Engrg., 11 (1995), 363.  doi: 10.1002/cnm.1640110410.  Google Scholar

[3]

Z.-Z. Bai, J.-C. Sun and D.-R. Wang, A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations,, Comput. Math. Appl., 32 (1996), 51.  doi: 10.1016/S0898-1221(96)00207-6.  Google Scholar

[4]

Z.-Z. Bai and C.-L. Wang, On the convergence of nonstationary multisplitting two-stage iteration methods for Hermitian positive definite linear systems,, J. Comput. Appl. Math., 138 (2002), 287.  doi: 10.1016/S0377-0427(01)00376-4.  Google Scholar

[5]

Z.-Z. Bai, L. Wang and J.-Y. Yuan, Weak-convergence theory of quasi-nonnegative splittings for singular matrices,, Appl. Numer. Math., 47 (2003), 75.  doi: 10.1016/S0168-9274(03)00057-6.  Google Scholar

[6]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications,", Wiley, (1974).   Google Scholar

[7]

A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Science,", Academic Press, (1979).   Google Scholar

[8]

Z. Cao and Z. Liu, Symmetric multisplitting of a symmetric positive definite matrix,, Linear Algebra Appl., 285 (1998), 309.  doi: 10.1016/S0024-3795(98)10151-9.  Google Scholar

[9]

Z. Cao, On the convergence of nonstationary iterative methods for symmetric positive (semi)defnite systems,, Appl. Numer. Math., 37 (2001), 319.  doi: 10.1016/S0168-9274(00)00047-7.  Google Scholar

[10]

Z. Cao, On the convergence of general stationary linear iterative methods for singular linear systems,, SIAM J. Matrix Anal. Appl., 29 (2007), 1382.  doi: 10.1137/060671243.  Google Scholar

[11]

Z. Cao, On the convergence of iterative methods for solving singular linear systems,, J. Comput. Appl. Math., 145 (2002), 1.  doi: 10.1016/S0377-0427(01)00531-3.  Google Scholar

[12]

M. J. Castel, V. Migallón and J. Penadés, Convergence of non-stationary parallel multisplitting methods for hermitian positive definite matrices,, Math. Comput., 67 (1998), 209.  doi: 10.1090/S0025-5718-98-00893-X.  Google Scholar

[13]

X. Cui, Y. Wei and N. Zhang, Quotient convergence and multisplitting methods for solving singular linear equations,, Calcolo, 44 (2007), 21.  doi: 10.1007/s10092-007-0127-y.  Google Scholar

[14]

A. Frommer, R. Nabben and D. B.Szyld, Convergence of stationary iterative methods for hermitian semidefinite linear systems and applications to schwarz methods,, SIAM J. Matrix Anal. Appl., 30 (2008), 925.  doi: 10.1137/080714038.  Google Scholar

[15]

H. B. Keller, On the solution of singular and semidefinite linear systems by iteration,, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 281.   Google Scholar

[16]

Y.-J. Lee, J. Wu, Jinchao Xu and L. Zikatanov, On the convergence of iterative methods for semidefinite linear systems,, SIAM J. Matrix Anal. Appl., 28 (2006), 634.  doi: 10.1137/050644197.  Google Scholar

[17]

L. Lin, Y. Wei and N. Zhang, Convergence and quotient convergence of iterative methods for solving singular linear equations with index one,, Linear Algebra Appl., 430 (2009), 1665.  doi: 10.1016/j.laa.2008.06.019.  Google Scholar

[18]

G. I. Marchuk and Y. Kuznetsov, "Iterative Methods and Quadratic Functionals,", Science Press, (1972).   Google Scholar

[19]

V. Migallón, J. Penadés and D. B. Szyld, Nonstationary multisplittings with general weighting matrices,, SIAM J. Matrix Anal. Appl., 22 (2001), 1089.  doi: 10.1137/S0895479800367038.  Google Scholar

[20]

D. P. O'Leary and R. E. White, Multisplittings of matrices and parallel solution of linear systems,, SIAM J. on Alg. and Disc. Meth., 6 (1985), 630.  doi: 10.1137/0606062.  Google Scholar

[21]

D. B. Szyld, Equivalence of conditions for convergence of iterative methods for singular equations,, Numer. Linear Algebra Appl., 1 (1994), 151.  doi: 10.1002/nla.1680010206.  Google Scholar

[22]

R. S. Varga, "Matrix Iterative Analysis,", 2nd edition, (2000).  doi: 10.1007/978-3-642-05156-2.  Google Scholar

[23]

C.-L. Wang, Nonstationary multisplitting with general weighting matrices for non-Hermitian positive definite systems,, Appl. Math. Lett., 16 (2003), 919.  doi: 10.1016/S0893-9659(03)90017-6.  Google Scholar

[24]

D.-R. Wang and Z.-Z. Bai, Asynchronous parallel matrix multisplitting multiparameter relaxation methods,, (Chinese) Numer. Math. J. Chinese Univ., 16 (1994), 107.   Google Scholar

[25]

Y. Wei, Index splitting for the Drazin inverse and the singular linear system,, Appl. Math. Comput., 95 (1998), 115.  doi: 10.1016/S0096-3003(97)10098-4.  Google Scholar

[26]

Y. Wei, Perturbation analysis of singular linear systems with index one,, Int. J. Comput. Math., 74 (2000), 483.  doi: 10.1080/00207160008804956.  Google Scholar

[27]

J. Wu, Y.-J. Lee, J. Xu and Ludmil Zikatanov, Convergence analysis on iterative methods for semidefinite systems,, J. Comput. Math., 26 (2008), 797.   Google Scholar

[28]

D. M. Young, "Iterative Solution of Large Linear Systems,", Academic Press, (1971).   Google Scholar

show all references

References:
[1]

Z.-Z. Bai and D.-R. Wang, Generalized matrix multisplitting relaxation methods and their convergence,, Numer. Math. J. Chinese Univ. (English Ser.), 2 (1993), 87.   Google Scholar

[2]

Z.-Z. Bai, On the convergence of the generalized matrix multisplitting relaxed methods,, Commun. Numer. Methods Engrg., 11 (1995), 363.  doi: 10.1002/cnm.1640110410.  Google Scholar

[3]

Z.-Z. Bai, J.-C. Sun and D.-R. Wang, A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations,, Comput. Math. Appl., 32 (1996), 51.  doi: 10.1016/S0898-1221(96)00207-6.  Google Scholar

[4]

Z.-Z. Bai and C.-L. Wang, On the convergence of nonstationary multisplitting two-stage iteration methods for Hermitian positive definite linear systems,, J. Comput. Appl. Math., 138 (2002), 287.  doi: 10.1016/S0377-0427(01)00376-4.  Google Scholar

[5]

Z.-Z. Bai, L. Wang and J.-Y. Yuan, Weak-convergence theory of quasi-nonnegative splittings for singular matrices,, Appl. Numer. Math., 47 (2003), 75.  doi: 10.1016/S0168-9274(03)00057-6.  Google Scholar

[6]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications,", Wiley, (1974).   Google Scholar

[7]

A. Berman and R. J. Plemmons, "Nonnegative Matrices in the Mathematical Science,", Academic Press, (1979).   Google Scholar

[8]

Z. Cao and Z. Liu, Symmetric multisplitting of a symmetric positive definite matrix,, Linear Algebra Appl., 285 (1998), 309.  doi: 10.1016/S0024-3795(98)10151-9.  Google Scholar

[9]

Z. Cao, On the convergence of nonstationary iterative methods for symmetric positive (semi)defnite systems,, Appl. Numer. Math., 37 (2001), 319.  doi: 10.1016/S0168-9274(00)00047-7.  Google Scholar

[10]

Z. Cao, On the convergence of general stationary linear iterative methods for singular linear systems,, SIAM J. Matrix Anal. Appl., 29 (2007), 1382.  doi: 10.1137/060671243.  Google Scholar

[11]

Z. Cao, On the convergence of iterative methods for solving singular linear systems,, J. Comput. Appl. Math., 145 (2002), 1.  doi: 10.1016/S0377-0427(01)00531-3.  Google Scholar

[12]

M. J. Castel, V. Migallón and J. Penadés, Convergence of non-stationary parallel multisplitting methods for hermitian positive definite matrices,, Math. Comput., 67 (1998), 209.  doi: 10.1090/S0025-5718-98-00893-X.  Google Scholar

[13]

X. Cui, Y. Wei and N. Zhang, Quotient convergence and multisplitting methods for solving singular linear equations,, Calcolo, 44 (2007), 21.  doi: 10.1007/s10092-007-0127-y.  Google Scholar

[14]

A. Frommer, R. Nabben and D. B.Szyld, Convergence of stationary iterative methods for hermitian semidefinite linear systems and applications to schwarz methods,, SIAM J. Matrix Anal. Appl., 30 (2008), 925.  doi: 10.1137/080714038.  Google Scholar

[15]

H. B. Keller, On the solution of singular and semidefinite linear systems by iteration,, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 281.   Google Scholar

[16]

Y.-J. Lee, J. Wu, Jinchao Xu and L. Zikatanov, On the convergence of iterative methods for semidefinite linear systems,, SIAM J. Matrix Anal. Appl., 28 (2006), 634.  doi: 10.1137/050644197.  Google Scholar

[17]

L. Lin, Y. Wei and N. Zhang, Convergence and quotient convergence of iterative methods for solving singular linear equations with index one,, Linear Algebra Appl., 430 (2009), 1665.  doi: 10.1016/j.laa.2008.06.019.  Google Scholar

[18]

G. I. Marchuk and Y. Kuznetsov, "Iterative Methods and Quadratic Functionals,", Science Press, (1972).   Google Scholar

[19]

V. Migallón, J. Penadés and D. B. Szyld, Nonstationary multisplittings with general weighting matrices,, SIAM J. Matrix Anal. Appl., 22 (2001), 1089.  doi: 10.1137/S0895479800367038.  Google Scholar

[20]

D. P. O'Leary and R. E. White, Multisplittings of matrices and parallel solution of linear systems,, SIAM J. on Alg. and Disc. Meth., 6 (1985), 630.  doi: 10.1137/0606062.  Google Scholar

[21]

D. B. Szyld, Equivalence of conditions for convergence of iterative methods for singular equations,, Numer. Linear Algebra Appl., 1 (1994), 151.  doi: 10.1002/nla.1680010206.  Google Scholar

[22]

R. S. Varga, "Matrix Iterative Analysis,", 2nd edition, (2000).  doi: 10.1007/978-3-642-05156-2.  Google Scholar

[23]

C.-L. Wang, Nonstationary multisplitting with general weighting matrices for non-Hermitian positive definite systems,, Appl. Math. Lett., 16 (2003), 919.  doi: 10.1016/S0893-9659(03)90017-6.  Google Scholar

[24]

D.-R. Wang and Z.-Z. Bai, Asynchronous parallel matrix multisplitting multiparameter relaxation methods,, (Chinese) Numer. Math. J. Chinese Univ., 16 (1994), 107.   Google Scholar

[25]

Y. Wei, Index splitting for the Drazin inverse and the singular linear system,, Appl. Math. Comput., 95 (1998), 115.  doi: 10.1016/S0096-3003(97)10098-4.  Google Scholar

[26]

Y. Wei, Perturbation analysis of singular linear systems with index one,, Int. J. Comput. Math., 74 (2000), 483.  doi: 10.1080/00207160008804956.  Google Scholar

[27]

J. Wu, Y.-J. Lee, J. Xu and Ludmil Zikatanov, Convergence analysis on iterative methods for semidefinite systems,, J. Comput. Math., 26 (2008), 797.   Google Scholar

[28]

D. M. Young, "Iterative Solution of Large Linear Systems,", Academic Press, (1971).   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]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[3]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[4]

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

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

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

[7]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[8]

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

[9]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[10]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[11]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435

[12]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[13]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[14]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[15]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]