DocumentCode
1421556
Title
A Karatsuba-Based Algorithm for Polynomial Multiplication in Chebyshev Form
Author
Lima, Juliano B. ; Panario, Daniel ; Wang, Qiang
Author_Institution
Polytech. Sch. of Pernambuco, Univ. of Pernambuco, Recife, Brazil
Volume
59
Issue
6
fYear
2010
fDate
6/1/2010 12:00:00 AM
Firstpage
835
Lastpage
841
Abstract
In this paper, we present a new method for multiplying polynomials in Chebyshev form. Our approach has two steps. First, the well-known Karatsuba´s algorithm is applied to polynomials constructed by using Chebyshev coefficients. Then, from the obtained result, extra arithmetic operations are used to write the final result in Chebyshev form. The proposed algorithm has a quadratic computational complexity. We also compare our method to other approaches.
Keywords
Chebyshev approximation; computational complexity; interpolation; Chebyshev Form; Chebyshev coefficients; Karatsuba-based algorithm; interpolation techniques; polynomial multiplication; quadratic computational complexity; Algorithm design and analysis; Arithmetic; Chebyshev approximation; Circuit analysis; Computational complexity; Digital filters; Discrete cosine transforms; Interpolation; Polynomials; Roundoff errors; Senior members; Theory of computation; analysis of algorithms and problem complexity; computations on polynomials.;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.2010.45
Filename
5416688
Link To Document