A fast parallel Bjorck-Pereyra-type algorithm for solving Cauchy linear equations

We propose a new fast O(n(2)) parallel algorithm for solving Cauchy systems of linear equations, We perform an a priori rounding error analysis and ob tain componentwise bounds for the forward, backward and residual errors. Th ese bounds indicate that for the class of totally positive Cauchy matrices the new algorithm is forward and backward stable, producing a remarkably hi gh relative accuracy. In particular, Hilbert linear systems, often consider ed to be too ill-conditioned to be attacked, can be rapidly solved with hig h precision. The results indicate a close resemblance between the numerical properties of Cauchy matrices and the much-studied Vandermonde matrices. I n fact, our proposed Cauchy solver is an analog of the well-known Bjorck-Pe reyra algorithm for Vandermonde systems.As a by-product we obtain favorably backward error bounds for the original Bjorck-Pereyra algorithm. Several c omputed examples illustrate a connection of high relative accuracy to the c oncepts of effective well-conditioning and total positivity. (C) 1999 Publi shed by Elsevier Science Inc. All rights reserved.