Unified superfast algorithm for confluent tangential interpolation problems and for structured matrices

Vadim Olshevsky; M. Amin Shokrollahi

doi:10.1117/12.367647

2 November 1999 Unified superfast algorithm for confluent tangential interpolation problems and for structured matrices

Vadim Olshevsky, M. Amin Shokrollahi

Proceedings Volume 3807, Advanced Signal Processing Algorithms, Architectures, and Implementations IX; (1999) https://doi.org/10.1117/12.367647
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1999, Denver, CO, United States

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(n²) 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 log² n) to O(n log³ 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.

Citation Download Citation

Vadim Olshevsky and M. Amin Shokrollahi "Unified superfast algorithm for confluent tangential interpolation problems and for structured matrices", Proc. SPIE 3807, Advanced Signal Processing Algorithms, Architectures, and Implementations IX, (2 November 1999); https://doi.org/10.1117/12.367647

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available