Block conjugate gradient methods with error norm estimates for least squares problems

Kód výsledku v IS VaVaI

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

Výsledek na webu

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10543-025-01096-3" target="_blank" >10.1007/s10543-025-01096-3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Block conjugate gradient methods with error norm estimates for least squares problems

Popis výsledku v původním jazyce

Least squares problems with multiple right-hand sides naturally arise in many practical applications. When the system matrix A is large and sparse, it is often convenient to solve such problems using suitably adapted variants of the block conjugate gradient method (block CGLS) or the block LSQR method. These block methods allow efficient use of modern computational architectures, and the number of iterations needed to achieve the required accuracy is typically much smaller than that required when solving each system separately and successively. However, a known limitation of these block methods is, for some problems, the occurrence of (near) breakdowns caused by (near) rank deficiencies within block vectors. We show how ideas presented in 2001 by A. Dubrulle for block CG can be incorporated into the block CGLS and block LSQR algorithms to avoid numerical instabilities caused by (near) rank deficiencies. For A with a full column rank, this provably prevents breakdowns in block CGLS. For the considered (preconditioned) algorithms, we derive estimates of the ATAdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$A&lt;^&gt;{T}A$$end{document}-norm of the error for each individual system, as well as for the trace of the corresponding bilinear form. These estimates are often well suited for use in stopping criteria. We consider both lower and upper bounds and show how the estimates can be adaptively refined to heuristically achieve a prescribed level of accuracy. Numerical experiments clearly illustrate which block algorithms are the most effective for practical computations and demonstrate that adaptive estimates perform reliably.

Název v anglickém jazyce

Block conjugate gradient methods with error norm estimates for least squares problems

Popis výsledku anglicky

Least squares problems with multiple right-hand sides naturally arise in many practical applications. When the system matrix A is large and sparse, it is often convenient to solve such problems using suitably adapted variants of the block conjugate gradient method (block CGLS) or the block LSQR method. These block methods allow efficient use of modern computational architectures, and the number of iterations needed to achieve the required accuracy is typically much smaller than that required when solving each system separately and successively. However, a known limitation of these block methods is, for some problems, the occurrence of (near) breakdowns caused by (near) rank deficiencies within block vectors. We show how ideas presented in 2001 by A. Dubrulle for block CG can be incorporated into the block CGLS and block LSQR algorithms to avoid numerical instabilities caused by (near) rank deficiencies. For A with a full column rank, this provably prevents breakdowns in block CGLS. For the considered (preconditioned) algorithms, we derive estimates of the ATAdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$A&lt;^&gt;{T}A$$end{document}-norm of the error for each individual system, as well as for the trace of the corresponding bilinear form. These estimates are often well suited for use in stopping criteria. We consider both lower and upper bounds and show how the estimates can be adaptively refined to heuristically achieve a prescribed level of accuracy. Numerical experiments clearly illustrate which block algorithms are the most effective for practical computations and demonstrate that adaptive estimates perform reliably.

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

BIT Numerical Mathematics

ISSN

0006-3835

e-ISSN

1572-9125

Svazek periodika

66

Číslo periodika v rámci svazku

December 2025

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

29

Strana od-do

2

Kód UT WoS článku

001632465500002

EID výsledku v databázi Scopus

2-s2.0-105024123657