ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2009, ТОМ 15, ВЫПУСК 7, СТР. 127-136
А. В. Леонтьев
Аннотация
Посмотреть как HTML
Посмотреть как рисунок
В работе рассматриваются точные алгебраические алгоритмы, вычисляющие произведение двух элементов в нильпотентных ассоциативных алгебрах над полями нулевой характеристики (частный случай алгоритмов для одновременного вычисления нескольких полиномов). Сложность алгебры в такой модели вычисления определяется как количество нескалярных умножений оптимального алгоритма (т. е. алгоритма, вычисляющего произведение двух элементов алгебры и имеющего минимальное число нескалярных умножений). Получены нижние оценки тензорного ранга для класса ассоциативных алгебр (в терминах размерностей некоторых фактор-алгебр), которые, в свою очередь, дают нижние оценки сложности алгебраических алгоритмов для этого класса алгебр. Также приведены примеры достижимости полученных оценок для алгебр различных размерностей.
Полнотекстовая версия статьи в формате PDF (130 Kb)
| Главная страница | Содержание журнала | Новости | Поиск |
URL страницы: http://mech.math.msu.su/~fpm/rus/k09/k097/k09705h.htm
Изменения вносились 19 апреля 2010 г.