A Karatsuba-Based Algorithm for Polynomial Multiplication in Chebyshev Form
- 1 June 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 59 (6) , 835-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
This publication has 9 references indexed in Scilit:
- Volterra Analysis Using Chebyshev Series2007
- Robust Calculation of Chromatic Dispersion Coefficients of Optical Fibers From Numerically Determined Effective Indices Using Chebyshev–Lagrange Interpolation PolynomialsJournal of Lightwave Technology, 2006
- An efficient numerical spectral method for solving the Schrodinger equationComputing in Science & Engineering, 2005
- Five, six, and seven-term Karatsuba-like formulaeIEEE Transactions on Computers, 2005
- Arbitrary Waveform DDFS Utilizing Chebyshev Polynomials InterpolationIEEE Transactions on Circuits and Systems I: Regular Papers, 2004
- Chebyshev interpolation for DMT modems2004
- Fast polynomial multiplication and convolutions related to the discrete cosine transformLinear Algebra and its Applications, 1997
- A new architecture for a parallel finite field multiplier with low complexity based on composite fieldsIEEE Transactions on Computers, 1996
- Direct methods for computing discrete sinusoidal transformsIEE Proceedings F Radar and Signal Processing, 1990