Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Sequential and parallel synchronous alternating iterative methods


Authors: Joan-Josep Climent, Carmen Perea, Leandro Tortosa and Antonio Zamora
Journal: Math. Comp. 73 (2004), 691-717
MSC (2000): Primary 65F10, 65F15
DOI: https://doi.org/10.1090/S0025-5718-03-01607-7
Published electronically: November 24, 2003
MathSciNet review: 2031401
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The so-called parallel multisplitting nonstationary iterative Model A was introduced by Bru, Elsner, and Neumann [Linear Algebra and its Applications 103:175-192 (1988)] for solving a nonsingular linear system $A\mbox{\mathversion{bold} $x$ } =\mbox{\mathversion{bold} $b$ }$ using a weak nonnegative multisplitting of the first type. In this paper new results are introduced when $A$ is a monotone matrix using a weak nonnegative multisplitting of the second type and when $A$ is a symmetric positive definite matrix using a $P$-regular multisplitting. Also, nonstationary alternating iterative methods are studied. Finally, combining Model A and alternating iterative methods, two new models of parallel multisplitting nonstationary iterations are introduced. When matrix $A$ is monotone and the multisplittings are weak nonnegative of the first or of the second type, both models lead to convergent schemes. Also, when matrix $A$ is symmetric positive definite and the multisplittings are $P$-regular, the schemes are also convergent.


References [Enhancements On Off] (What's this?)

  • 1. A. BERMAN AND R.J. PLEMMONS.
    Nonnegative Matrices in the Mathematical Sciences.
    Academic Press, New York, 1979. Reprinted by SIAM. Philadelphia, PA, 1994.MR 95e:15013
  • 2. M. BENZI AND D.B. SZYLD.
    Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods.
    Numerische Mathematik, 76: 39-321 (1997).MR 98c:65041
  • 3. R. BRU, L. ELSNER, AND M. NEUMANN.
    Models of parallel chaotic iteration methods.
    Linear Algebra and its Applications, 103: 175-192 (1988).MR 90b:65255
  • 4. R. BRU, L. ELSNER, AND M. NEUMANN.
    Convergence of infinite products of matrices and inner-outer iteration schemes.
    Electronic Transactions on Numerical Analysis, 2: 183-193 (1994).MR 95i:65046
  • 5. R. BRU, V. MIGALLÓN, AND J. PENADÉS.
    Chaotic methods for the parallel solution of linear systems.
    Computing Systems in Engineering, 6: 385-390 (1995).
  • 6. J.-J. CLIMENT AND C. PEREA.
    Some comparison theorems for weak nonnegative splittings of bounded operators.
    Linear Algebra and its Applications, 275/276: 77-106 (1998). MR 99j:65043
  • 7. J.-J. CLIMENT AND C. PEREA.
    Convergence and comparison theorems for multisplittings.
    Numerical Linear Algebra with Applications, 6: 93-107 (1999).MR 2000c:65023
  • 8. V. CONRAD AND Y. WALLACH.
    Alternating methods for sets of linear equations.
    Numerische Mathematik, 32: 105-108 (1979). MR 80b:65042
  • 9. G. CSORDAS AND R. VARGA.
    Comparisons of regular splittings of matrices.
    Numerische Mathematik, 44: 23-35 (1984). MR 85g:65043
  • 10. L. ELSNER.
    Comparisons of weak regular splittings and multisplitting methods.
    Numerische Mathematik, 56: 283-289 (1989). MR 85g:65043
  • 11. A. FROMMER AND G. MAYER.
    Convergence of relaxed parallel multisplitting methods.
    Linear Algebra and its Applications, 119: 141-152 (1989). MR 90f:65049
  • 12. A. FROMMER AND G. MAYER.
    On the theory and practice of multisplitting methods in parallel computation.
    Computing, 49: 63-74 (1992). MR 93e:65158
  • 13. A. FROMMER AND D.B. SZYLD.
    Weighted max norms, splittings, and overlapping additive Schwarz iterations.
    Numerische Mathematik, 83: 259-278 (1999). MR 2000g:65023
  • 14. J.M.D. HILL, B. MCCOLL, D.C. STEFANESCU, M.W. GOUDREAU, K. LANG, S.B. RAO, T. SUEL, T. TSANTILAS, AND R.H. BISSELING.
    BSPlib: The BSP Programming Library.
    Parallel Computing, 24: 1947-1980 (1998).
  • 15. P.J. LANZKRON, D.J. ROSE, AND D.B. SZYLD.
    Convergence of nested classical iterative methods for linear systems.
    Numerische Mathematik, 58: 685-702 (1991). MR 92e:65045
  • 16. G.I. MARCHUK.
    Splitting and alternating direction methods.
    In P.G. CIARLET AND J.L. LIONS (editors). Handbook of Numerical Analysis, Vol. I, pages 197-462. North Holland, New York, NY, 1990.
  • 17. I. MAREK AND D.B. SZYLD.
    Comparison theorems for weak splittings of bounded operators.
    Numerische Mathematik, 58: 389-397 (1990). MR 92f:65070
  • 18. V.A. MILLER AND M. NEUMANN.
    A note on comparison theorems for nonnegative matrices.
    Numerische Mathematik, 47: 427-434 (1985). MR 87a:65062
  • 19. V. MIGALLÓN, J. PENADÉS, AND D.B. SZYLD.
    Nonstationary multisplittings with general weighting matrices.
    SIAM Journal on Matrix Analysis and Applications, 22: 1089-1094 (2001). MR 2001m:65046
  • 20. R. NABBEN.
    A note on comparison theorems for splittings and multisplittings of Hermitian positive definite matrices.
    Linear Algebra and its Applications, 233: 67-80 (1996). MR 97a:15035
  • 21. M. NEUMANN AND R.J. PLEMMONS.
    Convergence of parallel multisplitting iterative methods for $M$-matrices.
    Linear Algebra and its Applications, 88/89: 559-573 (1987).MR 88k:65143
  • 22. D.P. O'LEARY AND R.E. WHITE.
    Multi-splittings of matrices and parallel solution of linear systems.
    SIAM Journal on Algebraic and Discrete Methods, 6: 630-640 (1985).MR 86h:65047
  • 23. J.M. ORTEGA.
    Numerical Analysis, A second course.
    Academic Press, New York, NY, 1972. Reprinted by SIAM, Philadelphia, PA, 1992. MR 90k:65005
  • 24. R.S. VARGA.
    Matrix Iterative Analysis.
    Prentice-Hall, Englewood Cliffs, NJ, 1962. MR 28:1725
  • 25. D. WANG.
    On the convergence of the parallel multisplitting AOR algorithm.
    Linear Algebra and its Applications, 154/156: 473-486 (1991). MR 92h:65210
  • 26. Z.I. WOZNICKI.
    Nonnegative splitting theory.
    Japan Journal on Industrial and Applied Mathematics, 11: 289-342 (1994). MR 95g:65051
  • 27. D.M. YOUNG.
    Iterative Solution of Large Linear Systems.
    Academic Press, New York, NY, 1971.MR 46:4698

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F10, 65F15

Retrieve articles in all journals with MSC (2000): 65F10, 65F15


Additional Information

Joan-Josep Climent
Affiliation: Departament de Ciència de la Computació i Intel$⋅$ligència Artificial, Universitat d’Alacant, Ap. Correus 99, E–03080 Alacant, Spain
Email: jcliment@dccia.ua.es

Carmen Perea
Affiliation: Departamento de Estadística y Matemática Aplicada, Universidad Miguel Hernández, Escuela Politécnica Superior de Orihuela, E-03550, Orihuela, Spain
Email: perea@umh.es

Leandro Tortosa
Affiliation: Departament de Ciència de la Computació i Intel$⋅$ligència Artificial, Universitat d’Alacant, Ap. Correus 99, E–03080 Alacant, Spain
Email: tortosa@dccia.ua.es

Antonio Zamora
Affiliation: Departament de Ciència de la Computació i Intel$⋅$ligència Artificial, Universitat d’Alacant, Ap. Correus 99, E–03080 Alacant, Spain
Email: zamora@dccia.ua.es

DOI: https://doi.org/10.1090/S0025-5718-03-01607-7
Keywords: Nonsingular matrix, iterative method, spectral radius, splitting, multisplitting, alternating method, stationary method, nonstationary method, convergence conditions, comparison conditions
Received by editor(s): July 9, 2001
Received by editor(s) in revised form: November 13, 2002
Published electronically: November 24, 2003
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society