Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2020 Mar 6;378(2166):20190050.
doi: 10.1098/rsta.2019.0050. Epub 2020 Jan 20.

On the cost of iterative computations

Erin Carson  1 , Zdeněk Strakoš  1
Affiliations

On the cost of iterative computations

Erin Carson et al. Philos Trans A Math Phys Eng Sci. .

Abstract

With exascale-level computation on the horizon, the art of predicting the cost of computations has acquired a renewed focus. This task is especially challenging in the case of iterative methods, for which convergence behaviour often cannot be determined with certainty a priori (unless we are satisfied with potentially outrageous overestimates) and which typically suffer from performance bottlenecks at scale due to synchronization cost. Moreover, the amplification of rounding errors can substantially affect the practical performance, in particular for methods with short recurrences. In this article, we focus on what we consider to be key points which are crucial to understanding the cost of iteratively solving linear algebraic systems. This naturally leads us to questions on the place of numerical analysis in relation to mathematics, computer science and sciences, in general. This article is part of a discussion meeting issue 'Numerical algorithms for high-performance computational science'.

Keywords: computational mathematics; high performance computing; iterative methods; matrix computations.

PubMed Disclaimer

Conflict of interest statement

We declare we have no competing interests.

Figures

Figure 1.
Figure 1.
Convergence of HSCG and s-step CG (using monomial basis) with s = 2, 3, 4 in double precision and exact CG for matrix bcsstk01. (Online version in colour.)
Figure 2.
Figure 2.
Convergence of HSCG and pipelined CG in double precision and exact CG for matrix bcsstk01. (Online version in colour.)
Figure 3.
Figure 3.
Convergence of HSCG, s-step CG (using monomial basis) with s = 2, 3, 4, and Pipelined CG in double precision as well as exact CG for matrix nos4. (Online version in colour.)
Figure 4.
Figure 4.
Convergence of CG with clusters of eigenvalues. (Online version in colour.)
See this image and copyright information in PMC

References

    1. Dongarra J, Heroux M, Luszczek P. 2016. High-performance conjugate-gradient benchmark. Int. J. High Perform. Comput. 30, 3–10. (10.1177/1094342015593158) - DOI
    1. Hestenes MR, Stiefel E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand. 49, 409–436. (10.6028/jres.049.044) - DOI
    1. Lanczos C. 1952. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur. Stand. 49, 33–53. (10.6028/jres.049.006) - DOI
    1. Liesen J, Strakoš Z. 2013. Krylov subspace methods: principles and analysis. Numerical Mathematics and Scientific Computation Oxford, UK: Oxford University Press.
    1. Málek J, Strakoš Z. 2015. Preconditioning and the conjugate gradient method in the context of solving PDEs, vol. 1 SIAM Spotlights Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM).

LinkOut - more resources