Abstract
In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n 2) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akhiezer, N.I., Krein, M.: Some questions in the theory of moments. Amer. Math. Soc. (1962)
Ben Atti, N., Diaz-Toca, G.M.: Block diagonalization and LU-equivalence of Hankel matrices. Linear Algebra Appl. 412, 247–269 (2006)
Bini, D.: Parallel solution of certain Toeplitz linear systems. SIAM J. Comput. 13, 268–276 (1984)
Bultheel, A., Van Barel, M.: Linear algebra, rational approximation and orthogonal polynomials. In: Studies in Computational Mathematics, vol. 6. Elsevier/North-Holland, Amsterdam (1997)
Bini, D., Pan, V.: Polynomial and matrix computations. Fundamental Algorithms, vol. 1. Birkhäuser (1994)
Gragg, W.B., Lindquist, A.: On partial realization problem. Linear Algebra Appl. 50, 277–319 (1983)
Golub, G.H., Milanfar, P., Varah, J.: A stable numerical method for inverting shape from moments. Technical Report SCCM-97-10, Sei. Comp. and Comp’l. Math. Pgm. Stanford University (1997)
Golub, G., Van Loan, C.: Matrix Computations. 3ème édition. J. Hopkins Univ. Press, Baltimore and London (1996)
Heining, G., Rost, K.: Algebraic Methods for Toeplitz-like Matrices and Operators. Birkhäuser Verlag, Basel (1984)
Heinig, G., Jungnickel, U.: Hankel matrices generated by Markov parameters, Hankel matrix extension, partial realization, and Pade approximation. In: Operator Theory: Advances and Applications, vol. 19, pp. 231–254. Birkhauser, Boston (1986)
Kalman, R.E.: On partial realizations, transfer functions and canonical forms. Acta Polytech. Stand. MA31, 9–32 (1979)
Kung, S.Y.: Multivariable and Multidimensional Systems. Ph.D. thesis, Stanford University, Stanford, CA, (June 1977)
Lin, F.-R., Ching, W.-K., Ng, M.K.: Fast inversion of triangular Toeplitz matrices. Theor. Comp. Sci. 315, 511–523 (2004)
Pal, D.: Fast algorithms for structured matrices with arbitrary rank profile. Ph.D. thesis, Stanford University, Stanford (1990)
Pan, V.Y.: Structured Matrices and Polynomials: Unified Superfast Algorithms. Springer Verlag (2001)
Pan, V.Y., Chen, Z.Q.: Approximate real polynomial division via approximate inversion of real triangular Toeplitz matrices. Appl. Math. Lett. 12, 1–2 (1999)
Pal, D., Kailath, T.: Fast triangular factorization of hankel and related matrices with arbitrary rank profile. SIAM J. Matrix Anal. Appl. 16, 451–478 (1990)
Phillips, J.: The triangular decomposition of Hankel matrices. Math. Comput. 25, 599–602 (1971)
Rissanen, J.: Algorithms for triangular decomposition of block Hankel and Toeplitz matrices with applications to factoring positive polynomials. Math. Comput. 27, 147–154 (1973)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Belhaj, S. A fast method to block-diagonalize a Hankel matrix. Numer Algor 47, 15–34 (2008). https://doi.org/10.1007/s11075-007-9144-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-007-9144-9