Обычная цепочка

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

Содержание

• 1 Введение
• 2 Примеры
• 3 Формальные определения
• 4 Свойства
• 5 См. Также
• 6 Дополнительные ссылки

Введение

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

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

Примеры

Обозначьте Q поле рационального числа. В Q[x1, x 2, x 3 ] с переменным порядком x 1< x2< x3,

$T\; =\; \{x\; 2\; 2\; -\; x\; 1\; 2,\; x\; 2\; (x\; 3\; -\; x\; 1)\; \}\; \{\backslash \; displaystyle\; T\; =\; \backslash \; \{x\_\; \{2\}\; ^\; \{2\}\; -x\_\; \{1\}\; ^\; \{2\},\; x\_\; \{2\}\; (x\_\; \{3\}\; -x\_\; \{1\})\; \backslash \}\}$

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

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

Переменные в кольце многочленов

$R\; =\; k\; [x\; 1,\dots ,\; xn]\; \{\backslash \; displaystyle\; R\; =\; k\; [x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{n\}]\}$

всегда сортируются как x 1<... < xn. Непостоянный многочлен f в $R\; \{\backslash \; displaystyle\; R\}$можно рассматривать как одномерный многочлен от его наибольшей переменной. Наибольшая переменная в f называется его главной переменной и обозначается mvar (f). Пусть u будет главной переменной f и запишем ее как

$f\; =\; aeue\; +\; \cdots \; +\; a\; 0\; \{\backslash \; displaystyle\; f\; =\; a\_\; \{e\}\; u\; ^\; \{e\}\; +\; \backslash \; cdots\; +\; a\_\; \{0\}\}$,

где е - степень f относительно u и $a\; e\; \{\backslash \; displaystyle\; a\_\; \{e\}\}$- старший коэффициент f относительно. ты Тогда начальное число f - это $a\; e\; \{\backslash \; displaystyle\; a\_\; \{e\}\}$, а e - его главная степень.

• Треугольное множество

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

• Правильная цепочка

Пусть T = {t 1,..., t s } будет треугольным множеством, таким что mvar (t 1) <... < mvar(ts), $hi\; \{\backslash \; displaystyle\; h\_\; \{i\}\}$быть начальным значением t i, а h быть произведением h i. Тогда T является регулярной цепочкой, если

$результирующая\; (h,\; T)\; =\; результирующая\; (\cdots \; (результирующая\; (h,\; ts),\dots ,\; ti)\; \cdots )\; \ne \; 0\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{resultant\}\; (h,\; T)\; =\; \backslash \; mathrm\; \{resultant\}\; (\backslash \; cdots\; (\backslash \; mathrm\; \{resultant\}\; (h,\; t\_\; \{s\}),\; \backslash \; ldots,\; t\_\; \{i\})\; \backslash \; cdots)\; \backslash \; neq\; 0\}$,

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

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

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

$W\; (T)\; =\; V\; (T)\; \setminus \; V\; (h)\; \{\backslash \; displaystyle\; W\; (T)\; =\; V\; (T)\; \backslash \; setminus\; V\; (h)\}$, то есть

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

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

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

$W\; (T)\; ¯\; =\; V\; (sat\; (T))\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{W\; (T)\}\}\; =\; V\; (\backslash \; mathrm\; \{sat\}\; (T))\}$,

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

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

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

$(F)\; =\; \cap \; я\; =\; 1\; esat\; (T\; i)\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{(F)\}\}\; =\; \backslash \; cap\; \_\; \{i\; =\; 1\}\; ^\; \{e\}\; \{\backslash \; sqrt\; \{\backslash \; mathrm\; \{sat\}\; (T\_\; \{i\})\}\}\}$.

Второй - для описания всех нулей в смысле Лазарда,

$V\; (F)\; =\; \cup \; i\; =\; 1\; e\; W\; (T\; i)\; \{\backslash \; displaystyle\; V\; (F)\; =\; \backslash \; cup\; \_\; \{i\; =\; 1\}\; ^\; \{e\}\; W\; (T\_\; \{i\})\}$.

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

Свойства

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

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

$sat\; (T\; \cap \; k\; [x\; 1,\dots ,\; xi])\; =\; sat\; (T)\; \cap \; k\; [x\; 1,\dots ,\; xi]\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{Sat\}\; (T\; \backslash \; cap\; k\; [x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{i\}])\; =\; \backslash \; mathrm\; \{sat\}\; (T)\; \backslash \; cap\; k\; [x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{i\; \}]\}$.

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

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

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

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

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

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

См. Также

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

Дополнительные ссылки

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