Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Numerical Algorithms
Published in: Numerical Algorithms 4/2021

18-10-2020 | Original Paper

Asynchronous Richardson iterations: theory and practice

Published in: Numerical Algorithms | Issue 4/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider asynchronous versions of the first- and second-order Richardson methods for solving linear systems of equations. These methods depend on parameters whose values are chosen a priori. We explore the parameter values that can be proven to give convergence of the asynchronous methods. This is the first such analysis for asynchronous second-order methods. We find that for the first-order method, the optimal parameter value for the synchronous case also gives an asynchronously convergent method. For the second-order method, the parameter ranges for which we can prove asynchronous convergence do not contain the optimal parameter values for the synchronous iteration. In practice, however, the asynchronous second-order iterations may still converge using the optimal parameter values, or parameter values close to the optimal ones, despite this result. We explore this behavior with a multithreaded parallel implementation of the asynchronous methods.
previous article New degrees of freedom for high-order Whitney approximations of Darcy’s flows
next article Local and parallel finite element algorithms for the time-dependent Oseen equations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
See also [7, 25].
 
2
Gene Golub in his thesis [14] calls this a method of averaging, following the nomenclature used by von Neumann.
 
Literature
1.
Avron, H., Druinsky, A., Gupta, A.: Revisiting asynchronous linear solvers: Provable convergence rate through randomization. J. ACM 62 (6), 51:1–51:27 (2015)MathSciNetCrossRef
2.
3.
Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences, 3rd edn. Academic Press, New York (1979). Reprinted by SIAM, Philadelphia, 1994MATH
4.
Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, NJ (1989)MATH
5.
Bethune, I., Bull, J.M., Dingle, N.J., Higham, N.J.: Performance analysis of asynchronous Jacobi’s method implemented in MPI, SHMEM and OpenMP. International Journal on High Performance Computing Applications 28 (1), 97–111 (2014)CrossRef
6.
7.
Climent, J.J., Perea, C.: Some comparison theorems for weak nonnegative splittings of bounded operators. Linear Algebra and its Applications 275–276, 77–106 (1998)MathSciNetCrossRef
8.
Eiermann, M., Niethammer, W.: On the construction of semiiterative methods. SIAM J. Numer. Anal. 20, 1153–1160 (1983)MathSciNetCrossRef
9.
Eiermann, M., Niethammer, W., Varga, R.S.: A study of semiiterative methods for nonsymmetric systems of linear equations. Numer. Math. 47, 505–533 (1985)MathSciNetCrossRef
10.
Frankel, S.P.: Convergence rates of iterative treatments of partial differential equations. Mathematical Tables and Aids to Computations 4, 65–75 (1950)MathSciNetCrossRef
11.
12.
Glusa, C., Boman, E.G., Chow, E., Rajamanickam, S., Szyld, D.B.: Scalable asynchronous domain decomposition solvers. Tech. Rep. 19-10-11, Department of Mathematics, Temple University (2019). Revised April 2020and July 2020. To appear in SIAM Journal on Scientific Computing
13.
Golub, G., Overton, M.: The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems. Numer. Math. 53(5), 571–594 (1988)MathSciNetCrossRef
14.
Golub, G.H.: The use of Chebyshev matrix polynomials in the iterative solution of linear equations compared to the method of successive relaxation. Ph.D. thesis, Department of Mathematics, University of Illinois, Urbana (1959)
15.
Golub, G.H., Varga, R.S.: Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods, Part I. Numer. Math. 3, 147–156 (1961)MathSciNetCrossRef
16.
Hook, J., Dingle, N.: Performance analysis of asynchronous parallel Jacobi. Adv. Eng. Softw. 77(3), 831–866 (2018)MathSciNetMATH
17.
Magoulès, F., Szyld, D.B., Venet, C.: Asynchronous optimized Schwarz methods with and without overlap. Numer. Math. 137, 199–227 (2017)MathSciNetCrossRef
18.
Marek, I., Szyld, D.B.: Comparison theorems for weak splittings of bounded operators. Numer. Math. 58, 387–397 (1990)MathSciNetCrossRef
19.
Richardson, L.F.: The approximate arithmetical solution by finite differences of physical problems involving differential equations with an application to the stresses to a masonry dam. Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences 210, 307–357 (1910)MATH
20.
Saad, Y.: Iterative methods for linear systems of equations: A brief historical journey. In: Brenner, S.C., Shparlinski, I., Shu, C.-W., Szyld, D.B. (eds.) 75 Years of Mathematics of Computation, pp 197–216. American Mathematical Society, Providence (2020)
21.
Spiteri, P.: Parallel asynchronous algorithms: A survey. Adv. Eng. Softw. 149, 102896 (2020)CrossRef
22.
Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs (1962). Second Edition, revised and expanded. Springer, Berlin, 2000MATH
23.
Wolfson-Pou, J., Chow, E.: Convergence models and surprising results for the asynchronous Jacobi method. In: 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018, pp 940–949 (2018)
24.
Wolfson-Pou, J., Chow, E.: Modeling the asynchronous Jacobi method without communication delays. Journal of Parallel and Distributed Computing 128, 84–98 (2019)CrossRef
25.
26.
Yamazaki, I., Chow, E., Bouteiller, A., Dongarra, J.: Performance of asynchronous optimized Schwarz with one-sided communication. Parallel Comput. 86, 66–81 (2019)MathSciNetCrossRef
27.
Young, D.M.: Iterative Solution of Large Linear Systems. Academic Press, New York (1971)MATH
28.
Young, D.M.: Second-degree iterative methods for the solution of large linear systems. Journal of Approximation Theory 5, 137–148 (1972)MathSciNetCrossRef
Metadata
Title
Asynchronous Richardson iterations: theory and practice
Publication date
18-10-2020
Published in
Numerical Algorithms / Issue 4/2021
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-020-01023-3

Other articles of this Issue 4/2021

Numerical Algorithms 4/2021 Go to the issue

Original Paper

New degrees of freedom for high-order Whitney approximations of Darcy’s flows

Original Paper

The radial part of a class of Sobolev polynomials on the unit ball

Original Paper

Fast and reliable high-accuracy computation of Gauss–Jacobi quadrature

Original Paper

On preconditioning and solving an extended class of interval parametric linear systems

Original Paper

Numerical study on Moore-Penrose inverse of tensors via Einstein product

Original Paper

α-robust error analysis of a mixed finite element method for a time-fractional biharmonic equation

Premium Partner

    Image Credits