Summary
The solution of systems of linear equations with Hankel coefficient matrices can be computed with onlyO(n 2) arithmetic operations, as compared toO(n 3) operations for the general cases. However, the classical Hankel solvers require the nonsingularity of all leading principal submatrices of the Hankel matrix. The known extensions of these algorithms to general Hankel systems can handle only exactly singular submatrices, but not ill-conditioned ones, and hence they are numerically unstable. In this paper, a stable procedure for solving general nonsingular Hankel systems is presented, using a look-ahead technique to skip over singular or ill-conditioned submatrices. The proposed approach is based on a look-ahead variant of the nonsymmetric Lanczos process that was recently developed by Freund, Gutknecht, and Nachtigal. We first derive a somewhat more general formulation of this look-ahead Lanczos algorithm in terms of formally orthogonal polynomials, which then yields the look-ahead Hankel solver as a special case. We prove some general properties of the resulting look-ahead algorithm for formally orthogonal polynomials. These results are then utilized in the implementation of the Hankel solver. We report some numerical experiments for Hankel systems with ill-conditioned submatrices.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berlekamp, E.R. (1968): Algebraic Coding Theory. McGraw-Hill, New York
Brent, R.P., Gustavson, F.G., Yun, D.Y.Y. (1980): Fast solution of Toeplitz systems of equations and computation of Padé approximants. J. Algorithms1, 259–295
Bultheel, A. (1987): Laurent Series and their Padé Approximations. Birkhäuser, Basel
Cabay, S., Meleshko, R. (1991): A weakly stable algorithm for Padé approximants and the inversion of Hankel matrices. Preprint
Chihara, T.S. (1978): An Introduction to Orthogonal Polynomials. Gordon and Breach, New York, 1978
Chun, J. (1989): Fast array algorithms for structural matrices. Ph.D. Thesis, Stanford University
Citron, T.K. (1986): Algorithms and architectures for error correcting codes. Ph.D. Thesis, Stanford University
Draux, A. (1983): Polynômes Orthogonaux Formels — Applications. Lecture Notes in Mathematics, Vol. 974. Springer. Berlin Heidelberg New York
Freund, R.W., Golub, G.H., Nachtigal, N.M. (1992): Iterative solution of linear systems. Acta Numerica1, 57–100
Freund, R.W., Gutknecht, M.H., Nachtigal, N.M. (1991): An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. Technical Report 91.09, RIACS, NASA Ames Research Center. SIAM J. Sci. Stat. Comput., to appear
Freund, R.W., Zha, H. (1991): Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems. Technical Report 91.27, RIACS, NASA Ames Research Center
Golub, G.H., Van Loan, C.F. (1989): Matrix Computations, Second Edition. The Johns Hopkins University Press, Baltimore
Gragg, W.B. (1972): The Padé table and its relation to certain algorithms of numerical analysis. SIAM Review14, 1–62
Gragg, W.B. (1974): Matrix interpretations and applications of the continued fraction algorithm. Rocky Mountain J. Math.4, 213–225
Gragg, W.B., Gustavson, F.G., Warner, D.D., Yun, D.Y.Y. (1982): On fast computation of superdiagonal Padé fractions. Math. Programming Stud.18, 39–42
Gragg, W.B., Lindquist, A. (1983): On the partial realization problem. Linear Algebra Appl.50, 277–319
Gutknecht, M.H. (1992): A completed theory of the unsymmetric Lanczos process and related algorithms, Part I. SIAM J. Matrix Anal. Appl.13, 549–639
Gutknecht, M.H. (1990): A completed theory of the unsymmetric Lanczos process and related algorithms, Part II. IPS Research Report No. 90-16, ETH Zürich
Heinig, G., Rost, K. (1984): Algebraic Methods for Toeplitz-like Matrices and Operators. Birkhäuser, Basel
Jonckheere, E., Ma, C. (1989): A simple Hankel interpretation of the Berlekamp-Massey algorithm. Linear Algebra Appl.125, 65–76
Kailath, T. (1980): Linear Systems. Prentince-Hall, Englewood Cliffs
Kalman, R.E. (1979): On partial realizations, transfer functions, and canonical forms. Acta Polytech. Scand. Math. Comput. Sci. Ser.31, 9–32
Kalman, R.E., Falb, P.L., Arbib, M.A. (1969): Topics in Mathematical System Theory. McGraw-Hill, New York
Kung, S.-Y. (1977): Multivariable and multidimensional systems: analysis and design. Ph.D. Dissertation, Stanford University
Lanczos, C. (1950): An iteration method for the solution of the eigen value problem of linear differential and integral operators. J. Res. Natl. Bur. Stand.45, 255–282
Lev-Ari, H., Kailath, T. (1986): Triangular factorization of structured Hermitian matrices. In: I. Gohberg, ed., I. Schur Methods in Operator Theory and Signal Processing. Operator Theory Adv. Appl.18, 301–324. Birkhäuser, Basel
Massey, J.L. (1969): Shift-register synthesis and BCH decoding. IEEE Trans. Inform TheoryIT-15, 122–127
Parlett, B.N., Taylor, D.R., Liu, Z.A. (1985): A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp.44, 105–124
Phillips, J.L. (1971): The triangular decomposition of Hankel matrices. Math. Comp.25, 599–602
Rissanen, J. (1973/74): Solution of linear equations with Hankel and Toeplitz matrices. Numer. Math.22, 361–366
Trench, W. (1965): An algorithm for the inversion of finite Hankel matrices. J. Soc. Indust. Appl. Math.13, 1102–1107
Author information
Authors and Affiliations
Additional information
The research of the first author was supported by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).
The research of the second author was supported in part by NSF grant DRC-8412314 and Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).