Mixed precision s-step Lanczos and conjugate gradient algorithms

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10436238" target="_blank" >RIV/00216208:11320/21:10436238 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=6NE8Dz.9PD" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=6NE8Dz.9PD</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/nla.2425" target="_blank" >10.1002/nla.2425</a>

Result language

angličtina

Original language name

Mixed precision s-step Lanczos and conjugate gradient algorithms

Original language description

Compared to the classical Lanczos algorithm, the s-step Lanczos variant has the potential to improve performance by asymptotically decreasing the synchronization cost per iteration. However, this comes at a price; despite being mathematically equivalent, the s-step variant may behave quite differently in finite precision, potentially exhibiting greater loss of accuracy and slower convergence relative to the classical algorithm. It has previously been shown that the errors in the s-step version follow the same structure as the errors in the classical algorithm, but are amplified by a factor depending on the square of the condition number of the O(s)-dimensional Krylov bases computed in each outer loop. As the condition number of these s-step bases grows (in some cases very quickly) with s, this limits the s values that can be chosen and thus can limit the attainable performance. In this work, we show that if a select few computations in s-step Lanczos are performed in double the working precision, the error terms then depend only linearly on the conditioning of the s-step bases. This has the potential for drastically improving the numerical behavior of the algorithm with little impact on per-iteration performance. Our numerical experiments demonstrate the improved numerical behavior possible with the mixed precision approach, and also show that this improved behavior extends to mixed precision s-step CG. We present preliminary performance results on NVIDIA V100 GPUs that show that the overhead of extra precision is minimal if one uses precisions implemented in hardware.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10102 - Applied mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2021

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Numerical Linear Algebra with Applications

ISSN

1070-5325

e-ISSN

—

Volume of the periodical

2021

Issue of the periodical within the volume

e2425

Country of publishing house

GB - UNITED KINGDOM

Number of pages

24

Pages from-to

1-24

UT code for WoS article

000721446000001

EID of the result in the Scopus database

2-s2.0-85119656079