Share Email Print

Proceedings Paper

Unified superfast algorithm for confluent tangential interpolation problems and for structured matrices
Author(s): Vadim Olshevsky; M. Amin Shokrollahi
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

The classical Caratheodory-Fejer and Nevanlinna-Pick interpolation problems have a long and distinguished history, appearing in a variety of applications in mathematics and electrical engineering. It is well-known that these problems can be solved in O(n2) operations, where n is the overall multiplicity of interpolation points. In this paper we suggest a superfast algorithm for solving the more general confluent tangential interpolation problem. The cost of the new algorithm varies from O(n log2 n) to O(n log3 n), depending on the multiplicity pattern of the interpolation points. The new algorithm can be used to factorize, invert, and solve a linear system of equations with confluent- Cauchy-like matrices. This class of matrices includes Hankel-like (i.e., permuted Toeplitz-like), Vandermonde-like and Cauchy-like matrices as special cases. An important ingredient of the proposed method is a new fast algorithm to compute a product of a confluent- Cauchy-like matrix by a vector.

Paper Details

Date Published: 2 November 1999
PDF: 12 pages
Proc. SPIE 3807, Advanced Signal Processing Algorithms, Architectures, and Implementations IX, (2 November 1999); doi: 10.1117/12.367647
Show Author Affiliations
Vadim Olshevsky, Georgia State Univ. (United States)
M. Amin Shokrollahi, Lucent Technologies/Bell Labs. (United States)

Published in SPIE Proceedings Vol. 3807:
Advanced Signal Processing Algorithms, Architectures, and Implementations IX
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top