Обычная сеть

В математике , а точнее в компьютерной алгебре и теории исключения , регулярная цепь — это особый вид треугольного набора над многомерных многочленов полем, где треугольный набор — это конечная последовательность многочленов, каждый из которых содержит по крайней мере еще один неопределенный набор. чем предыдущий. Условие, которому треугольное множество должно удовлетворять, чтобы быть регулярной цепью, состоит в том, что для каждого k каждый общий нуль (в алгебраически замкнутом поле ) k первых многочленов может быть продолжен до общего нуля ( k + 1) -го полинома. полиномиальный. Другими словами, регулярные цепочки позволяют решать системы полиномиальных уравнений путем решения последовательных одномерных уравнений без рассмотрения различных случаев.

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

Введение

Учитывая линейную систему , можно преобразовать ее в треугольную систему методом исключения Гаусса . В нелинейном случае, если задана полиномиальная система F над полем, ее можно преобразовать (разложить или триангуляризовать) в конечный набор треугольных множеств в том смысле, что алгебраическое многообразие V (F) описывается этими треугольными множествами. .

Треугольное множество может просто описывать пустое множество. Чтобы исправить этот ухудшенный случай, независимо друг от друга Калкбренер (1993), Ян и Чжан (1994) ввели понятие регулярной цепи. Регулярные цепочки также появляются у Чжоу и Гао (1992). Регулярные цепи — это специальные треугольные множества, которые используются в различных алгоритмах вычисления несмешанно-мерных разложений алгебраических многообразий. Без использования факторизации эти разложения обладают лучшими свойствами, чем те, которые производятся алгоритмом Ву . Первоначальное определение Калькбренера было основано на следующем наблюдении: каждое неприводимое многообразие однозначно определяется одной из своих общих точек , и многообразия могут быть представлены путем описания общих точек их неприводимых компонентов. Эти общие точки задаются регулярными цепочками.

Примеры

Обозначим Q поле рациональных чисел. В Q [ x ₁ , x ₂ , x ₃ ] с переменным порядком x ₁ < x ₂ < x ₃ ,

$T=\{x_{2}^{2}-x_{1}^{2},x_{2}(x_{3}-x_{1})\}$

представляет собой треугольное множество и также является регулярной цепью. заданными T, являются ( a , a , a ) и ( a , − a , a ), где a трансцендентна над Q. Двумя общими точками , Таким образом, есть два неприводимых компонента, заданные формулами { x ₂ − x ₁ , x ₃ − x ₁ } и { x ₂ + x ₁ , x ₃ − x ₁ } соответственно.Обратите внимание, что: (1) содержимое второго полинома равно x ₂ , что не влияет на представленные общие точки и, следовательно, может быть удалено; (2) размерность каждой компоненты равна 1 — числу свободных переменных в регулярной цепочке.

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

Переменные в кольце полиномов

$R=k[x_{1},\ldots ,x_{n}]$

всегда сортируются как x ₁ < ⋯ < x _n . Непостоянный полином f в $R$ можно рассматривать как одномерный многочлен от наибольшей переменной.Самая большая переменная в f называется главной переменной и обозначается mvar ( f ). Пусть u — основная переменная f и запишите ее как

$f=a_{e}u^{e}+\cdots +a_{0},$

где e - степень f по отношению к u и $a_{e}$ является старшим коэффициентом f по отношению к u . Тогда начальная буква f равна $a_{e}$ — e его главная степень.

• Треугольный набор

Непустое подмножество T из $R$ является треугольным множеством, если многочлены из T непостоянны и имеют различные основные переменные. Следовательно, треугольное множество конечно и имеет мощность не более n .

• Обычная сеть

Пусть T = { t ₁ , ..., t _s } — треугольное множество такое, что mvar ( t ₁ ) < ⋯ < mvar ( t _s ) , $h_{i}$ быть начальным значением t _i и h быть произведением h _i . Тогда T — регулярная цепь , если

$\mathrm {resultant} (h,T)=\mathrm {resultant} (\cdots (\mathrm {resultant} (h,t_{s}),\ldots ,t_{i})\cdots )\neq 0,$

где каждый результат вычисляется относительно основной переменной t _i соответственно. Это определение принадлежит Янгу и Чжану и имеет большой алгоритмический оттенок.

• Квазикомпонентный и насыщенный идеал регулярной цепи

Квазикомпонента ) , W ( T описываемая регулярной цепью T, есть

$W(T)=V(T)\setminus V(h)$, то есть,

разность множеств многообразий V ( T ) и V ( h ). Присоединенный алгебраический объект регулярной цепи — это ее насыщенный идеал.

$\mathrm {sat} (T)=(T):h^{\infty }.$

Классический результат состоит в том, что Зариского замыкание W ( T ) равно многообразию, определенному sat( T ), то есть

${\overline {W(T)}}=V(\mathrm {sat} (T)),$

и его размерность равна n − | T |, разность числа переменных и количества полиномов в T .

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

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

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

Второй — описать все нули в смысле Лазара :

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

Существуют различные алгоритмы треугольного разложения в любом смысле.

Свойства

Пусть T — регулярная цепь в кольце полиномов R .

• Насыщенный идеал sat( T ) — это несмешанный идеал размерности n − | Т |.
• Регулярная цепь обладает сильным свойством исключения в том смысле, что:

$\mathrm {sat} (T\cap k[x_{1},\ldots ,x_{i}])=\mathrm {sat} (T)\cap k[x_{1},\ldots ,x_{i}].$

• Полином p находится в sat( T ) тогда и только тогда, когда p псевдо-приводится к нулю с помощью T , то есть,

$p\in \mathrm {sat} (T)\iff \mathrm {prem} (p,T)=0.$

Следовательно, проверка принадлежности для sat( T ) является алгоритмической.

• Полином p является делителем нуля по модулю sat( T ) тогда и только тогда, когда $\mathrm {prem} (p,T)\neq 0$ и $\mathrm {resultant} (p,T)=0$.

Следовательно, проверка регулярности sat( T ) является алгоритмической.

• Для простого идеала P существует регулярная цепь C такая, что P = sat( C ).
• Если первый элемент регулярной цепи C является неприводимым многочленом, а остальные линейны по своей основной переменной, то sat( C ) является простым идеалом.
• Обратно, если P — простой идеал, то после почти всех линейных замен переменных существует регулярная цепочка C предыдущей формы такая, что P = sat( C ).
• Треугольное множество является регулярной цепью тогда и только тогда, когда оно является характеристическим множеством Ритта своего насыщенного идеала.

См. также

• Метод набора характеристик Ву
• База Грёбнер
• Регулярная полуалгебраическая система
• Треугольное разложение

Дальнейшие ссылки

• П. Обри, Д. Лазар, М. Морено Маза. О теориях треугольных множеств . Журнал символических вычислений, 28 (1–2): 105–124, 1999.
• Ф. Булье, Ф. Лемэр и М. Морено Маза. Известные теоремы о треугольных системах и принцип D5 . Трансгрессивные вычисления 2006, Гранада, Испания.
• Э. Хьюберт. Заметки о треугольных множествах и алгоритмах триангуляции-декомпозиции I: Полиномиальные системы . LNCS, том 2630, Springer-Verlag Heidelberg.
• Ф. Лемэр и М. Морено Маза и Ю. Се. Библиотека RegularChains. Кленовая конференция 2005.
• М. Калькбренер: Алгоритмические свойства колец многочленов . Дж. Симб. Вычислить. 26(5): 525–581 (1998).
• М. Калькбренер: Обобщенный евклидов алгоритм вычисления треугольных представлений алгебраических многообразий . Дж. Симб. Вычислить. 15(2): 143–167 (1993).
• Д. Ван. Вычисление треугольных систем и регулярных систем . Журнал символических вычислений 30 (2) (2000) 221–236.
• Ян Л., Чжан Дж. (1994). Поиск зависимости между алгебраическими уравнениями: алгоритм, применяемый для автоматизированных рассуждений . Искусственный интеллект в математике, стр. 14715, Oxford University Press.