|
Organizers |
Fast and superfast algorithms for matrices generated by orthogonal polynomials
by
Georg Heinig
Kuwait University
Coauthors: Vadim Olshevsky (Georgia State University, Atlanta)
Toeplitz and Hankel matrices can be considered as matrices of restrictions of an operator of multiplication by a polynomial with respect to the power basis. In many applications it is more appropriate to consider other bases than the power basis, in particular bases of orthogonal polynomials. The resulting matrices will be called OP-Hankel matrices. OP-Hankel matrices appear in many situations and applications. They possess a displacement structure, i.e. the rank of AU-UA is small for an appropriately chosen matrix U. In the case of OP-Hankel matrices A will be chosen as tridiagonal matrix.
In the talk we present a new O(n2) complexity Schur-type algorithm, together with some theoretical background, and discuss the possibility for ``superfast'' O(nlog2 n) complexity solvers for OP-Hankel matrices. Note that the Schur-type algorithm does not fit into the general framework of Schur-type algorithms developed before (as in [KS]). We also discuss some modifications of the Levinson-type algorithm in [HHR].
References
[HHR] G. Heinig, W. Hoppe, K. Rost, Structured matrices in interpolation and approximation problems, Wiss. Zeitschr. d. TU Karl-Marx-Stadt 31, 2 (1989), 196-202.
[KS] T. Kailath, A. Sayed, Displacement structure: Theory and applications, SIAM Revue 37 (1995), 297-386.
Date received: February 3, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caeb-98.