Lower bounds for algebraic complexity of nilpotent associative algebras

A. V. Leont'ev

Program Systems Institute of RAS

Abstract: 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.

UDC: 512.55

 English version: Journal of Mathematical Sciences (New York), 2010, 169:5, 644–650

Bibliographic databases:

• 
• 
• 
•