Author： Leont’ev A.
Publisher： Springer Publishing Company
ISSN： 1072-3374
Source： Journal of Mathematical Sciences, Vol.169, Iss.5, 2010-09, pp. : 644-650
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
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 these estimates for different dimensions of nilpotent algebras are presented.
Related content
Lower Bounds for Dynamic Algebraic Problems
By Frandsen G.S. Hansen J.P. Miltersen P.B.
Information and Computation, Vol. 171, Iss. 2, 2001-12 ,pp. :
Access to resources
Recommend
Propositional lower bounds: Algorithms and complexity
By Cadoli M.
Annals of Mathematics and Artificial Intelligence, Vol. 27, Iss. 1-4, 1999-01 ,pp. :
Lower Bounds for the Complexity of Functions in a Realistic RAM Model
By Bshouty N.H.
Journal of Algorithms, Vol. 32, Iss. 1, 1999-07 ,pp. :
Hilbert Function and Complexity Lower Bounds for Symmetric Boolean Functions
Information and Computation, Vol. 153, Iss. 1, 1999-08 ,pp. :