Система полиномиальных уравнений

Корни множественных многомерных полиномов

Система полиномиальных уравнений (иногда просто полиномиальная система ) — это набор одновременных уравнений f ₁ = 0, ..., f _h = 0 , где f _i — полиномы от нескольких переменных, скажем, x ₁ , ..., x _n , над некоторым полем k .

Решение полиномиальной системы — это набор значений для x _i s , которые принадлежат некоторому алгебраически замкнутому расширению поля K поля k и делают все уравнения верными. Когда k — поле рациональных чисел , K обычно считается полем комплексных чисел , поскольку каждое решение принадлежит расширению поля k , которое изоморфно подполю комплексных чисел.

В этой статье речь идет о методах решения, то есть нахождения всех решений или их описания. Поскольку эти методы предназначены для реализации на компьютере, акцент делается на областях k, в которых вычисления (включая проверку равенства) просты и эффективны, то есть в области рациональных чисел и конечных полей .

Поиск решений, принадлежащих определенному множеству, является задачей, которая, как правило, гораздо сложнее и выходит за рамки данной статьи, за исключением случая решений в заданном конечном поле. Для случая решений, все компоненты которых являются целыми или рациональными числами, см. Диофантово уравнение .

Определение

Многочисленные особые точки секстики Барта являются решениями полиномиальной системы

Простой пример системы полиномиальных уравнений:

${\displaystyle {\begin{aligned}x^{2}+y^{2}-5&=0\\xy-2&=0.\end{aligned}}}$

Его решениями являются четыре пары ( x , y ) = (1, 2), (2, 1), (-1, -2), (-2, -1) . Эти решения можно легко проверить подстановкой, но для доказательства отсутствия других решений потребуется больше работы.

Предметом данной статьи является изучение обобщений таких примеров и описание методов, используемых для вычисления решений.

Система полиномиальных уравнений, или полиномиальная система, представляет собой совокупность уравнений

${\displaystyle {\begin{aligned}f_{1}\left(x_{1},\ldots ,x_{m}\right)&=0\\&\;\;\vdots \\f_{n}\left(x_{1},\ldots ,x_{m}\right)&=0,\end{aligned}}}$

где каждый f _h является многочленом от неопределенных x ₁ , ..., x _m , с целыми коэффициентами или коэффициентами в некотором фиксированном поле , часто поле рациональных чисел или конечное поле . ^[1] Другие поля коэффициентов, такие как действительные числа , используются реже, так как их элементы не могут быть представлены на компьютере (в вычислениях можно использовать только приближения действительных чисел, и эти приближения всегда являются рациональными числами).

Решением полиномиальной системы называется набор значений ( x ₁ , ..., x _m ) , удовлетворяющий всем уравнениям полиномиальной системы. Решения ищутся в комплексных числах или, в более общем случае, в алгебраически замкнутом поле, содержащем коэффициенты. В частности, в нулевой характеристике ищутся все комплексные решения . Поиск действительных или рациональных решений — гораздо более сложные задачи, которые в этой статье не рассматриваются.

Множество решений не всегда конечно; например, решения системы

${\displaystyle {\begin{aligned}x(x-1)&=0\\x(y-1)&=0\end{aligned}}}$

представляют собой точку ( x , y ) = (1,1) и прямую x = 0. [ ^2] Даже когда множество решений конечно, в общем случае не существует замкнутого выражения решений (в случае одного уравнения это теорема Абеля–Руффини ).

Поверхность Барта , показанная на рисунке, является геометрическим представлением решений полиномиальной системы, сведенной к одному уравнению степени 6 с 3 переменными. Некоторые из ее многочисленных особых точек видны на изображении. Они являются решениями системы из 4 уравнений степени 5 с 3 переменными. Такая переопределенная система не имеет решения в общем случае (то есть, если коэффициенты не являются конкретными). Если она имеет конечное число решений, это число не превышает 5 ³ = 125 по теореме Безу . Однако было показано, что для случая особых точек поверхности степени 6 максимальное число решений равно 65 и достигается поверхностью Барта.

Основные свойства и определения

Система переопределена, если число уравнений больше числа переменных. Система противоречива, если она не имеет комплексного решения (или, если коэффициенты не являются комплексными числами, то решения в алгебраически замкнутом поле, содержащем коэффициенты). Согласно Nullstellensatz Гильберта это означает, что 1 является линейной комбинацией (с многочленами в качестве коэффициентов) первых членов уравнений. Большинство, но не все переопределенные системы, построенные со случайными коэффициентами, противоречивы. Например, система x ³ – 1 = 0, x ² – 1 = 0 переопределена (имеет два уравнения, но только одно неизвестное), но она не противоречива, поскольку имеет решение x = 1 .

Система недоопределена, если число уравнений меньше числа переменных. Недоопределенная система либо несовместна, либо имеет бесконечно много комплексных решений (или решений в алгебраически замкнутом поле , содержащем коэффициенты уравнений). Это нетривиальный результат коммутативной алгебры , включающий, в частности, Nullstellensatz Гильберта и теорему Крулля о главном идеале .

Система является нульмерной, если она имеет конечное число комплексных решений (или решений в алгебраически замкнутом поле). Эта терминология исходит из того факта, что алгебраическое многообразие решений имеет размерность ноль. Система с бесконечным числом решений называется положительно-размерной .

Нульмерная система с таким же количеством уравнений, как и переменных, иногда называется хорошо себя ведущей . ^[3] Теорема Безу утверждает, что хорошо себя ведущая система, уравнения которой имеют степени d ₁ , ..., d _{n ,} имеет не более d ₁ ⋅⋅⋅ d _n решений. Эта граница точная. Если все степени равны d , эта граница становится d ⁿ и экспоненциально зависит от числа переменных. ( Основная теорема алгебры — это частный случай n = 1 .)

Такое экспоненциальное поведение затрудняет решение полиномиальных систем и объясняет, почему существует мало решателей, которые способны автоматически решать системы с границей Безу выше, скажем, 25 (три уравнения степени 3 или пять уравнений степени 2 выходят за эту границу). ^{[ необходима ссылка ]}

Что такое решение?

Первое, что нужно сделать для решения полиномиальной системы, — решить, является ли она несовместной, нульмерной или положительной размерности. Это можно сделать, вычислив базис Грёбнера левых частей уравнений. Система несовместна , если этот базис Грёбнера сводится к 1. Система нульмерна , если для каждой переменной существует ведущий моном некоторого элемента базиса Грёбнера, который является чистой степенью этой переменной. Для этого теста наилучшим порядком мономов (то есть тем, который обычно приводит к самому быстрому вычислению) обычно является градуированный обратный лексикографический (grevlex).

Если система имеет положительную размерность , она имеет бесконечно много решений. Таким образом, перечислить их невозможно. Из этого следует, что в этом случае решение может означать только «нахождение описания решений, из которого легко извлечь соответствующие свойства решений». Общепринятого такого описания не существует. На самом деле существует множество различных «соответствующих свойств», которые охватывают почти все подполя алгебраической геометрии .

Естественным примером такого вопроса, касающегося положительно-размерных систем, является следующий: решить, имеет ли полиномиальная система над рациональными числами конечное число действительных решений, и вычислить их . Обобщением этого вопроса является нахождение хотя бы одного решения в каждой связной компоненте множества действительных решений полиномиальной системы . Классическим алгоритмом решения этих вопросов является цилиндрическое алгебраическое разложение , которое имеет дважды экспоненциальную вычислительную сложность и поэтому не может быть использовано на практике, за исключением очень небольших примеров.

Для нульмерных систем решение состоит из вычисления всех решений. Существует два различных способа вывода решений. Наиболее распространенный способ возможен только для действительных или комплексных решений и состоит в выводе числовых приближений решений. Такое решение называется числовым . Решение сертифицировано, если оно снабжено границей погрешности приближений, и если эта граница разделяет различные решения.

Другой способ представления решений называется алгебраическим . Он использует тот факт, что для нульмерной системы решения принадлежат алгебраическому замыканию поля k коэффициентов системы. Существует несколько способов представления решения в алгебраическом замыкании, которые обсуждаются ниже. Все они позволяют вычислять численное приближение решений путем решения одного или нескольких одномерных уравнений. Для этого вычисления предпочтительнее использовать представление, которое включает решение только одного одномерного многочлена на решение, поскольку вычисление корней многочлена, имеющего приближенные коэффициенты, является крайне нестабильной задачей .

Расширения

Тригонометрические уравнения

Тригонометрическое уравнение — это уравнение g = 0 , где g — тригонометрический полином . Такое уравнение можно преобразовать в полиномиальную систему, разложив в нем синусы и косинусы (используя формулы суммы и разности ), заменив sin( x ) и cos( x ) двумя новыми переменными s и c и добавив новое уравнение s ² + c ² – 1 = 0 .

Например, из-за идентичности

${\displaystyle \cos(3x)=4\cos ^{3}(x)-3\cos(x),}$

решение уравнения

${\displaystyle \sin ^{3}(x)+\cos(3x)=0}$

эквивалентно решению полиномиальной системы

${\displaystyle {\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}}$

Для каждого решения ( c ₀ , s ₀ ) этой системы существует единственное решение x уравнения такое, что 0 ≤ x < 2 π .

В случае этого простого примера может быть неясно, проще ли решить систему, чем уравнение. В более сложных примерах отсутствуют систематические методы для непосредственного решения уравнения, в то время как программное обеспечение доступно для автоматического решения соответствующей системы.

Решения в конечном поле

При решении системы над конечным полем k с q элементами в первую очередь интересуют решения в k . Поскольку элементы k являются в точности решениями уравнения x ^q – x = 0 , для ограничения решений до k достаточно добавить уравнение x _i ^q – x _i = 0 для каждой переменной  x _i .

Коэффициенты в числовом поле или в конечном поле с непростым порядком

Элементы алгебраического числового поля обычно представляются в виде многочленов от генератора поля, который удовлетворяет некоторому одномерному полиномиальному уравнению. Для работы с полиномиальной системой, коэффициенты которой принадлежат числовому полю, достаточно рассмотреть этот генератор как новую переменную и добавить уравнение генератора к уравнениям системы. Таким образом, решение полиномиальной системы над числовым полем сводится к решению другой системы над рациональными числами.

Например, если система содержит , то система над рациональными числами получается путем сложения уравнения r ₂ ² – 2 = 0 и замены на r ₂ в остальных уравнениях. ${\displaystyle {\sqrt {2}}}$ ${\displaystyle {\sqrt {2}}}$

В случае конечного поля то же самое преобразование позволяет всегда предположить, что поле k имеет простой порядок.

Алгебраическое представление решений

Регулярные цепи

Обычный способ представления решений — через нульмерные регулярные цепочки. Такая цепочка состоит из последовательности многочленов f ₁ ( x ₁ ) , f ₂ ( x ₁ , x ₂ ) , ..., f _n ( x ₁ , ..., x _n ) таких, что для каждого i такого, что 1 ≤ i ≤ n

• f _i — многочлен только от x ₁ , ..., x _i , имеющий степень d _i > 0 по x _i ;
• коэффициент при x _i ^{d _i} в f _i является многочленом от x ₁ , ..., x _{i −1 ,} который не имеет общих нулей с f ₁ , ..., f _{i − 1} .

С такой регулярной цепочкой связана треугольная система уравнений

${\displaystyle {\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}}$

Решения этой системы получаются путем решения первого уравнения одной переменной, подстановки решений в другие уравнения, затем решения второго уравнения, которое теперь является уравнением одной переменной, и т. д. Определение регулярных цепочек подразумевает, что уравнение одной переменной, полученное из f _{i ,} имеет степень d _i и, таким образом, что система имеет d ₁ ... d _n решений, при условии, что в этом процессе разрешения нет кратных корней ( основная теорема алгебры ).

Каждая нульмерная система полиномиальных уравнений эквивалентна (т.е. имеет те же решения) конечному числу регулярных цепей. Может потребоваться несколько регулярных цепей, как это имеет место для следующей системы, которая имеет три решения.

${\displaystyle {\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}}$

Существует несколько алгоритмов для вычисления треугольного разложения произвольной полиномиальной системы (не обязательно нульмерной) ^[4] в регулярные цепочки (или регулярные полуалгебраические системы ).

Существует также алгоритм, который специфичен для нульмерного случая и в этом случае конкурирует с прямыми алгоритмами. Он состоит в вычислении сначала базиса Грёбнера для градуированного обратного лексикографического порядка (grevlex) , затем выведении лексикографического базиса Грёбнера с помощью алгоритма FGLM ^[5] и, наконец, применении алгоритма Lextriangular. ^[6]

Такое представление решений вполне удобно для коэффициентов в конечном поле. Однако для рациональных коэффициентов необходимо учитывать два аспекта:

• Выходные данные могут содержать огромные целые числа, что может затруднить вычисления и использование результата.
• Чтобы вывести числовые значения решений из выходных данных, необходимо решить одномерные полиномы с приближенными коэффициентами, что является крайне нестабильной задачей.

Первая проблема была решена Даханом и Шостом: ^{[7] [8]} Среди наборов регулярных цепей, которые представляют заданный набор решений, есть набор, для которого коэффициенты явно ограничены в терминах размера входной системы, с почти оптимальной границей. Этот набор, называемый равнопроекционным разложением , зависит только от выбора координат. Это позволяет использовать модульные методы для эффективного вычисления равнопроекционного разложения. ^[9]

Вторая проблема обычно решается путем вывода регулярных цепей специального вида, иногда называемых леммой формы , для которых все d _i , кроме первого, равны 1. Для получения таких регулярных цепей, возможно, придется добавить еще одну переменную, называемую разделяющей переменной , которой присваивается индекс 0. Рациональное одномерное представление , описанное ниже, позволяет вычислить такую ​​специальную регулярную цепочку, удовлетворяющую границе Дахана–Шоста, начиная либо с регулярной цепи, либо с базиса Грёбнера.

Рациональное одномерное представление

Рациональное одномерное представление или RUR — это представление решений нульмерной полиномиальной системы над рациональными числами, которое было введено Ф. Руйе. ^[10]

РУР нульмерной системы состоит из линейной комбинации x ₀ переменных, называемой разделяющей переменной , и системы уравнений ^[11]

${\displaystyle {\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}}$

где h — одномерный многочлен относительно x ₀ степени D , а g ₀ , ..., g _n — одномерные многочлены относительно x ₀ степени меньше D .

Для нульмерной полиномиальной системы над рациональными числами RUR обладает следующими свойствами.

• Все линейные комбинации переменных, за исключением конечного числа, являются разделяющими переменными.
• Когда разделяющая переменная выбрана, RUR существует и является уникальным. В частности, h и g _i определяются независимо от любого алгоритма для их вычисления.
• Решения системы находятся во взаимно однозначном соответствии с корнями h , а кратность каждого корня h равна кратности соответствующего решения.
• Решения системы получаются путем подстановки корней h в другие уравнения.
• Если h не имеет кратных корней, то g ₀ является производной h .

Например, для системы в предыдущем разделе каждая линейная комбинация переменной, за исключением кратных x , y и x + y , является разделяющей переменной. Если выбрать t = ⁠х – у/2⁠ в качестве разделительной переменной, то RUR равен

${\displaystyle {\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}}$

RUR однозначно определяется для заданной разделяющей переменной, независимо от любого алгоритма, и сохраняет кратности корней. Это заметное отличие от треугольных разложений (даже равнопроекционного разложения), которые, в общем случае, не сохраняют кратности. RUR разделяет с равнопроекционным разложением свойство производить выход с коэффициентами относительно малого размера.

Для нульмерных систем RUR позволяет извлекать числовые значения решений путем решения одного одномерного полинома и подстановки их в рациональные функции. Это позволяет производить сертифицированные приближения решений с любой заданной точностью.

Более того, одномерный многочлен h ( x ₀ ) RUR может быть факторизован, и это дает RUR для каждого неприводимого множителя. Это обеспечивает простое разложение заданного идеала (то есть первичное разложение радикала идеала). На практике это обеспечивает выход с гораздо меньшими коэффициентами, особенно в случае систем с высокой кратностью.

В отличие от треугольных разложений и равнопроективных разложений, RUR не определен в положительном измерении.

Решение численно

Общие алгоритмы решения

Общие численные алгоритмы, разработанные для любой системы нелинейных уравнений, работают также и для полиномиальных систем. Однако, как правило, предпочтение отдается конкретным методам, поскольку общие методы, как правило, не позволяют найти все решения. В частности, когда общий метод не находит никакого решения, это обычно не является признаком того, что решения нет.

Тем не менее, два метода заслуживают здесь упоминания.

• Метод Ньютона можно использовать, если число уравнений равно числу переменных. Он не позволяет найти все решения или доказать, что решения нет. Но он очень быстр, если начинать с точки, близкой к решению. Поэтому он является базовым инструментом для метода продолжения гомотопии, описанного ниже.
• Оптимизация редко используется для решения полиномиальных систем, но около 1970 года ей удалось показать, что система из 81 квадратного уравнения с 56 переменными не является непротиворечивой. ^[12] С другими известными методами это остается за пределами возможностей современной технологии по состоянию на 2022 год ^{[обновлять]}. Этот метод состоит просто в минимизации суммы квадратов уравнений. Если ноль найден как локальный минимум, то он достигается в решении. Этот метод работает для переопределенных систем, но выводит пустую информацию, если все найденные локальные минимумы положительны.

Метод продолжения гомотопии

Это получисловой метод, который предполагает, что число уравнений равно числу переменных. Этот метод относительно старый, но он был значительно улучшен в последние десятилетия. ^[13]

Этот метод делится на три шага. Сначала вычисляется верхняя граница числа решений. Эта граница должна быть максимально точной. Поэтому она вычисляется, по крайней мере, четырьмя различными методами, и сохраняется лучшее значение, скажем, . ${\displaystyle N}$

На втором этапе генерируется система полиномиальных уравнений, которая имеет ровно столько решений, сколько легко вычислить. Эта новая система имеет то же количество переменных и то же количество уравнений и ту же общую структуру, что и решаемая система, . ${\displaystyle g_{1}=0,\,\ldots ,\,g_{n}=0}$ ${\displaystyle N}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f_{1}=0,\,\ldots ,\,f_{n}=0}$

Затем рассматривается гомотопия между двумя системами. Она состоит, например, из прямой линии между двумя системами, но могут рассматриваться и другие пути, в частности, чтобы избежать некоторых особенностей в системе

${\displaystyle (1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0}$.

Продолжение гомотопии состоит в деформации параметра от 0 до 1 и отслеживании решений в ходе этой деформации. Это дает искомые решения для . Отслеживание означает, что если , решения для выводятся из решений для методом Ньютона. Трудность здесь заключается в том, чтобы хорошо выбрать значение Слишком большое, сходимость Ньютона может быть медленной и может даже перескочить с одного пути решения на другой. Слишком маленькое, и количество шагов замедляет метод. ${\displaystyle t}$ ${\displaystyle N}$ ${\displaystyle t=1}$ ${\displaystyle t_{1}<t_{2}}$ ${\displaystyle t=t_{2}}$ ${\displaystyle t=t_{1}}$ ${\displaystyle t_{2}-t_{1}:}$

Численное решение с использованием рационального одномерного представления

Вывести числовые значения решений из RUR кажется простым: достаточно вычислить корни одномерного полинома и подставить их в другие уравнения. Это не так просто, поскольку оценка полинома по корням другого полинома крайне нестабильна.

Корни одномерного полинома должны быть вычислены с высокой точностью, которая не может быть определена раз и навсегда. Существуют два алгоритма, которые удовлетворяют этому требованию.

• Метод Аберта , реализованный в MPSolve, вычисляет все комплексные корни с любой точностью.
• Алгоритм Успенского Коллинза и Акрита ^[14], усовершенствованный Руйе и Циммерманом ^[15] и основанный на правиле знаков Декарта . Этот алгоритм вычисляет действительные корни, изолированные в интервалах произвольной малой ширины. Он реализован в Maple (функции fsolve и RootFinding[Isolate] ).

Пакеты программного обеспечения

Существует по крайней мере четыре пакета программного обеспечения, которые могут автоматически решать нульмерные системы (под автоматическим подразумевается, что не требуется никакого человеческого вмешательства между вводом и выводом, и, таким образом, не требуется никакого знания метода пользователем). Существует также несколько других пакетов программного обеспечения, которые могут быть полезны для решения нульмерных систем. Некоторые из них перечислены после автоматических решателей.

Функция Maple RootFinding[Isolate] принимает в качестве входных данных любую полиномиальную систему над рациональными числами (если некоторые коэффициенты являются числами с плавающей точкой , они преобразуются в рациональные числа) и выводит действительные решения, представленные либо (необязательно) в виде интервалов рациональных чисел, либо в виде приближений с плавающей точкой произвольной точности. Если система не является нульмерной, это сигнализируется как ошибка.

Внутренне этот решатель, разработанный Ф. Руйе, вычисляет сначала базис Грёбнера, а затем рациональное одномерное представление, из которого выводится требуемое приближение решений. Он работает рутинно для систем, имеющих до нескольких сотен сложных решений.

Рациональное одномерное представление можно вычислить с помощью функции Maple Groebner[RationalUnivariateRepresentation] .

Чтобы извлечь все комплексные решения из рационального одномерного представления, можно использовать MPSolve , который вычисляет комплексные корни одномерных полиномов с любой точностью. Рекомендуется запускать MPSolve несколько раз, каждый раз удваивая точность, пока решения не станут устойчивыми, поскольку подстановка корней в уравнения входных переменных может быть крайне нестабильной.

Второй решатель — PHCpack, ^{[13] [16],} написанный под руководством Дж. Вершельде. PHCpack реализует метод продолжения гомотопии. Этот решатель вычисляет изолированные комплексные решения полиномиальных систем, имеющих столько же уравнений, сколько и переменных.

Третий решатель — Bertini, ^{[17] [18],} написанный DJ Bates, JD Hauenstein, AJ Sommese и CW Wampler. Bertini использует численное гомотопическое продолжение с адаптивной точностью. В дополнение к вычислению нульмерных множеств решений, как PHCpack, так и Bertini способны работать с положительными размерными множествами решений.

Четвертый решатель — библиотека Maple RegularChains , написанная Марком Морено-Маза и соавторами. Она содержит различные функции для решения полиномиальных систем с помощью регулярных цепей .

Смотрите также

• Теория исключения
• Системы полиномиальных неравенств
• Треугольное разложение
• Метод характеристического множества Ву

Ссылки

1. Бейтс и др. 2013, стр. 4
2. Бейтс и др. 2013, стр. 8
3. Songxin Liang, J. Gerhard, DJ Jeffrey, G. Moroz, Пакет для решения параметрических полиномиальных систем . Сообщения в компьютерной алгебре (2009)
4. Обри, П.; Маза, М. Морено (1999). «Треугольные множества для решения полиномиальных систем: сравнительная реализация четырех методов». J. Symb. Comput . 28 (1–2): 125–154. doi : 10.1006/jsco.1999.0270 .
5. Faugère, JC; Gianni, P .; Lazard, D.; Mora, T. (1993). «Эффективное вычисление нульмерного базиса Грёбнера путем изменения порядка». Journal of Symbolic Computation . 16 (4): 329–344. doi : 10.1006/jsco.1993.1051 .
6. Лазар, Д. (1992). «Решение нульмерных алгебраических систем». Журнал символических вычислений . 13 (2): 117–131. doi :10.1016/S0747-7171(08)80086-7.
7. Ксавье Дахан и Эрик Шост. Точные оценки для треугольных множеств . Более того, недавние алгоритмы разложения полиномиальных систем на треугольные разложения производят регулярные цепочки с коэффициентами, соответствующими результатам Дахана и Шоста. В трудах ISSAC'04, страницы 103--110, ACM Press, 2004
8. Дахан, Ксавье; Морено Маза, Марк; Шост, Эрик; У, Вэньюань; Се, Юйчжэнь (2005). «Методы подъема для треугольных разложений» (PDF) . Труды ISAAC 2005. ACM Press. стр. 108–105.
9. Чанбо Чен и Марк Морено-Маза. Алгоритмы для вычисления треугольного разложения полиномиальных систем . В трудах ISSAC'2011, страницы 83-90, ACM Press, 2011 и Journal of Symbolic Computation (в печати)
10. Руйе, Фабрис (1999). «Решение нульмерных систем с помощью рационального одномерного представления». Appl. Algebra Eng. Commun. Comput . 9 (9): 433–461. doi :10.1007/s002000050114. S2CID  25579305.
11. Саугата Басу; Ричард Поллак; Мари-Франсуаза Руа (2006). Алгоритмы в реальной алгебраической геометрии, глава 12.4. Springer-Verlag .
12. Лазар, Дэниел (2009). «Тридцать лет решения полиномиальных систем, а теперь?». J. Symb. Comput . 44 (3): 2009. doi : 10.1016/j.jsc.2008.03.004 .
13. Verschelde, Jan (1999). "Алгоритм 795: PHCpack: универсальный решатель для полиномиальных систем с помощью гомотопического продолжения" (PDF) . ACM Transactions on Mathematical Software . 25 (2): 251–276. doi :10.1145/317275.317286. S2CID  15485257.
14. Джордж Э. Коллинз и Алкивиадис Г. Акритас, Изоляция полиномиальных действительных корней с использованием правила знаков Декарта . Труды симпозиума ACM 1976 года по символьным и алгебраическим вычислениям
15. Руйе, Ф.; Циммерман, П. (2004). «Эффективная изоляция действительных корней многочлена». Журнал вычислительной и прикладной математики . 162 (1): 33–50. Bibcode : 2004JCoAM.162...33R. doi : 10.1016/j.cam.2003.08.015 .
16. Выпуск 2.3.86 PHCpack
17. Бейтс и др. 2013
18. Бертини: Программное обеспечение для численной алгебраической геометрии

• Bates, Daniel J.; Sommese, Andrew J.; Hauenstein, Jonathan D.; Wampler, Charles W. (2013). Численное решение полиномиальных систем с помощью Bertini . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-1-61197-269-6.
• Кокс, Дэвид; Литтл, Джон; О'Ши, Донал (1997). Идеалы, многообразия и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру (2-е изд.). Нью-Йорк: Springer. ISBN 978-0387946801.
• Морган, Александр (1987). Решение полиномиальных систем с использованием продолжения для инженерных и научных задач (ред. SIAM). Общество промышленной и прикладной математики (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104). ISBN 9780898719031.
• Sturmfels, Bernd (2002). Решение систем полиномиальных уравнений . Providence, RI: American Mathematical Soc. ISBN 0821832514.