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
Additional Information
- M. Jesús Castel
- Affiliation: Departamento de Tecnología Informática y Computación, Universidad de Alicante, E-03071 Alicante, Spain
- Email: chus@dtic.ua.es
- Violeta Migallón
- Affiliation: Departamento de Tecnología Informática y Computación, Universidad de Alicante, E-03071 Alicante, Spain
- Email: violeta@dtic.ua.es
- José Penadés
- Affiliation: Departamento de Tecnología Informática y Computación, Universidad de Alicante, E-03071 Alicante, Spain
- Email: jpenades@dtic.ua.es
- Received by editor(s): February 2, 1996
- Received by editor(s) in revised form: July 29, 1996
- Additional Notes: This research was supported by Spanish CICYT grant number TIC96-0718-C02-02.
- © Copyright 1998 American Mathematical Society
- Journal: Math. Comp. 67 (1998), 209-220
- MSC (1991): Primary 65F10, 65F15
- DOI: https://doi.org/10.1090/S0025-5718-98-00893-X
- MathSciNet review: 1433264