|
Фундаментальная и прикладная математика, 2009, том 15, выпуск 7, страницы 127–136
(Mi fpm1273)
|
|
|
|
Нижние оценки алгебраических алгоритмов для нильпотентных ассоциативных алгебр
А. В. Леонтьев Институт программных систем им. А. К. Айламазяна РАН
Аннотация:
В работе рассматриваются точные алгебраические алгоритмы, вычисляющие произведение двух элементов в нильпотентных ассоциативных алгебрах над полями нулевой характеристики (частный случай алгоритмов для одновременного вычисления нескольких полиномов). Сложность алгебры в такой модели вычисления определяется как количество нескалярных умножений оптимального алгоритма (т.е. алгоритма, вычисляющего произведение двух элементов алгебры и имеющего минимальное число нескалярных умножений). Получены нижние оценки тензорного ранга для класса ассоциативных алгебр (в терминах размерностей некоторых фактор-алгебр), которые, в свою очередь, дают нижние оценки сложности алгебраических алгоритмов для этого класса алгебр. Также приведены примеры достижимости полученных оценок для алгебр различных размерностей.
Ключевые слова:
ассоциативные алгебры, точные алгебраические алгоритмы, алгебраическая сложность, тензорный ранг, нижние оценки.
Образец цитирования:
А. В. Леонтьев, “Нижние оценки алгебраических алгоритмов для нильпотентных ассоциативных алгебр”, Фундамент. и прикл. матем., 15:7 (2009), 127–136; J. Math. Sci., 169:5 (2010), 644–650
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/fpm1273 https://www.mathnet.ru/rus/fpm/v15/i7/p127
|
Статистика просмотров: |
Страница аннотации: | 203 | PDF полного текста: | 97 | Список литературы: | 43 | Первая страница: | 1 |
|