Geodesic
Lower bounds for algebraic complexity of nilpotent associative algebras
Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 7, pp. 127-136.

Voir la notice de l'article provenant de la source Math-Net.Ru

Exact algebraic algorithms for calculating the product of two elements of nilpotent associative algebras over fields of characteristic zero are considered (this is a particular case of simultaneous calculation of several multinomials). The complexity of an algebra in this computational model is defined as the number of nonscalar multiplications of an optimal algorithm. Lower bounds for the tensor rank of nilpotent associative algebras (in terms of dimensions of certain subalgebras) are obtained, which give lower bounds for the algebraic complexity of this class of algebras. Examples of reaching of these estimates for different dimensions of the nilpotent algebras are presented. 
@article{FPM_2009_15_7_a4,
     author = {A. V. Leont'ev},
     title = {Lower bounds for algebraic complexity of nilpotent associative algebras},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {127--136},
     publisher = {mathdoc},
     volume = {15},
     number = {7},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2009_15_7_a4/}
}
TY  - JOUR
AU  - A. V. Leont'ev
TI  - Lower bounds for algebraic complexity of nilpotent associative algebras
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2009
SP  - 127
EP  - 136
VL  - 15
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2009_15_7_a4/
LA  - ru
ID  - FPM_2009_15_7_a4
ER  - 
%0 Journal Article
%A A. V. Leont'ev
%T Lower bounds for algebraic complexity of nilpotent associative algebras
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2009
%P 127-136
%V 15
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2009_15_7_a4/
%G ru
%F FPM_2009_15_7_a4
A. V. Leont'ev. Lower bounds for algebraic complexity of nilpotent associative algebras. Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 7, pp. 127-136. http://geodesic.mathdoc.fr/item/FPM_2009_15_7_a4/

[1] Zhoshina S. A., “O multiplikativnoi slozhnosti algebr Li”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 1990, no. 4, 75–77 | MR | Zbl

[2] Zhoshina S. A., “O multiplikativnoi slozhnosti prostykh algebr Li $G_2$, $F_4$, $E_6$, $E_7$, $E_8$ i poluprostykh algebr Li”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 1993, no. 4, 35–37 | MR | Zbl

[3] Latyshev V. N., Kombinatornaya teoriya kolets. Slozhnost algebraicheskikh algoritmov, Izd-vo Mosk. un-ta, M., 1988 | MR | Zbl

[4] Leontev A. V., “Nizhnie otsenki algebraicheskoi slozhnosti dlya klassicheskikh prostykh algebr Li”, Mat. sb., 199:5 (2008), 27–34 | DOI | MR | Zbl

[5] Alder A., Strassen V., “On the algorithmic complexity of the associative algebras”, Theor. Comput. Sci., 15 (1981), 201–211 | DOI | MR | Zbl