Algorithmic complexity of linear nonassociative algebra

Abstract

One of the central problems of algebraic complexity theory is the complexity of multiplication in algebras. For this, first, the concept of algebra is defined and the class of algebras under study is fixed. Then the concept of the algorithm and its complexity are clarified. in the most general sense, an algebra is a set with operations. An operation is defined, as a rule, as a function of one or more elements of a set, the set of values of which is the original set or some of its subset. Usually, a set of elementary operations is fixed, for example, a Boolean operation on two bits, addition or multiplication of two numbers, after which a computation model is fixed, for example, a sequential algorithm, at each step of which one elementary operation is performed on some inputs and the results of intermediate calculations, the result of which can be used to enter an elementary operation at subsequent steps of the algorithm. The most significant ones are the column-by-column multiplication algorithm, which has quadratic complexity (along the input length) and the row-by-column matrix multiplication algorithm, which has $O(mnp)$ complexity for multiplying $m \times n$ by $n \times p$ matrices. Estimation of the complexity of algebras from other more complex classes is relevant. in this paper, we derive an estimate for the complexity of a nondegenerate symmetric bilinear form over an algebraic closed field for a simple Jordan algebra, as well as an estimate for a Cayley-Dixon body and for a simple Lie algebra over a characteristic field.

Keywords

• algebra complexity
• optimal algorithm
• simple algebra
• cayley-dixon body
• lie algebra
• characteristic field