"Записки научных семинаров ПОМИ"
Том 528, стр. 261-290
Алгоритм для факторизации многочленов в кольце формальных степенных
рядов от многих переменных в нулевой характеристике. II
А. Л. Чистов
Санкт-Петербургское отделение
Математического института им. В. А. Стеклова
Российской академии наук,
наб. р. Фонтанки 27,
191023 Санкт-Петербург
alch@pdmi.ras.ru
Laboratory of Information Technologies,
Joint Institute for Nuclear Research,
141980 Dubna, Russia;
A. I. Alikhanyan National Science Laboratory (YerPhI),
Yerevan, Armenia
astghik@jinr.ru
- Аннотация:
Мы улучшаем алгоритмы для факторизации многочленов
в (и над) кольцами формальных степенных рядов от многих переменных,
предложенные в первой части статьи.
Для этого мы используем эффективную версию теоремы Бертини для полных
локальных областей целостности. В результате теперь сложность каждого из
построенных алгоритмов полиномиальна от длины записи входных данных
(в естественном смысле).
Библ. -- 17 назв.
- Ключевые слова:
формальные степенные ряды, факторизация многочленов, многие переменные,сложность алгоритмов
[formal power series, factoring polynomials, many variables,
complexity of the algorithms]
Полный текст(.pdf)