Accurate solution of structured linear systems via rank-revealing decompositions
type: Item
instance of: scholarly article
title: Accurate solution of structured linear systems via rank-revealing decompositions
zbMATH Open document ID: 1251.65040
author: Froilán M. Dopico
author: Juan M. Molera
published in: IMA Journal of Numerical Analysis
publication date: 2012-08-17T00:00:00Z
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F35
zbMATH DE Number: 6067216
zbMATH Keywords: accurate solutions
zbMATH Keywords: acyclic matrices
zbMATH Keywords: Cauchy matrices
zbMATH Keywords: diagonally dominant matrices
zbMATH Keywords: graded matrices
zbMATH Keywords: linear systems
zbMATH Keywords: polynomial Vandermonde matrices
zbMATH Keywords: rank-revealing decompositions
zbMATH Keywords: structured matrices
zbMATH Keywords: Vandermonde matrices
zbMATH Keywords: condition number
MaRDI profile type: Publication
full work available at URL: drr023
OpenAlex ID: W2329633813
DOI: 10.1093/IMANUM/DRR023
review text: Systems of linear equations \(Ax=b\), where the matrix \(A\) has some particular structure, arise frequently in applications. Very often, structured matrices have huge condition numbers \(\kappa (A)=\|A^{-1}\| \|A\|\) and, therefore, standard algorithms fail to compute accurate solutions of \(Ax=b\). It is shown in this paper that a computed solution \(\hat x\) is accurate if \(\|\hat x-x\|/\|x\|=\mathcal O(u)\), \(u\) being the unit roundoff. A framework is introduced that allows many classes of structured linear systems to be solved accurately, independently of the condition number of \(A\) and efficiently, that is, with cost \(\mathcal O(n^3)\). The approach in this work relies on first computing an accurate rank-revealing decomposition of \(A\). The new method is illustrated by solving Cauchy and Vandermonde linear systems with any distribution of nodes, that is, without requiring \(A\) to be totally positive for most right-hand sides \(b\).
description: scientific article; zbMATH DE number 6067216