Fast Gaussian Elimination with Partial Pivoting
for Matrices with
Displacement Structure
I.Gohberg, T.Kailath and
Vadim Olshevsky
Fast O(n^2) implementation of Gaussian elimination with partial
pivoting is designed
for matrices possessing Cauchy-like displacement structure.
We show how Toeplitz-like, Toeplitz-plus-Hankel-like
and Vandermonde-like matrices
can be transformed into Cauchy-like matrices by using Discrete Fourier,
Cosine or Sine Transform matrices.
In particular this allows us to propose a new fast O(n^2)
Toeplitz solver GKO,
which incorporates partial pivoting. A large set of numerical
examples showed that GKO demonstrated stable numerical behavior and
can be recommended for solving linear systems, especially with
nonsymmetric, indefinite and ill-conditioned positive definite
Toeplitz matrices. It is also useful for block Toeplitz and mosaic
Toeplitz (Toeplitz-block) matrices.
The algorithms proposed in this paper suggest an attractive
alternative to look-ahead approaches, where one has to jump over
ill-conditioned leading submatrices, which in the worse case requires
O(n^3) operations.
Related papers:
The algorithms with partial and diagonal pivoting for
Cauchy-like matrices and for matrices with other types of displacement
structure are suggested in
[GO94a],
( see also [GO94e] for the short version).
Partial pivoting on an ordinary Cauchy matrix can be rapidly performed in advance,
without actually performing elimination, see, e.g.,
[BKO94a], where it was called
predictive partial pivoting.
A transformation of Vandermonde-like and Cauchy-like matrices into
Toeplitz-like matrices was utilized in
[GO94c] to speed-up matrix-vector multiplication
(to this end factor circulant displacements are considered).
An explicit formula to transform polynomial Vandermonde matrix into a Cauchy
matrix appeared in [BKO94a].
Key words:
Gaussian elimination, partial pivoting, displacement structure
Toeplitz-like, Cauchy-like, Vandermonde-like,
Toeplitz-plus-Hankel matrix,
Schur algorithm, Levinson algorithm.
AMS subject classification:
15A06, 15A09, 15A23, 15A57, 65F05, 65H10.
Vadim Olshevsky's Home page
Vadim Olshevsky
olshevsk@isl.stanford.edu
Last modified: Fri Sep 15 1995