Scholarlink

<p>Least squares problems with multiple right-hand sides naturally arise in many practical applications. When the system matrix <i>A</i> 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.&#xa0;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 <i>A</i> with a full column rank, this provably prevents breakdowns in block CGLS. For the considered (preconditioned) algorithms, we derive estimates of the <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(A^{T}A\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>A</mi> <mi>T</mi> </msup> <mi>A</mi> </mrow> </math></EquationSource> </InlineEquation>-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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2025年12月8日

查看全文
  • Gérard Meurant,
  • Jan Papež,
  • Petr Tichý

摘要

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 \(A^{T}A\) A T A -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.