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?)

  • [1] G. Ammar and P. Gader, New decompositions of the inverse of a Toeplitz matrix, Signal Processing, Scattering and Operator Theory, and Numerical Methods, Proc. Internat. Sympos. MTNS-89, vol. III, Birkhäuser, Boston, 1990, pp. 421-428. MR 1115471 (92g:65031)
  • [2] J. Ball, I. Gohberg, and L. Rodman, Interpolation of rational matrix functions, OT45, Birkhäuser Verlag, Basel, 1990. MR 1083145 (92m:47027)
  • [3] A. W. Bojanczyk, private communication.
  • [4] A. W. Bojanczyk, R. P. Brent, F. R. de Hoog, and D. R. Sweet, On the stability of the Bareiss and related Toeplitz factorization algorithms, SIAM J. Matrix Anal. Appl. 16 (1995), 40-57. MR 1311417 (95k:65030)
  • [5] E. Bozzo and C. Di Fiore, On the use of certain matrix algebras associated with discrete trigonometric transforms in matrix displacement decomposition, SIAM J. Matrix Anal. Appl. 16 (1994), 312-326. MR 1311435 (96a:65040)
  • [6] J. Chun and T. Kailath, Fast triangularization and orthogonalization of Hankel and Vandermonde matrices, Linear Algebra Appl. 151 (1991), 199-228. MR 1102150 (91m:65118)
  • [7] -, Generalized displacement structure for block-Toeplitz, Toeplitz-block, and Toeplitz-derived matrices, SIAM J. Matrix Anal. Appl. 15 (1994), 114-128. MR 1257621 (95i:65044)
  • [8] G. Cybenko, The numerical stability of Levinson-Durbin algorithm for Toeplitz systems of equations, SIAM J. Sci. Statist. Comput. 1 (1980), 303-319. MR 596026 (82i:65019)
  • [9] I. Gohberg and I. Koltracht, Efficient algorithm for Toeplitz plus Hankel matrices, Integral Equations Operator Theory 12 (1989), 136-142. MR 973051 (89k:65029)
  • [10] I. Gohberg, I. Koltracht, and D. Xiao, On the solution of Yule-Walker equations, Proc. SPIE Conference of Advanced Algorithms and Architectures for Signal Processing IV, vol. 1566, July 1991, pp. 14-22.
  • [11] -, Condition and accuracy of algorithms for computing Schur coefficients of Toeplitz matrices, SIAM J. Matrix Anal. Appl. 15 (1994), 1290-1309. MR 1293918 (95g:65056)
  • [12] I. Gohberg and V. Olshevsky, Circulants, displacements and decompositions of matrices, Integral Equations Operator Theory 15 (1992), 730-743. MR 1177319 (93i:15015)
  • [13] -, Complexity of multiplication with vectors for structured matrices, Linear Algebra Appl. 202 (1994), 163-192. MR 1288487 (95d:65038)
  • [14] -Fast algorithm for matrix Nehari problem, Proc. MTNS-93, Systems and Networks: Mathematical Theory and Applications, vol. 2, Invited and Contributed Papers (U. Helmke, R. Mennicken and J. Sauers, eds.), Akademie Verlag, 1994, pp. 687-690.
  • [15] -, Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems, Integral Equations Operator Theory 20 (1994), 44-83. MR 1290458 (95e:47021)
  • [16] G. Golub and C. Van Loan, Matrix computations, 2nd ed., John Hopkins Univ. Press, Baltimore, MD, 1989. MR 1002570 (90d:65055)
  • [17] G. Heinig, Inversion of generalized Cauchy matrices and other classes of structured matrices, Linear Algebra in Signal Processing, IMA volumes in Mathematics and its Applications, vol. 69, 1994, pp. 95-114. MR 1351733 (96h:65044)
  • [18] G. Heinig, P. Jankowski, and K. Rost, Fast inversion of Toeplitz-plus-Hankel matrices, Numer. Math. 52 (1988), 665-682. MR 946382 (89j:65054)
  • [19] G. Heinig and K. Rost, Algebraic methods for Toeplitz-like matrices and operators, Operator Theory, vol. 13, Birkhäuser, Basel, 1984. MR 782105 (86i:47034b)
  • [20] T. Kailath, Signal processing applications of some moment problems, Moments in Mathematics (H. Landau, ed.), vol. 37, Amer. Math. Soc., Providence, RI, 1987, pp. 71-109. MR 921085 (89e:94001)
  • [21] T. Kailath, S. Kung and M. Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), 395-407. MR 533501 (80k:65029)
  • [22] T. Kailath and V. Olshevsky, Displacement structure approach to Chebyshev-Vandermonde and related matrices, Integral Equations Operator Theory, 1995 (to appear). MR 1327594 (96c:15004)
  • [23] -, Displacement structure approach to polynomial Vandermonde and related matrices, preprint, 1994.
  • [24] T. Kailath and A. H. Sayed, Fast algorithms for generalized displacement structures, Recent Advances in Mathematical Theory of Systems, Control, Networks and Signal Processing II, Proc. MTNS-91 (H. Kimura, S. Kodama, eds.), Mita Press, Japan, 1992, pp. 27-32. MR 1197996
  • [25] -, Displacement structure: theory and applications, SIAM Rev. (to appear). 26. P. Lancaster and M. Tismenetsky, Theory of matrices with applications, 2nd ed., Academic Press, Orlando, 1985. MR 1355506 (96h:15015)
  • [27] H. Lev-Ari and T. Kailath, Triangular factorization of structured Hermitian matrices, Operator Theory: Advances and Applications, (I. Gohberg, ed.), vol. 18, Birkhäuser, Boston, 1986, pp. 301-324. MR 902610 (88i:15030)
  • [28] V. Pan, On computations with dense structured matrices, Math. Comp. 55 (1990), 179-190. MR 1023051 (90m:65085)
  • [29] J. Pasupathy and R. A. Damodar, The Gaussian Toeplitz matrix, Linear Algebra Appl. 171 (1992), 133-147. MR 1165450 (93g:15010)
  • [30] A. Sayed, H. Lev-Ari, and T. Kailath, Fast triangular factorization of the sum of quasi-Toeplitz and quasi-Hankel matrices, Linear Algebra Appl. 191 (1993), 77-106. MR 1233467 (94f:15012)
  • [31] I. Schur, Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind, J. Reine Angew. Math. 147 (1917), 205-232; English transl., Operator Theory: Advances and Applications (I. Gohberg, ed.), vol. 18, Birkhäuser, Boston, 1986, pp. 31-88.
  • [32] J. M. Varah, The prolate matrix, Linear Algebra Appl. 187 (1993), 269-278. MR 1221711 (94e:15058)

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

American Mathematical Society