Geodesic
On the choice of multiplication algorithm for polynomials and polynomial matrices
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XVII, Tome 373 (2009), pp. 157-188 
G. I. Malaschonok; Yu. D. Valeev; A. O. Lapaev. On the choice of multiplication algorithm for polynomials and polynomial matrices. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XVII, Tome 373 (2009), pp. 157-188. http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a10/
@article{ZNSL_2009_373_a10,
     author = {G. I. Malaschonok and Yu. D. Valeev and A. O. Lapaev},
     title = {On the choice of multiplication algorithm for polynomials and polynomial matrices},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {157--188},
     year = {2009},
     volume = {373},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a10/}
}
TY  - JOUR
AU  - G. I. Malaschonok
AU  - Yu. D. Valeev
AU  - A. O. Lapaev
TI  - On the choice of multiplication algorithm for polynomials and polynomial matrices
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2009
SP  - 157
EP  - 188
VL  - 373
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a10/
LA  - ru
ID  - ZNSL_2009_373_a10
ER  - 
%0 Journal Article
%A G. I. Malaschonok
%A Yu. D. Valeev
%A A. O. Lapaev
%T On the choice of multiplication algorithm for polynomials and polynomial matrices
%J Zapiski Nauchnykh Seminarov POMI
%D 2009
%P 157-188
%V 373
%U http://geodesic.mathdoc.fr/item/ZNSL_2009_373_a10/
%G ru
%F ZNSL_2009_373_a10

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

The multiplication algorithm for dense and sparse polynomials and polynomial matrices of different numerical domains are investigated. The expressions for complexity of multiplication operations of polynomials and polynomial matrices are obtained. Each of these expressions is an average of distribution for machine arithmetic operation numbers. Expressions of complexity for a set of parameters which has a practical interest are presented. The results of experiments with the respective programs are demonstrated. Bibl. – 8 titles.

[1] V. Strassen, “Gaussian Elimination is not optimal”, Numer. Math., 13 (1969), 354–356 | DOI | MR | Zbl

[2] A. Akho, Dzh. Khopkroft, Dzh. Ulman, Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR

[3] D. E. Knut, Isskustvo programmirovaniya. T. 2. Poluchislennye algoritmy, 3-e izd., Izdatelskii dom “Vilyams”, M., 2001

[4] G. I. Malashonok, E. S. Satina, “Bystroe umnozhenie i razrezhennye struktury”, Programmirovanie, 2 (2004), 1–5

[5] G. I. Malaschonok, “Complexity Considerations in Computer Algebra”, Computer Algebra in Scientific Computing, CASC 2004, Techn. Univ. Munchen, Garching, Germany, 2004, 325–332

[6] G. I. Malashonok, “Slozhnost bystrogo umnozheniya na razrezhennykh strukturakh”, Algebra, logika i kibernetika, Materialy mezhdunarodnoi konferentsii, Izd-vo GOU VPO “IGPU”, Irkutsk, 2004, 175–177

[7] P. Noden, K. Kitte, Algebraicheskaya algoritmika (s uprazhneniyami i resheniyami), Per. s frants., Mir, M., 1999

[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 2002 | MR