FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2009, VOLUME 15, NUMBER 7, PAGES 127-136

**Lower bounds for algebraic complexity of nilpotent associative
algebras**

A. V. Leont'ev

Abstract

View as HTML
View as gif image

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.

Location: http://mech.math.msu.su/~fpm/eng/k09/k097/k09705h.htm

Last modified: April 18, 2010