Pivoting and backward stability of fast algorithms for solving Cauchy linear equations

Three fast O(n(2)) algorithms for solving Cauchy linear systems of equations are proposed. A rounding error analysis indicates that the backward stability of these new Cauchy solvers is similar to that of Gaussian elimination, thus suggesting to employ various pivoting techniques to achieve a favorable backward stability. It is shown that Cauchy structure allows one to achieve in O(n(2)) operations partial pivoting ordering of the rows and several other judicious orderings in advance, without actually performing the elimination. The analysis also shows that for the important class of totally positive Cauchy matrices it is advantageous to avoid pivoting, which yields a remarkable backward stability of the suggested algorithms. It is shown that Vandermonde and Chebyshev-Vandermonde matrices can be efficiently transformed into Cauchy matrices, using Discrete Fourier, Cosine or Sine transforms. This allows us to use the proposed algorithms for Cauchy matrices for rapid and accurate solution of Vandermonde and Chebyshev-Vandermonde linear systems. The analytical results are illustrated by computed examples. (C) 2002 Elsevier Science Inc. All rights reserved.