Lower bounds for algebraic algorithms for nilpotent and solvable Lie algebras

A. V. Leont'ev

University of Pereslavl, Pereslavl-Zalessky, Yaroslavl region, Russia

Abstract: We obtain the lower bounds for the tensor rank for the class of nilpotent and solvable Lie algebras (in terms of dimensions of certain quotient algebras). These estimates, in turn, give lower bounds for the complexity of algebraic algorithms for this class of algebras. We adduce examples of attainable estimates for nilpotent Lie algebras of various dimensions.

Keywords: nilpotent Lie algebras, solvable Lie algebras, exact algebraic algorithms, algebraic complexity, tensor rank, lower bounds.

UDC: 512.55

Received: 28.11.2007

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:3, 12–18

Bibliographic databases:

• 
• 
•