THREE-PRECISION GMRES-BASED ITERATIVE REFINEMENT FOR LEAST SQUARES PROBLEMS

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420371" target="_blank" >RIV/00216208:11320/20:10420371 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

THREE-PRECISION GMRES-BASED ITERATIVE REFINEMENT FOR LEAST SQUARES PROBLEMS

Popis výsledku v původním jazyce

The standard iterative refinement procedure for improving an approximate solution to the least squares problem min(x) parallel to b - Ax parallel to(2), where A is an element of R-mxn with m &gt;= n has full rank, is based on solving the (m n) x (m n) augmented system with the aid of a QR factorization. In order to exploit multiprecision arithmetic, iterative refinement can be formulated to use three precisions, but the resulting algorithm converges only for a limited range of problems. We build an iterative refinement algorithm called GMRES-LSIR, analogous to the GMRES-IR algorithm developed for linear systems [E. Carson and N. J. Higham, SIAM T. Set. Comput., 40 (2018), pp. A817-A8471, that solves the augmented system using GMRES preconditioned by a matrix based on the computed QR factors. We explore two left preconditioners; the first has full off-diagonal blocks, and the second is block diagonal and can be applied in either left-sided or split form. We prove that for a wide range of problems the first preconditioner yields backward and forward errors for the augmented system of order the working precision under suitable assumptions on the precisions and the problem conditioning. Our proof does not extend to the block diagonal preconditioner, but our numerical experiments show that with this preconditioner the algorithm performs about as well in practice. The experiments also show that if we use MINRES in place of GMRES then the convergence is similar for sufficiently well conditioned problems but worse for the most ill conditioned ones.

Název v anglickém jazyce

THREE-PRECISION GMRES-BASED ITERATIVE REFINEMENT FOR LEAST SQUARES PROBLEMS

Popis výsledku anglicky

The standard iterative refinement procedure for improving an approximate solution to the least squares problem min(x) parallel to b - Ax parallel to(2), where A is an element of R-mxn with m &gt;= n has full rank, is based on solving the (m n) x (m n) augmented system with the aid of a QR factorization. In order to exploit multiprecision arithmetic, iterative refinement can be formulated to use three precisions, but the resulting algorithm converges only for a limited range of problems. We build an iterative refinement algorithm called GMRES-LSIR, analogous to the GMRES-IR algorithm developed for linear systems [E. Carson and N. J. Higham, SIAM T. Set. Comput., 40 (2018), pp. A817-A8471, that solves the augmented system using GMRES preconditioned by a matrix based on the computed QR factors. We explore two left preconditioners; the first has full off-diagonal blocks, and the second is block diagonal and can be applied in either left-sided or split form. We prove that for a wide range of problems the first preconditioner yields backward and forward errors for the augmented system of order the working precision under suitable assumptions on the precisions and the problem conditioning. Our proof does not extend to the block diagonal preconditioner, but our numerical experiments show that with this preconditioner the algorithm performs about as well in practice. The experiments also show that if we use MINRES in place of GMRES then the convergence is similar for sufficiently well conditioned problems but worse for the most ill conditioned ones.

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í

2020

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 of Scientific Computing

ISSN

1064-8275

e-ISSN

—

Svazek periodika

42

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

21

Strana od-do

"A4063"-"A4083"

Kód UT WoS článku

000600650400024

EID výsledku v databázi Scopus

2-s2.0-85099012171