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

Previous Article
On convergence of the inner-outer iteration method for computing PageRank
NACO Home
This Issue
Next Article

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

Yanxing Cui ^1, , Chuanlong Wang ^2, and Ruiping Wen ^2,

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

Abstract
Related Papers

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.

Keywords: Parallel Multisplitting, seminorm convergence, semidefinite matrix, convergence, quotient convergence..

Mathematics Subject Classification: 58F15, 58F1.

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,", 2^nd 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,", 2^nd 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]	Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023
[2]	Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[3]	Xiaoxue Gong, Ying Xu, Vinay Mahadeo, Tulin Kaman, Johan Larsson, James Glimm. Mesh convergence for turbulent combustion. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4383-4402. doi: 10.3934/dcds.2016.36.4383
[4]	Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[5]	James Broda, Alexander Grigo, Nikola P. Petrov. Convergence rates for semistochastic processes. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 109-125. doi: 10.3934/dcdsb.2019001
[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]	Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030
[8]	Jacek Banasiak, Amartya Goswami. Singularly perturbed population models with reducible migration matrix 1. Sova-Kurtz theorem and the convergence to the aggregated model. Discrete & Continuous Dynamical Systems - A, 2015, 35 (2) : 617-635. doi: 10.3934/dcds.2015.35.617
[9]	Micol Amar, Andrea Braides. A characterization of variational convergence for segmentation problems. Discrete & Continuous Dynamical Systems - A, 1995, 1 (3) : 347-369. doi: 10.3934/dcds.1995.1.347
[10]	Michael Boshernitzan, Máté Wierdl. Almost-everywhere convergence and polynomials. Journal of Modern Dynamics, 2008, 2 (3) : 465-470. doi: 10.3934/jmd.2008.2.465
[11]	Antonio Giorgilli, Stefano Marmi. Convergence radius in the Poincaré-Siegel problem. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 601-621. doi: 10.3934/dcdss.2010.3.601
[12]	Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791
[13]	Chunlei Zhang, Qin Sheng, Raúl Ordóñez. Notes on the convergence and applications of surrogate optimization. Conference Publications, 2005, 2005 (Special) : 947-956. doi: 10.3934/proc.2005.2005.947
[14]	Eric Cancès, Claude Le Bris. Convergence to equilibrium of a multiscale model for suspensions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 449-470. doi: 10.3934/dcdsb.2006.6.449
[15]	Giuseppe Maria Coclite, Lorenzo di Ruvo. A note on the convergence of the solution of the Novikov equation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (6) : 2865-2899. doi: 10.3934/dcdsb.2018290
[16]	Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[17]	J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[18]	Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[19]	Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[20]	Pavel Krejčí, Songmu Zheng. Pointwise asymptotic convergence of solutions for a phase separation model. Discrete & Continuous Dynamical Systems - A, 2006, 16 (1) : 1-18. doi: 10.3934/dcds.2006.16.1

Impact Factor:

American Institute of Mathematical Sciences