Breakdown and near-breakdown control in the CGS algorithm using stochastic arithmetic
type: Item
instance of: scholarly article
title: Breakdown and near-breakdown control in the CGS algorithm using stochastic arithmetic
zbMATH Open document ID: 0847.65017
DOI: 10.1007/BF02142491
author: Jean-Marie Chesneaux
author: Ana C. Matos
published in: Numerical Algorithms
publication date: 1996-10-13T00:00:00Z
review text: The aim of this paper is to show how using stochastic arithmetic the problem with near-breakdown can be eliminated. In the conjugate gradient squared (CGS) method (which is a variant of the Lanczos method), a sequence of residuals \(r_k= P^2_k (A) r_0\) has to be computed. The coefficients of the orthogonal matrix polynomials \(P_k (A)\) are given by ratios of scalar products. However, when some of the scalar products appearing in the demoninators are badly computed, then rounding errors can affect all the computations -- a typical situation of near-breakdown. In specific computations, due to the finite precision one cannot distinguish between breakdown and near-breakdown. Recurrence formulas for orthogonal polynomials in order to avoid near-breakdown in CGS algorithm have been proposed by C. Brezinski and M. Redivo-Zagaria, but some choices have to be made: when to jump and what is the size of the jump. In this paper, the authors present an algorithm using stochastic arithmetic where the computer decides whether to jump or not and how far. Some numerical results showing the good numerical properties of the proposed algorithm are given. This techniques can be applied to different algorithms involving recurrence relations for orthogonal polynomials and can be useful in detecting and controlling numerical instabilities.
reviewed by: Krassimir Georgiev
Mathematics Subject Classification ID: 65F10
zbMATH DE Number: 871277
zbMATH Keywords: conjugate gradient squared method
zbMATH Keywords: Lanczos method
zbMATH Keywords: orthogonal matrix polynomials
zbMATH Keywords: near-breakdown
zbMATH Keywords: stochastic arithmetic
zbMATH Keywords: numerical results
zbMATH Keywords: recurrence relations
zbMATH Keywords: controlling numerical instabilities
describes a project that uses: na5
describes a project that uses: na1
describes a project that uses: CGS
MaRDI profile type: Publication
cites work: Padé-type approximation and general orthogonal polynomials
cites work: A new presentation of orthogonal polynomials with applications to their computation
cites work: Lanczos-type algorithms for solving systems of linear equations
cites work: Treatment of near-breakdown in the CGS algorithm
cites work: Q4697161
cites work: The equality relations in scientific computing
cites work: Polynômes orthogonaux formels - applications
cites work: CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems
cites work: New methods for evaluating the validity of the results of mathematical computations
full work available at URL: https://doi.org/10.1007/bf02142491
OpenAlex ID: W2030342534
description: scientific article; zbMATH DE number 871277