Алгоритмическая сложность некоторых линейных неассоциативных алгебр

Авторы

  • R. K. Kerimbaev Казахский национальный университет имени аль-Фараби, г. Алматы, Казахстан http://orcid.org/0000-0003-4615-741X
  • K. A. Dosmagulova Казахский национальный университет имени аль-Фараби, г. Алматы, Казахстан http://orcid.org/0000-0001-8289-6573
  • Zh. Kh. Zhunussova Казахский национальный университет имени аль-Фараби, г. Алматы, Казахстан http://orcid.org/0000-0003-1256-1027

DOI:

https://doi.org/10.26577/JMMCS.2020.v107.i3.03

Ключевые слова:

сложность алгебры, оптимальный алгоритм, простая алгебра, тело Кэли-Диксона, алгебра Ли, характеристическое поле

Аннотация

Одной из центральных задач алгебраической теории сложности является сложность умножения в алгебрах. Для этого сначала определяется понятие алгебры и фиксируется класс изучаемых алгебр. Затем уточняется понятие алгоритма и его сложности.
В наиболее общем смысле алгеброй называется множество с операциями. Операция определяется, как правило, как функция одного или нескольких элементов множества, множеством значений которой является исходное множество или некоторое его подмножество. Обычно фиксируется некоторое множество элементарных операций, например, булева операция над двумя битами, сложение или умножение двух чисел, после чего фиксируется модель вычислений, например, последовательный алгоритм, на каждом из шагов которого выполняется одна элементарная операция над некоторыми входами и результатами промежуточных вычислений, результат которой может быть использован для входа элементарной операции на последующих шагах алгоритма.
К наиболее значимым следует отнести алгоритм умножения чисел "в столбик", имеющий квадратичную сложность (по длине входа) и алгоритм умножения матриц "строка на столбец", имеющий сложность $O(mnp)$ для умножения матриц размера $m\times n$ на $n \times p$.
Оценка сложности алгебр из других более сложных классов актуальна. В данной статье мы выводим оценку сложности невырожденной симметрической билинейной формы над алгебраическим замкнутым полем для простой йордановой алгебры, а также оценку для тела Кэли-Диксона и простой алгебры Ли над характеристическим полем.

Библиографические ссылки

[1] A. Alder, Shtrassen F. "Algorithmic complexity of linear algebra. Algorithms in the modern mathematics and its applications 2 (1978): 124.

[2] K.A. Zhevlakov, A.M. Slinko, I.P. Shestakov, A.I. Shirshov, "Rings, closed to associative M.: Science. (1978).

[3] V. Strassen, "Vermeidung Von Divissionen I. fur reine und angew. Mathematik. 264 (1973): 184–202.

Загрузки

Опубликован

2020-09-30