Simple C# classes for fast multivariate polynomial symbolic computation – Part III: Polynomial multiplication algorithm and its efficiency

• Autorzy: Sowa M.

Warianty tytułu

PL

Proste klasy w języku C# do obliczeń symbolicznych wielomianów wielu zmiennych – Część III: algorytm mnożenia wielomianów i jego efektywność

• Języki publikacji: EN

Abstrakty

EN

Part I of the paper represented the implementation details of a lightweight C# implementation of symbolic computation of multivariate polynomials. Part II represented the results of an analysis of the numerical efficiency. The current part discusses the multiplication and exponentiation operations. An original algorithm for sparse multivariate polynomial multiplication is proposed. An analysis on polynomial exponentiation is also performed.

PL

Część I niniejszego artykułu zawierała szczegóły prostej implementacji obliczeń symbolicznych wielomianów wielu zmiennych. W części II przedstawiono wyniki analizy efektywności numerycznej. Niniejsza część omawia operacje mnożenia i potęgowania. Zaproponowano oryginalny algorytm do mnożenia rzadkich wielomianów wielu zmiennych. Przeprowadzona jest również analiza na temat potęgowania wielomianów.

Słowa kluczowe

EN

symbolic computation; computation time; C# implementation; polynomial multiplication

PL

obliczenia symboliczne; czas obliczeń; implementacja C#; mnożenie wielomianów

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Prace Naukowe Politechniki Śląskiej. Elektryka
• Rocznik: 2016
• Tom: z. 1
• Strony: 93--103
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Sowa M.

• Silesian University of Technology, Faculty of Electrical Engineering, Institute of Electrical Engineering and Computer Science, ul. Akademicka 10, 44-100, Gliwice

Bibliografia

• 1. Ponder C.G.: Parallel multiplication and powering of polynomials. “Journal of Symbolic Computation” 1991, 11, s.307-320.
• 2. van der Hoeven J., Lecerf G.: On the bit-complexity of sparse polynomial and series multiplication.“Journal of Symbolic Computation” 2013, 50, s.227-254.
• 3. Fateman R.: Comparing the speed of programs for sparse polynomial multiplication. “ACM SIGSAM Bulletin” 2003, 37 (1), s.4-15.
• 4. Harvey D.: A cache-friendly truncated FFT. “Theoretical Computer Science” 2009, 410 (27), s.2649-2658.
• 5. Cenk M., Özbudak F.: Multiplication of polynomials modulo xn. “Theoretical Computer Science” 2011, 412 (29), s.3451-3462.
• 6. Kronecker L.: Grundzüge einer arithmetischen Theorie der algebraischen Grössen. 1882, 92, s.1-122.
• 7. Pan V.Y.: Simple multivariate polynomial multiplication. “Journal of Symbolic Computation” 1994, 18 (3), s.183-186.
• 8. Jia Y.-B.: Polynomial Multiplication and Fast Fourier Transform. “Com S 477/577 Notes” 2014.
• 9. Gentleman W.M., Sande G.: Fast fourier transforms – for fun and profit. “Proc. AFIPS 1966 FJCC 29”, 1966, s.563-578.
• 10. van der Hoeven J.: Notes on the truncated fourier transform. “Tech.Rep. 2005-5”, 2005.
• 11. Monagan M., Pearce R.: Parallel sparse polynomial multiplication using heaps. “Proceedings of the 2009 international symposium on symbolic and algebraic computation. ACM”, 2009, s.263-270.
• 12. Gastineau M., Laskar J.: Development of TRIP: Fast sparse multivariate polynomial multiplication using burst tries. “Computational Science-ICCS” 2006, s.446-453.
• 13. Roche D.S.: Chunky and equal-spaced polynomial multiplication. “Journal of Symbolic Computation” 2011, 46 (7), 791-806.
• 14. Johnson S.C.: Sparse polynomial arithmetic. “ACM SIGSAM Bulletin” 1974, 8(3), s.63-71.
• 15. Monagan M., Pearce R.: Sparse polynomial powering using heaps. “Computer Algebra in Scientific Computing”, Springer, 2012, s.236-247.
• 16. Sowa M., Typańska D.: Pre-assembly for FEM 2D non-curvilinear quadrilateral Lagrangian elements. “Computer Applications in Electrical Engineering” 2014, Vol.12, s.106-119.