Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast Gaussian elimination with partial pivoting for matrices with displacement structure

Authors: I. Gohberg, T. Kailath and V. Olshevsky
Journal: Math. Comp. 64 (1995), 1557-1576
MSC: Primary 15A06; Secondary 15A09, 15A23, 15A57, 65F05
MathSciNet review: 1312096
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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 worst case requires $ O({n^3})$ operations.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 15A06, 15A09, 15A23, 15A57, 65F05

Retrieve articles in all journals with MSC: 15A06, 15A09, 15A23, 15A57, 65F05

Additional Information

Keywords: Gaussian elimination, partial pivoting, displacement structure, Toeplitz-like, Cauchy-like, Vandermonde-like, Toeplitz-plus-Hankel matrix, Schur algorithm, Levinson algorithm
Article copyright: © Copyright 1995 American Mathematical Society