Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On computations with dense structured matrices

Author: Victor Pan
Journal: Math. Comp. 55 (1990), 179-190
MSC: Primary 65F30
MathSciNet review: 1023051
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ n \times n$ matrices of Vandermonde and Hilbert types for the cost of $ O(n{\log ^2}n)$ arithmetic operations. (Previously, such results were only known for the more narrow class of Vandermonde and generalized Hilbert matrices.)

References [Enhancements On Off] (What's this?)

  • [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1976. MR 0413592 (54:1706)
  • [2] G. S. Ammar and W. G. Gragg, Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 9 (1988), 61-76. MR 938136 (89b:65065)
  • [3] C. R. Anderson, A method of local corrections for computing the velocity field due to a distribution of vortex blobs, J. Comput. Phys. 62 (1986), 111-123. MR 825893 (87d:76050)
  • [4] A. W. Appel, An efficient program for many-body simulation, SIAM J. Sci. Statist. Comput. 6 (1985), 85-103. MR 773283 (85m:85001)
  • [5] J. Barnes and P. Hut, A hierarchical $ O(N\log N)$ force-calculation algorithm, Nature 324 (1986), 446-449.
  • [6] R. R. Bitmead and B. D. O. Anderson, Asymptotically fast solution of Toeplitz and related systems of linear equations, Linear Algebra Appl. 34 (1980), 103-116. MR 591427 (81m:65044)
  • [7] A. Borodin and I. Munro, The computational complexity of algebraic and numeric problems, American Elsevier, New York, 1975. MR 0468309 (57:8145)
  • [8] J. F. Canny, E. Kaltofen, and Y. Lakshman, Solving systems of non-linear polynomial equations faster, Proc. ACM-SIGSAM Internat. Symposium on Symbolic and Algebraic Computations, ACM, New York, 1989, pp. 34-42.
  • [9] J. Chun and T. Kailath, Divide-and-conquer solution of least-squares problems for matrices with displacement structure, SIAM J. Matrix Anal. Appl. (submitted). MR 1082331 (91m:65078)
  • [10] J. Chun, T. Kailath, and H. Lev-Ari, Fast parallel algorithm for QR-factorization of structured matrices, SIAM J. Sci. Statist. Comput. 8 (1987), 899-913. MR 911062 (89e:65035)
  • [11] N. Gastinel, Inversion d'une matrice généralisant la matrice de Hilbert, Chiffres 3 (1960), 149-152. MR 0123585 (23:A910)
  • [12] A. Gerasoulis, A fast algorithm for the multiplication of generalized Hilbert matrices with vectors, Math. Comp. 50 (1987), 179-188. MR 917825 (88j:65084)
  • [13] I. Gohberg, T. Kailath, and I. Koltracht, Efficient solution of linear systems of equations with recursive structure, Linear Algebra Appl. 80 (1986), 81-113. MR 851934 (87i:65058)
  • [14] I. Gohberg, T. Kailath, I. Koltracht, and P. Lancaster, Linear complexity parallel algorithms for linear systems of equations with recursive structure, Linear Algebra Appl. 88/89 (1987), 271-315. MR 882451 (88g:65027)
  • [15] G. Heining and K. Rost, Algebraic methods for Toeplitz-like matrices and operators, Operator Theory, vol. 13, Birkhäuser, 1984.
  • [16] T. Kailath and J. Chun, Generalized Gohberg-Semencul formulas for matrix inversion, Operator Theory: Advances and Applications, vol. 40, Birkhäuser, 1989, pp. 231-246. MR 1038316 (90m:15006)
  • [17] T. Kailath, S.-Y. Kung, and M. Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), 395-407. MR 533501 (80k:65029)
  • [18] T. Kailath, A. Viera, and M. Morf, Inverses of Toeplitz operators, innovations, and orthogonal polynomials, SIAM Rev. 20 (1978), 106-119. MR 0512865 (58:23722)
  • [19] A. Leonard, Vortex methods for flow simulation, J. Comput. Phys. 37 (1980), 289-335. MR 588256 (81i:76016)
  • [20] B. R. Musicus, Levinson and fast Choleski algorithms for Toeplitz and almost Toeplitz matrices, Internal Report, Lab. of Electonics, M.I.T., 1981.
  • [21] 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.
  • [22] A. M. Odlyzko and A. Schönhage, Fast algorithms for multiple evaluations of the Riemann zeta function, Trans. Amer. Math. Soc. 309 (1988), 797-809. MR 961614 (89j:11083)
  • [23] V. Pan, New effective methods for computations with structured matrices, Technical Report 88-28, Computer Science Dept., SUNY Albany, 1988.
  • [24] -, Fast and efficient parallel inversion of Toeplitz and block Toeplitz matrices, Operator Theory: Advances and Applications, vol. 40, Birkhäuser, 1989, pp. 359-389. MR 1038320 (91d:65055)
  • [25] -, Parallel least-squares solution of general and Toeplitz-like linear systems, manuscript, 1990.
  • [26] F. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Phys. 60 (1985), 187-207. MR 805870 (86k:65120)
  • [27] V. Rokhlin, A fast algorithm for the discrete Laplace transform, J. Complexity 4 (1988), 12-32. MR 939693 (89b:65309)
  • [28] M. Tismenetsky, Bésoutians, Toeplitz and Hankel matrices in the spectral theory of matrix polynomials, Ph.D. thesis, Technion, Haifa, 1981.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

Keywords: Dense structured matrices, algorithms, displacement rank, Hilbert, Vandermonde, Toeplitz and Hankel matrices
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society