On some computations with dense structured matrices

ABSTRACT

We reduce several computations with Hilbert and Vandermonde type matrices to matrix computations of the Hankel-Toeplitz type (and vice versa). This unifies various known algorithms for computations with dense structured matrices and enables us to extend any progress in computations with matrices of one class to the computations with other classes of matrices. In particular, this enables us to compute the inverses and the determinants of nXn matrices of Vandermonde and Hilbert types for the cost of O(n log2n) arithmetic operations. (Previously, such results were only known for the more narrow class of Vandermonde and generalized Hilbert matrices.)

REFERENCES

• AHU: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• AG,b: Gregory S. Ammar , William B. Gragg, Superfast solution of real positive definite toeplitz systems, SIAM Journal on Matrix Analysis and Applications, v.9 n.1, p.61-76, Jan. 1988 [doi>10.1137/0609005]
• BA: R.R. Bitmead and B.D.O. Anderson, "Asymptotically Fast Solution of Toeplitz and Related Systems of Linear Equations," Linear Algebra and Its Applics., vol. 34, pp. 103-116, 1980.
• BM: A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York, 1975.
• CKL88: J.F. Canny, E. Kaltofen, and Y. Lakshman, "Solving Systems of Non-Linear Polynomial Equations Faster," manuscript, 1988.
• CK: I. Chun and T. Kailath, "Divideand-Conquer Solution of Least- Squares Problems for Matrices with Displacement Structure," manuscript, 1988.
• CKL-A: J. Chun , T. Kailath , H. Lev-Ari, Fast parallel algorithms for QR and triangular factorization, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.899-913, November 1, 1987 [doi>10.1137/0908073]
• Gast60: N. Gastinel, "Inversion d'une Matrice Generalisant la Matrice de Hilbert," Chiffres, vol. 3, pp. 149-152, 1960.
• Ger87: A. Gerasoulis, "A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors," Math. of Computations, vol. 50, 181, pp. 179-188, 1987.
• Gohberg et al.: I. Gohberg, T. Kailath, I. Koltracht, and P. Lancaster, "Linear Complexity Parallel Algorithms for Linear Systems of Equations with Recursive Structure," Linear Algebra and Its Applications, v01. 88/89, pp. 271-315, 1987.
• KC: T. Kailath and J. Chun, "Generalized Gohberg-Semencul Formulas for Matrix Inversion," manuscript, 1988.
• KKM: T. Kailath, S.-Y. Kung, and M. Morf, "Displacement Ranks of Matrices and Linear Equations," J. Math. Anal. Appl., vol. 68,2, pp. 395-407, 1979.
• KVM: T. Kailath, A. Viera, and M. Morf, "Inverses of Toeplitz Operators, Innovations, and Orthogonal Polynomials," SIAM Review, vol. 20,1, pp. 106-119, 1978.
• ODR: S.T. O'Donnell and V. Rokhlin, "A Fast Algorithm for Numerical Evaluation of Conformal Mappings," Research Report RR-554, Yale Univ., Dept. of Computer Science, 1987.
• P88b: V. Pan, "New Effective Methods for Computations with Structured Matrices," Technical Report 88- 28, Computer Science Dept., SUNY Albany, 1988.
• Rokh87: V. Rokhlin, A fast algorithm for the discrete Laplace transformation, Journal of Complexity, v.4 n.1, p.12-32, March 1988 [doi>10.1016/0885-064X(88)90007-6]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Theory