
Accession Number : AD0755451
Title : Fast Evaluation and Interpolation,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Kung,H. T.
Report Date : JAN 1973
Pagination or Media Count : 14
Abstract : A method for dividing a polynomial of degree (2n1) 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)
Descriptors : (*POLYNOMIALS, *INTERPOLATION), COMPLEX NUMBERS, ALGORITHMS, THEOREMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE