MIXED PRECISION SKETCHING FOR LEAST-SQUARES PROBLEMS AND ITS APPLICATION IN GMRES-BASED ITERATIVE REFINEMENT

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10509866" target="_blank" >RIV/00216208:11320/25:10509866 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/24M1702246" target="_blank" >10.1137/24M1702246</a>

Jazyk výsledku

angličtina

Název v původním jazyce

MIXED PRECISION SKETCHING FOR LEAST-SQUARES PROBLEMS AND ITS APPLICATION IN GMRES-BASED ITERATIVE REFINEMENT

Popis výsledku v původním jazyce

Sketching-based preconditioners have been shown to accelerate the solution of dense least-squares problems with coefficient matrices having substantially more rows than columns. The cost of generating these preconditioners can be reduced by employing low precision floating-point formats for all or part of the computations. We perform finite precision analysis of a mixed precision algorithm that computes the R-factor of a QR factorization of the sketched coefficient matrix. Two precisions can be chosen and the analysis allows understanding how to set these precisions to exploit the potential benefits of low precision formats and still guarantee an effective preconditioner. If the nature of the least-squares problem requires a solution with a small forward error, then mixed precision iterative refinement (IR) may be needed. For ill-conditioned problems the GMRES-based IR approach can be used, but good preconditioner is crucial to ensure convergence. We theoretically show when the sketching-based preconditioner can guarantee that the GMRES-based IR reduces the relative forward error of the least-squares solution and the residual to the level of the working precision unit roundoff. Small numerical examples illustrate the analysis.

Název v anglickém jazyce

MIXED PRECISION SKETCHING FOR LEAST-SQUARES PROBLEMS AND ITS APPLICATION IN GMRES-BASED ITERATIVE REFINEMENT

Popis výsledku anglicky

Sketching-based preconditioners have been shown to accelerate the solution of dense least-squares problems with coefficient matrices having substantially more rows than columns. The cost of generating these preconditioners can be reduced by employing low precision floating-point formats for all or part of the computations. We perform finite precision analysis of a mixed precision algorithm that computes the R-factor of a QR factorization of the sketched coefficient matrix. Two precisions can be chosen and the analysis allows understanding how to set these precisions to exploit the potential benefits of low precision formats and still guarantee an effective preconditioner. If the nature of the least-squares problem requires a solution with a small forward error, then mixed precision iterative refinement (IR) may be needed. For ill-conditioned problems the GMRES-based IR approach can be used, but good preconditioner is crucial to ensure convergence. We theoretically show when the sketching-based preconditioner can guarantee that the GMRES-based IR reduces the relative forward error of the least-squares solution and the residual to the level of the working precision unit roundoff. Small numerical examples illustrate the analysis.

Druh

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

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

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

SIAM Journal on Matrix Analysis and Applications

ISSN

0895-4798

e-ISSN

1095-7162

Svazek periodika

46

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

20

Strana od-do

2041-2060

Kód UT WoS článku

001580457700005

EID výsledku v databázi Scopus

2-s2.0-105015737412