Convergence of non-stationary parallel multisplitting methods for hermitian positive definite matrices

Castel, M.; Migallón, Violeta; Penadés, José

doi:10.1090/S0025-5718-98-00893-X

Convergence of non-stationary parallel multisplitting methods for hermitian positive definite matrices
HTML articles powered by AMS MathViewer

by M. Jesús Castel, Violeta Migallón and José Penadés PDF

Math. Comp. 67 (1998), 209-220 Request permission

Abstract:

Non-stationary multisplitting algorithms for the solution of linear systems are studied. Convergence of these algorithms is analyzed when the coefficient matrix of the linear system is hermitian positive definite. Asynchronous versions of these algorithms are considered and their convergence investigated.

References

Michele Benzi and Daniel B. Szyld, Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods, Tech. Report 95-81, Department of Mathematics, Temple University, Philadelphia, Pa., August 1995. Also available via anonymous ftp at ftp.math.temple.edu in directory pub/szyld. To appear in Numer. Math.
Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. MR 1298430, DOI 10.1137/1.9781611971262
Rafael Bru, Ludwig Elsner, and Michael Neumann, Models of parallel chaotic iteration methods, Linear Algebra Appl. 103 (1988), 175–192. MR 944001, DOI 10.1016/0024-3795(88)90227-3
Rafael Bru and Robert Fuster, Parallel chaotic extrapolated \text{J}acobi method, Appl. Math. Lett. 3 (1990), no. 4, 65–69.
Rafael Bru, Violeta Migallón, and José Penadés, Chaotic inner–outer iterative schemes, Proceedings of the Fifth SIAM Conference on Applied Linear Algebra (J.G. Lewis, ed.), SIAM Press, Philadelphia, 1994, pp. 434–438.
—, Chaotic methods for the parallel solution of linear systems, Computing Systems in Engineering 6 (1995), no. 4,5, 385–390.
Rafael Bru, Violeta Migallón, José Penadés, and Daniel B. Szyld, Parallel, synchronous and asynchronous two-stage multisplitting methods, Electron. Trans. Numer. Anal. 3 (1995), no. Mar., 24–38. MR 1320601
D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra Appl. 2 (1969), 199–222. MR 251888, DOI 10.1016/0024-3795(69)90028-7
L. Elsner, I. Koltracht, and M. Neumann, On the convergence of asynchronous paracontractions with application to tomographic reconstruction from incomplete data, Linear Algebra Appl. 130 (1990), 65–82. Linear algebra in image reconstruction from projections. MR 1057801, DOI 10.1016/0024-3795(90)90206-R
Andreas Frommer, On asynchronous iterations in partially ordered spaces, Numer. Funct. Anal. Optim. 12 (1991), no. 3-4, 315–325. MR 1143002, DOI 10.1080/01630569108816431
Andreas Frommer and Günter Mayer, Convergence of relaxed parallel multisplitting methods, Linear Algebra Appl. 119 (1989), 141–152. MR 1005240, DOI 10.1016/0024-3795(89)90074-8
A. Frommer and G. Mayer, On the theory and practice of multisplitting methods in parallel computation, Computing 49 (1992), no. 1, 63–74 (English, with English and German summaries). MR 1182442, DOI 10.1007/BF02238650
Andreas Frommer and Daniel B. Szyld, Asynchronous two-stage iterative methods, Numer. Math. 69 (1994), no. 2, 141–153. MR 1310314, DOI 10.1007/s002110050085
Robert Fuster, Violeta Migallón, and José Penadés, Non-stationary parallel multisplitting AOR methods, Electron. Trans. Numer. Anal. 4 (1996), no. Mar., 1–13. MR 1386972
—, Parallel chaotic extrapolated \text{J}acobi–like methods, Linear Algebra Appl. 247 (1966), 237–250.
Alston S. Householder, The theory of matrices in numerical analysis, Dover Publications, Inc., New York, 1975. Reprint of 1964 edition. MR 0378371
Charles R. Johnson and Rafael Bru, The spectral radius of a product of nonnegative matrices, Linear Algebra Appl. 141 (1990), 227–240. MR 1076115, DOI 10.1016/0024-3795(90)90320-C
Paul J. Lanzkron, Donald J. Rose, and Daniel B. Szyld, Convergence of nested classical iterative methods for linear systems, Numer. Math. 58 (1991), no. 7, 685–702. MR 1090255, DOI 10.1007/BF01385649
Guri I. Marchuk, Splitting and alternating direction methods, Handbook of Numerical Analysis, Vol. I (P.G. Ciarlet and J.L. Lions, eds.), North Holland, New York, 1990, pp. 197–462.
José Mas, Violeta Migallón, José Penadés, and Daniel B. Szyld, Non-stationary parallel relaxed multisplitting methods, Linear Algebra Appl. 241–243 (1996), 733–748.
Reinhard Nabben, A note on comparison theorems for splittings and multisplittings of Hermitian positive definite matrices, Linear Algebra Appl. 233 (1996), 67–80. MR 1368073, DOI 10.1016/0024-3795(94)00050-6
M. Neumann and R. J. Plemmons, Convergence of parallel multisplitting iterative methods for $M$-matrices, Linear Algebra Appl. 88/89 (1987), 559–573. MR 882463, DOI 10.1016/0024-3795(87)90125-X
Dianne P. O’Leary and R. E. White, Multisplittings of matrices and parallel solution of linear systems, SIAM J. Algebraic Discrete Methods 6 (1985), no. 4, 630–640. MR 800993, DOI 10.1137/0606062
James M. Ortega, Matrix theory, The University Series in Mathematics, Plenum Press, New York, 1987. A second course. MR 878977, DOI 10.1007/978-1-4899-0471-3
James M. Ortega, Introduction to parallel and vector solution of linear systems, Frontiers of Computer Science, Plenum Press, New York, 1989. MR 1106195
Werner C. Rheinboldt and James S. Vandergraft, A simple approach to the Perron-Frobenius theory for positive operators on general partially-ordered finite-dimensional linear spaces, Math. Comp. 27 (1973), 139–145. MR 325650, DOI 10.1090/S0025-5718-1973-0325650-4
F. Robert, M. Charnay, and F. Musy, Itérations chaotiques série-parallèle pour des équations non-linéaires de point fixe, Apl. Mat. 20 (1975), 1–38 (French, with Czech summary). MR 373272
R. E. White, Multisplittings and parallel iterative methods, Proceedings of the first world congress on computational mechanics (Austin, Tex., 1986), 1987, pp. 567–577. MR 912527, DOI 10.1016/0045-7825(87)90057-0
R. E. White, Multisplitting with different weighting schemes, SIAM J. Matrix Anal. Appl. 10 (1989), no. 4, 481–493. MR 1016797, DOI 10.1137/0610034
R. E. White, Multisplitting of a symmetric positive definite matrix, SIAM J. Matrix Anal. Appl. 11 (1990), no. 1, 69–82. MR 1032217, DOI 10.1137/0611004