Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Fast Gaussian elimination with partial pivoting for matrices with displacement structure
HTML articles powered by AMS MathViewer

by I. Gohberg, T. Kailath and V. Olshevsky PDF
Math. Comp. 64 (1995), 1557-1576 Request permission


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.
Similar Articles
Additional Information
  • © Copyright 1995 American Mathematical Society
  • Journal: Math. Comp. 64 (1995), 1557-1576
  • MSC: Primary 15A06; Secondary 15A09, 15A23, 15A57, 65F05
  • DOI:
  • MathSciNet review: 1312096