Mathematics of Computation

Convergence of Non-stationary Parallel Multisplitting Methods for Hermitian Positive Definite Matrices

Author(s): M. Jesús Castel; Violeta Migallón; José Penadés.
Journal: Math. Comp. 67 (1998), 209-220.
MSC (1991): Primary 65F10, 65F15
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

1.: 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.
2.: Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, third ed., Academic Press, New York, 1979, Reprinted by SIAM, Philadelphia, 1994. MR 95e:15013
3.: Rafael Bru, Ludwing Elsner, and Michael Neumann, Models of parallel chaotic iteration methods, Linear Algebra Appl. 103 (1988), 175-192. MR 90b:65255
4.: Rafael Bru and Robert Fuster, Parallel chaotic extrapolated acobi method, Appl. Math. Lett. 3 (1990), no. 4, 65-69. CMP 91:04
5.: 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.
6.: -, Chaotic methods for the parallel solution of linear systems, Computing Systems in Engineering 6 (1995), no. 4,5, 385-390.
7.: Rafael Bru, Violeta Migallón, José Penadés, and Daniel B. Szyld, Parallel, synchronous and asynchronous two-stage multisplitting methods, Electronic Transactions on Numerical Analysis 3 (1995), 24-38. MR 95m:65048
8.: D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra Appl. 2 (1969), 199-222. MR 40:5114
9.: Ludwig Elsner, Israel Koltracht, and Michael Neumann, On the convergence of asynchronous paracontractions with application to tomographic reconstruction from incomplete data, Linear Algebra Appl. 130 (1990), 65-82. MR 91g:65093
10.: Andreas Frommer, On asynchronous iterations in partially ordered spaces, Numer. Funct. Anal. Optim. 12 (1991), no. 3,4, 315-325. MR 92m:54060
11.: Andreas Frommer and Mayer, Convergence of relaxed parallel multisplitting methods, Linear Algebra Appl. 119 (1989), 141-152. MR 90f:65049
12.: -, On the theory and practice of multisplitting methods in parallel computation, Computing 49 (1992), 63-74. MR 93e:65158
13.: Andreas Frommer and Daniel B. Szyld, Asynchronous two-stage iterative methods, Numer. Math. 69 (1994), 141-153. MR 95m:65049
14.: Robert Fuster, Violeta Migallón, and José Penadés, Non-stationary parallel multisplitting methods, Electronic Transactions on Numerical Analysis 4 (1996), 1-13. MR 96m:65038
15.: -, Parallel chaotic extrapolated acobi-like methods, Linear Algebra Appl. 247 (1966), 237-250. CMP 97:02
16.: Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell, Waltham, Mass. 1964, Reprinted by Dover, New York, 1975. MR 51:14539
17.: Charles R. Johnson and Rafael Bru, The spectral radius of a product of nonnegative matrices, Linear Algebra Appl. 141 (1990), 227-240. MR 91i:15011
18.: Paul J. Lanzkron, Donald J. Rose, and Daniel B. Szyld, Convergence of nested iterative methods for linear systems, Numer. Math. 58 (1991), 685-702. MR 92e:65045
19.: 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. CMP 90:08
20.: 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. CMP 96:15
21.: Reinhard Nabben, A note on comparison theorems for splittings and multisplittings of hermitian positive definite matrices, Linear Algebra Appl. 233 (1995), 67-80. MR 97a:15035
22.: Michael Neumann and Robert J. Plemmons, Convergence of parallel multisplitting iterative methods for $M$-matrices, Linear Algebra Appl. 88-89 (1987), 559-573. MR 88k:65143
23.: Dianne P. O'Leary and Robert E. White, Multi-splittings of matrices and parallel solution of linear systems, SIAM J. Alg. Disc. Meth. 6 (1985), 630-640. MR 86h:65047
24.: James M. Ortega, Matrix theory, Plenum Press, New York, 1987. MR 88a:15002
25.: James M. Ortega, Introduction to parallel and vector solution of linear systems, Plenum Press, New York, 1988. MR 92i:65220a
26.: Werner C. Rheinboldt and James S. Vandergraft, A simple approach to the Perron-Frobenius theory for positive operators on general partially-ordered finite-dimentional linear spaces, Math. Comp. 27 (1973), 139-145. MR 48:3997
27.: F. Robert, M. Charnay, and F. Musy, Itérations chaotiques série-parallèle pour des équations non-linéaires de point fixe, Aplikace Matematiky 20 (1975), 1-38. MR 51:9472
28.: Robert E. White, Multisplittings and parallel iterative methods, Comput. Methods Appl. Mech. Engrg. 64 (1987), 567-577. MR 88j:65315
29.: -, Multisplitting with different weighting schemes, SIAM J. Matrix Anal. Appl. 10 (1989), 481-493. MR 90k:65116
30.: -, Multisplitting of a symmetric positive definite matrix, SIAM J. Matrix Anal. Appl. 11 (1990), 69-82. MR 91k:65064

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

DOI: 10.1090/S0025-5718-98-00893-X
PII: S 0025-5718(98)00893-X
Keywords: Non-stationary methods, asynchronous iterations, linear systems, multisplitting, hermitian matrix, positive definite matrix
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 of article: Copyright 1998, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS