"Записки научных семинаров ПОМИ"
Том 387, стр. 5-52
О сложности решения параметрических полиномиальных систем уравнений
А. Аяд
CEA LIST, Software Safety Laboratory,
Point Courrier 94, Gif-sur-Yvette,
F-91191 France; IRMAR , Campus de Beaulieu
Universit\'e Rennes 1, 35042, Rennes, France
ayadali99100@hotmail.com
- Аннотация:
В работе представлены три алгоритма: первый алгоритм находит решения нульмерных параметрических однородных систем
за экспоненциальное время от количества неизвестных $n%$. Второй алгоритм факторизует параметрические полиномы
от нескольких переменных за экспоненциальное аремя от $n$ и верхней оценки степеней факторизуемых полиномов $d$.
Третьий алгоритм разлагает алгебраическое многообразие положительной размерности,
определенное параметрической системой полиномиальных уравнений, на неприводимые для всех значений
параметров компоненты. Оценка сложности этого алгоритма двойная экспонента от $n$. С другой стороны,
теоретической нижней оценкой задачи разрешения параметрической полиномиальной системы уравнений также является
двойная экспонента от $n$.
Библ. -- 71 назв.
- Ключевые слова: символьные вычисления, анализ сложности,параметрические
полиномы, параметрические польномиальные системы, теория результантов,
полиномиальная факторизация, алгебраические многообразия, неприводимые
компоненты
[Symbolic computation, complexity analysis, parametric polynomials,
parametric polynomial systems, Rational Univariate Representation, theory of
resultants, polynomial factorization, algebraic varieties, irreducible components ]
Полный текст(.pdf)