Accurate solution of structured linear systems via rank-revealing decompositions (Q2902204)

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\).