Fast Evaluation and Interpolation,
Abstract
A method for dividing a polynomial of degree (2n-1) by a precomputed nth degree polynomial in 0(n log n) arithmetic operations is given. This is used to prove that the evaluation of an nth degree polynomial at n+1 arbitrary points can be done in 0(n (log sup 2) n) arithmetic operations, and consequently, its dual problem, interpolation of an nth degree polynomial from n+1 arbitrary points can be performed in 0(n (log sup 2) n) arithmetic operations. The best previously known algorithms required 0(n (log sup 3) n) arithmetic operations. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1973
- Accession Number
- AD0755451
Entities
People
- H. T. Kung
Organizations
- Carnegie Mellon University