Algorithmic complexity of linear nonassociative algebra
Autor: | Zh. Zhunussova, K. A. Dosmagulova, R. K. Kerimbaev |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2020 |
Předmět: |
characteristic field
Computer science simple algebra QA75.5-76.95 algebra complexity Algebra Algorithmic complexity Electronic computers. Computer science ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION optimal algorithm TJ1-1570 Mechanical engineering and machinery Algebra over a field lie algebra cayley-dixon body |
Zdroj: | Вестник КазНУ. Серия математика, механика, информатика, Vol 107, Iss 3, Pp 20-33 (2020) |
ISSN: | 2617-4871 1563-0277 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |