Mixed precision Rayleigh quotient iteration for total least squares problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10469268" target="_blank" >RIV/00216208:11320/23:10469268 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11075-023-01665-z" target="_blank" >10.1007/s11075-023-01665-z</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Mixed precision Rayleigh quotient iteration for total least squares problems

Popis výsledku v původním jazyce

With the recent emergence of mixed precision hardware, there has been a renewed interest in its use for solving numerical linear algebra problems fast and accurately. The solution of total least squares problems, i.e., solving {$min_{E,r} | [E, r]|_F$} subject to $(A+E)x=b+${$r$}, arises in numerous applications. Solving this problem requires finding the smallest singular value and corresponding right singular vector of $[A,b]$, which is challenging when $A$ is large and sparse. An efficient algorithm for this case due to Bj&quot;{o}rck et al. [SIAM J. Matrix Anal. Appl. 22(2), 2000], called RQI-PCGTLS, is based on Rayleigh quotient iteration coupled with the preconditioned conjugate gradient method.We develop a mixed precision variant of this algorithm, RQI-PCGTLS-MP, in which up to three different precisions can be used. We assume that the lowest precision is used in the computation of the preconditioner, and give theoretical constraints on how this precision must be chosen to ensure stability. In contrast to standard least squares, for total least squares, the resulting constraint depends not only on the matrix $A$, but also on the right-hand side $b$. We perform a number of numerical experiments on model total least squares problems used in the literature, which demonstrate that our algorithm can attain the same accuracy as RQI-PCGTLS albeit with a potential convergence delay due to the use of low precision. Performance modeling shows that the mixed precision approach can achieve up to a $4times$ speedup depending on the size of the matrix and the number of Rayleigh quotient iterations performed.

Název v anglickém jazyce

Mixed precision Rayleigh quotient iteration for total least squares problems

Popis výsledku anglicky

With the recent emergence of mixed precision hardware, there has been a renewed interest in its use for solving numerical linear algebra problems fast and accurately. The solution of total least squares problems, i.e., solving {$min_{E,r} | [E, r]|_F$} subject to $(A+E)x=b+${$r$}, arises in numerous applications. Solving this problem requires finding the smallest singular value and corresponding right singular vector of $[A,b]$, which is challenging when $A$ is large and sparse. An efficient algorithm for this case due to Bj&quot;{o}rck et al. [SIAM J. Matrix Anal. Appl. 22(2), 2000], called RQI-PCGTLS, is based on Rayleigh quotient iteration coupled with the preconditioned conjugate gradient method.We develop a mixed precision variant of this algorithm, RQI-PCGTLS-MP, in which up to three different precisions can be used. We assume that the lowest precision is used in the computation of the preconditioner, and give theoretical constraints on how this precision must be chosen to ensure stability. In contrast to standard least squares, for total least squares, the resulting constraint depends not only on the matrix $A$, but also on the right-hand side $b$. We perform a number of numerical experiments on model total least squares problems used in the literature, which demonstrate that our algorithm can attain the same accuracy as RQI-PCGTLS albeit with a potential convergence delay due to the use of low precision. Performance modeling shows that the mixed precision approach can achieve up to a $4times$ speedup depending on the size of the matrix and the number of Rayleigh quotient iterations performed.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název periodika

Numerical Algorithms

ISSN

1017-1398

e-ISSN

1572-9265

Svazek periodika

2023

Číslo periodika v rámci svazku

05/10/2023

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

22

Strana od-do

—

Kód UT WoS článku

001079117400001

EID výsledku v databázi Scopus

2-s2.0-85173767553