On the Polynomial Multiplication in Chebyshev Form

Akleylek S., Cenk M., ÖZBUDAK F.

IEEE TRANSACTIONS ON COMPUTERS, cilt.61, sa.4, ss.584-587, 2012 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 61 Sayı: 4
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1109/tc.2011.38
  • Dergi Adı: IEEE TRANSACTIONS ON COMPUTERS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.584-587
  • Anahtar Kelimeler: Chebyshev polynomials, theory of computation, multiplication of polynomials, arithmetic complexity., INTERPOLATION
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We give an efficient multiplication method for polynomials in Chebyshev form. This multiplication method is different from the previous ones. Theoretically, we show that the number of multiplications is at least as good as Karatsuba-based algorithm. Moreover, using the proposed method, we improve the number of additions slightly. We remark that our method works efficiently for any N and it is easy to implement. To the best of our knowledge, the proposed method has the best multiplication and addition complexity for the N-term polynomial multiplication in Chebyshev form with 3 <= N <= 13.