A Karatsuba-Based Algorithm for Polynomial Multiplication in Chebyshev Form

作者：Lima Juliano B^*; Panario Daniel; Wang Qiang

来源：IEEE Transactions on Computers, 2010, 59(6): 835-841.

DOI：10.1109/TC.2010.45

• Theory of computation
• analysis of algorithms and problem complexity
• computations on polynomials

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.

• 出版日期2010-6