Polynomial and Rational Evaluation and Interpolation (with Structured Matrices)

摘要: Polynomial and rational interpolation multipoint evaluation are classical subjects, which remain central for the theory practice of algebraic numerical computing have extensive applications to sciences, engineering signal image processing. In spite long intensive study these several major problems remained open. We achieve substantial progress, based on our new matrix representations with use node polynomials. particular: 1. show strong correlation between polynomial as well interpolation, enables unified algorithmic treatment all subjects. 2. real engineering, processing, most important is case where input/output represented in Chebyshev bases. this we rely fast cosine/sine transforms (FCT/FST) decrease arithmetic cost known solutions from order n O(log2 n) per point. 3. general complex case, devise effective approximation algorithms input polynomials degree - 1 sets nodes. The support complexity bounds O(log point approximate solution within output error bound Ɛ = 2-b, log b n), taken relative specified parameters. This substantially improved estimate point. Our supporting cited allow their NC work optimal parallelization. Our results also include exact a) Trummer's problem evaluation, (unlike Gerasoulis algorithm) interpolation-free, b) unknown poles, exploits structure instead customary reduction Euclidean algorithm. Technically, exploit among various transformations (mappings) into each other both associated structured matrices.