Треугольное разложение

В компьютерной алгебре треугольное разложение полиномиальной системы S — это набор более простых полиномиальных систем , _S1 ..., Se _таких , что точка является решением системы S тогда и только тогда, когда она является решением одной из систем. S ₁ , ..., S _е .

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

История

Метод набора характеристик — это первый алгоритм без факторизации, который был предложен для разложения алгебраического многообразия на равномерные компоненты. Более того, автор Вэнь-Цун Ву реализовал реализацию этого метода и сообщил об экспериментальных данных в своей новаторской статье 1987 года под названием «Теорема о нулевой структуре для решения полиномиальных уравнений». Чтобы представить эту работу в контексте, давайте вспомним, какова была общая идея декомпозиции алгебраического множества во время написания этой статьи.

Пусть K — алгебраически замкнутое поле и k подполе в K. — Подмножество V ⊂ K ^н является (аффинным) алгебраическим многообразием над k, если существует полиномиальное множество F ⊂ k [ x ₁ , ..., x _n ] такое, что нулевое множество V ( F ) ⊂ K ^н F ​ равно V. ​

Напомним, что V называется неприводимым, если для всех алгебраических многообразий V ₁ , V ₂ ⊂ K ^н соотношение V = V ₁ ∪ V ₂ влечет либо V = V ₁ , либо V = V ₂ . Первым результатом разложения алгебраического многообразия является знаменитая теорема Ласкера – Нётер, из которой следует следующее.

Теорема (Ласкера — Нётер). Для каждого алгебраического многообразия V ⊂ K ^н существует конечное число неприводимых алгебраических многообразий V ₁ , ..., V _e ⊂ K ^н такой, что у нас есть

$V=V_{1}\cup \cdots \cup V_{e}.$

, если V _i ⊈ V _j выполнено для 1 ⩽ i < j ⩽ e, то множество { V ₁ , ..., V _e } уникально и образует неприводимое разложение V Более того .

Многообразия V ₁ , ..., V _e в приведенной выше теореме называются неприводимыми компонентами V в и могут рассматриваться как естественный результат алгоритма декомпозиции или, другими словами, алгоритма, решающего систему уравнений k [ Икс ₁ , ..., Икс _п ] .

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

Theorem (Ritt). If V ⊂ K ^н является непустым и неприводимым многообразием, то можно вычислить приведенное треугольное множество C, содержащееся в идеале $\langle F\rangle$ порожденный F в k [ x ₁ , ..., x _n ] и такой, что все многочлены g в $\langle F\rangle$ сводится к нулю псевдоделением относительно C .

Множество C в теореме Ритта мы называем характеристическим множеством Ритта идеала $\langle F\rangle$. Пожалуйста, обратитесь к регулярной цепочке за понятием треугольного набора.

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

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

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

Метод набора характеристик основан на следующем варианте теоремы Ритта.

Теорема (Вэнь-Цун Ву). Для любого конечного полиномиального набора F ⊂ k [ x ₁ , ..., x _n ] можно вычислить приведенный треугольный набор $C\subset \langle F\rangle$ такой, что весь многочлен g в F сводится к нулю псевдоделением относительно C .

Различные концепции и алгоритмы расширили работу Вэнь-Цун Ву . В начале 1990-х годов появилось понятие регулярной цепи , независимо введенное Майклом Калкбренером в 1991 году в его докторской диссертации, а также Лу Яном и Цзинчжун Чжаном. привели к важным алгоритмическим открытиям.

По мнению Калькбренера, регулярные цепи используются для представления общих нулей неприводимых компонент алгебраического многообразия. В оригинальной работе Янга и Чжана они используются для определения того, пересекает ли гиперповерхность квазимногообразие (заданное регулярной цепью). На самом деле регулярные цепи обладают несколькими интересными свойствами и являются ключевым понятием во многих алгоритмах декомпозиции систем алгебраических или дифференциальных уравнений.

Регулярные цепи исследовались во многих работах.

Обилие литературы по этому вопросу можно объяснить множеством эквивалентных определений регулярной цепи. На самом деле первоначальная формулировка Калькбренера сильно отличается от формулировки Янга и Чжана. Мост между этими двумя понятиями, точкой зрения Калькбренера и точкой зрения Янга и Чжана, появляется в статье Вана Дунмина.

Существуют различные алгоритмы получения треугольного разложения V ( F ) как в смысле Калькбренера, так и в смысле Лазарда и Вен-Цун Ву . алгоритм Лектреугольный Дэниела Лазарда и алгоритм триады Марка Морено Маза вместе с методом набора характеристик доступны в различных системах компьютерной алгебры, включая Axiom и Maple .

Формальные определения

Пусть k — поле и x ₁ < ... < x _n — упорядоченные переменные. Обозначим через R = k [ x1 _xn ,... ] _{соответствующее} , кольцо полиномов . Для F ⊂ R , рассматриваемого как система полиномиальных уравнений, существует два понятия треугольного разложения над замыканием алгебраическим k . Первый — ленивое разложение, представляя только общие точки алгебраического множества V ( F ) в так называемом смысле Калькбренера.

${\sqrt {(F)}}=\bigcap _{i=1}^{e}{\sqrt {\mathrm {sat} (T_{i})}}.$

Второй — явно описать все точки V ( F ) в так называемом смысле по Лазарду и Вэнь-Цунь Ву .

$V(F)=\bigcup _{i=1}^{e}W(T_{i}).$

В обоих случаях T ₁ , ..., e _— конечное число регулярных цепей R и T ${\sqrt {\mathrm {sat} (T_{i})}}$ радикал идеала Ti , _​ а W ( Ti ₎ ​ обозначает квазикомпоненту Ti обозначает _. насыщенного Пожалуйста, обратитесь к регулярной цепочке для определений этих понятий.

С этого момента будем считать, что k — действительное замкнутое поле . Рассмотрим S полуалгебраическую систему с полиномами из R . Существуют конечное число регулярных полуалгебраических систем , _S1 ..., Se _таких , что имеем

$Z_{\mathbf {k} }(S)=Z_{\mathbf {k} }(S_{1})\cup \cdots \cup Z_{\mathbf {k} }(S_{e})$

где Z _k ( S ) обозначает точки k ^н решают С. которые Регулярные полуалгебраические системы S ₁ , ..., S _e образуют треугольное разложение полуалгебраической системы S .

Примеры

Обозначим Q поле рациональных чисел. В $Q[x,y,z]$ с переменным порядком $x>y>z$, рассмотрим следующую полиномиальную систему:

$S={\begin{cases}x^{2}+y+z=1\\x+y^{2}+z=1\\x+y+z^{2}=1\end{cases}}$

Согласно коду Maple :

with(RegularChains):
R := PolynomialRing([x, y, z]):
sys := {x^2+y+z-1, x+y^2+z-1, x+y+z^2-1}:
l := Triangularize(sys, R):
map(Equations, l, R);

Одно из возможных треугольных разложений набора решений S с использованием библиотеки RegularChains :

${\begin{cases}z=0\\y=1\\x=0\end{cases}}\cup {\begin{cases}z=0\\y=0\\x=1\end{cases}}\cup {\begin{cases}z=1\\y=0\\x=0\end{cases}}\cup {\begin{cases}z^{2}+2z-1=0\\y=z\\x=z\end{cases}}$

См. также

• Метод набора характеристик Ву
• Обычная сеть
• Регулярная полуалгебраическая система