By exploiting the
displacement structure of the coefficient matrix
we derive three new algorithms for solving Cauchy
linear systems. One of the suggested schemes matches the
well-known Bjorck-Pereyra algorithm for Vandermonde matrices.
It is shown, that partial pivoting on a Cauchy matrix
can be performed in advance, without actually performing elimination,
by simply reordering of the points, defining the Cauchy matrix.
This ordering, called predictive partial pivoting
matches the well-known Leja ordering for Vandermonde matrices.
In a wide set of experiments these algorithms show
numerical superiority over Gaussian elimination with complete
pivoting, and demonstrate the possibility of computing an
extremely accurate solution even if the coefficient
matrix is ill-conditioned. In particular, we obtain very good results
for solving linear systems with a Hilbert coefficient matrix.
Related papers:
Analogous algorithms for Vandermonde and Chebyshev-Vandermonde
matrices are discussed in [BKO94b].
An a-priori forward error analysis for one of the algorithms, developed
in the present paper is presented in
[BKO95],
giving an explanarion for its high relative accuracy.
Key words: Displacement Structure, Cauchy matrix, Hilbert
matrix, Vandermonde matrix, Chebyshev polynomials, Fast algorithms,
Generalized Schur Algorithm, Partial pivoting, Ordering of interpolation
points.
AMS subject classification: 65F05, 65L20, 15A09, 15A23
Vadim Olshevsky's Home page
