Loading...
Please wait, while we are loading the content...
Similar Documents
Polynomial evaluation and interpolation: fast and stable approximate solution.
| Content Provider | CiteSeerX |
|---|---|
| Author | Pan, Victor Y. |
| Abstract | Multipoint polynomial evaluation and interpolation are fundamental for modern algebraic and numerical computing. The known algorithms solve both problems over any field by using O(N log 2 N) arithmetic operations for the input of size N, but the cost grows to quadratic for numerical solution. Our study results in numerically stable algorithms that use O(uN log N) arithmetic time for approximate evaluation (within the relative output error norm 2 −u)and O(uN log 2 N) time for approximate interpolation. The problems are equivalent to multiplication of an n × n Vandermonde matrix by a vector and the solution of a nonsingular Vandermonde linear systems of n equations, respectively. The algorithms and complexity estimates can be also applied where the transposed Vandermonde matrices replace Vandermonde matrices. Our advance is due to employing and extending our earlier method of the transformation of matrix structures, which enables application of the HSS–Multipole method to our tasks and further extension of the algorithms to more general classes of structured matrices. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Polynomial Evaluation Stable Approximate Solution Un Log Vandermonde Matrix Relative Output Error Known Algorithm Approximate Interpolation Numerical Solution Hs Multipole Method Matrix Structure Nonsingular Vandermonde Linear System Multipoint Polynomial Evaluation Modern Algebraic Transposed Vandermonde Matrix Numerical Computing Stable Algorithm Arithmetic Operation General Class Approximate Evaluation Study Result Arithmetic Time Complexity Estimate Structured Matrix Cost Grows |
| Content Type | Text |
