FORTRAN subroutines for general Toeplitz systems

ABSTRACT

This paper presents FORTRAN 77 implementations of the lookahead Levinson algorithm of Chan and Hansen [7, 8] for solving symmetric indefinite and general Toeplitz systems. The algorithms are numerically stable for all Toeplitz matrices that do not have many consecutive ill-conditioned leading principal submatrices, and also produce estimates of the algorithm and matrix condition numbers. In contrast, the classical Levinson algorithm is only guaranteed to be numerically stable for symmetric positive definite Toeplitz matrices, and no condition estimate is produced.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: ARUSHANIAN, O. B., SAMARIN, M. K., VOEVODIN, V. V., TYRTYSHNIKOV, E. ~}., GARBOW, B. S., BOYLE, J. M., COWELL, W. R., AND DRI?Z, K.W. The Toeplitz Package Users' Guide. Rep. ANL-83-16, Argonne National Lab., 1983.
• 3: BRENT, R.P. Old and new algorithms for Toeplitz systems. In Advanced Algorithms and Architectures for Signal Processing III, F. T. Luk, Ed., Proc. SPIE 975 (1988), 2-9.
• 4: BRENT, R. P.~ LUK, F. T., AND VAN LOAN, C.F. Computation of the singular value decomposition using mesh-connected processors. J VLSI Coraput. Syst. I (1985), 242-270.
• 5: BUNCH, J.R. Stability of methods for solving Toeplitz systems. SIAM J Sci. Stat. Comput. 6, 2 (Mar. 1985), 349-364.
• 6: CADZOW, J. A., AND CHEN~ T.-C. Application of Toeplitz eigenvalue decomposition in digital filter synthesis. IEEE ASSSP-37 (1989), 655-664.
• 7: Tony F. Chan , Per Christian Hansen, A look-ahead Levinson algorithm for indefinite Toeplitz systems, SIAM Journal on Matrix Analysis and Applications, v.13 n.2, p.490-506, April 1992 [doi>10.1137/0613032]
• 8: CHAN, T. F., AND HANSEN, P. C. A lookahead Levinson algorithm for general Toeplitz systems. CAM Rep. 90-11, Dept. of Mathematics, UCLA; to appear in IEEE $P
• 9: George Cybenko , Charles Van Loan, Computing thr minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.123-131, Jan. 1986 [doi>10.1137/0907009]
• 10: DAHLQUIST, G.. BJGRCK, A, AND ANDERSON, N. Numerical Methods. Prentme Hall, Englewood Cliffs, N.J., 1974.
• 11: DELSARTE, P., GEN1N, Y. V., AND KAMP, Y.G. A generalization of the Levinson algorithm for Hermitian Toeplltz matrices with any rank profile. IEEE ASSP-33, 4 (Aug. 1987), 964-971.
• 12: DEMEURE, C. J., AND SCHARF, L.L. Linear statistical methods for stationary sequences and related algorithms for Cholesky factorization of Toeplitz matrices. IEEE ASSP-35, 1 (Jan. 1987)~ 29 42.
• 13: DONGARRA, J. J., BUNCH, J. R., MOLER, C. B., AND STEWART, G.W. Linpack Users' Guide. SIAM, Philadelphia, Pa., 1979.
• 14: GOLUB, G. H., AND VAN LOAN, C.F. Matrix ComputatLons, 2rid ed.. Johns Hopkins University Press, Baltimore, Md., 1989.
• 15: COVER, M. J. C., AND BARNETT, S. Inversion of Toeplitz matrices which are not strongly non-singular. IMA J. Numer. Anal. 5~ 1 (Jan. 1985), 101-110.
• 16: GRIMES, R. G., AND LEWIS, J.G. Condition number estimation for sparse matrices. SIAM J. Sct. Stat. Comput. 2, 4 (Dec. 1981), 384-388.
• 17: IMSL Math/Library User's Manual. IMSL, 1987.
• 18: KAILATH, T. A view of three decades of linear filtering theory. IEEE IT-20 (1974), 145-181.
• 19: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 20: LEVINSON, N. The Wiener rms (root mean square) error criterion in filter design and prediction. J. Moth. Phys. 25 (1947l, 261-278.
• 21: PRESS, W. H., FLANNERY, g. P., TEUKOLSKI, S. A., AND VETTERLING, W.T. Numerical Rectpes. Cambridge University Press, 1987.
• 22: SWEET, D.R. The use of pivoting to improve the numerical performance of Toeplitz solvers. In Advanced Algorithms and Architectures for Signal Processing, J. M. Speiser, Ed., Proceedings SPIE 696 (1986), 8-18.
• 23: William F. Trench, Numerical solution of the eigenvalue problem for symmetric rationally generated Toeplitz matrices, SIAM Journal on Matrix Analysis and Applications, v.9 n.2, p.291-303, April 1988 [doi>10.1137/0609023]
• 24: TYRTYSHNIKOV, E.E. New cost-efficient and fast algorithms for special classes of Toeplitz systems. Soy. J. Numer. Anal. Model. 3, i (Jan. 1988), 63 76.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Performance

Keywords:
Levinson's algorithm, Toeplitz systems, condition estimation