Fast Gaussian elimination with partial pivoting for matrices with displacement structure

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.