Вус метод набора характеристик - Wus method of characteristic set - Wikipedia

Вэньцзюнь Ву метод это алгоритм решения многомерные полиномиальные уравнения представленный в конце 1970-х годов китайским математиком Вэнь-Цун Ву. Этот метод основан на математической концепции набор характеристик представленный в конце 1940-х годов Дж. Ф. Ритт. Он полностью независим от Основа Грёбнера метод, введенный Бруно Бухбергер (1965), даже если для вычисления наборов характеристик можно использовать базисы Гребнера.[1][2]

Метод Ву эффективен для механическое доказательство теорем в элементарная геометрия, и обеспечивает полный процесс решения для определенных классов проблем. Он использовался в исследованиях в его лаборатории (KLMM, Ключевая лаборатория математической механизации Китайской академии наук) и по всему миру. Основные направления исследований метода Ву касаются системы полиномиальных уравнений положительного измерения и дифференциальная алгебра куда Ритт Результаты оказались эффективными.[3][4] Метод Ву применялся в различных областях науки, таких как биология, компьютерное зрение, кинематика роботов и особенно автоматические доказательства в геометрии.[5]

Неформальное описание

Метод Ву использует многочлен подразделение для решения задач вида:

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

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

В частности, для идеальный я в звенеть k[Икс1, ..., Иксп] над полем k, характеристическое множество (Ритта) C из я состоит из набора многочленов от я, имеющий треугольную форму: многочлены от C имеют различные основные переменные (см. формальное определение ниже). Учитывая характеристический набор C из я, можно решить, является ли многочлен ж равен нулю по модулю я. То есть тест на членство можно проверить на я, при условии характерного набора я.

Набор характеристик Ritt

Характеристическое множество Ритта - это конечный набор многочленов от треугольная форма идеала. Это треугольное множество удовлетворяет определенному условию минимума относительно порядка Ритта и сохраняет многие интересные геометрические свойства идеала. Однако это может быть не его система генераторов.

Обозначение

Пусть R - многомерное кольцо многочленов k[Икс1, ..., Иксп] над полем k. Переменные упорядочены линейно в соответствии с их нижним индексом: Икс1 < ... < Иксп.Для непостоянного многочлена п в R, наибольшая переменная, эффективно представленная в п, называется основная переменная или же учебный класс, играет особую роль:п естественно рассматривать как одномерный многочлен от своей главной переменной Иксk с коэффициентами в k[Икс1, ..., Иксk−1]. Степень p как одномерного многочлена от его главной переменной также называется его главной степенью.

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

Множество Т непостоянных многочленов называется треугольный набор если все многочлены из Т имеют различные основные переменные. Это обобщает треугольную системы линейных уравнений естественным образом.

Ritt заказывает

Для двух непостоянных многочленов п и q, мы говорим п меньше чем q относительно Ritt заказывает и написано как п <р q, если выполнено одно из следующих утверждений:

(1) основная переменная п меньше, чем основная переменная q, то есть мвар (п) <мвар (q),
(2) п и q имеют ту же основную переменную и основную степень п меньше чем основная степень изq, то есть мвар (п) = мвар (q) и mdeg (п) q).

Таким образом, (k[Икс1, ..., Иксп],<р) образует ну частичный порядок. Однако порядок Ритта не общий заказ: существуют многочлены p и q такие, что ни п <р q ни п >р q. В этом случае мы говорим, что п и q несопоставимы. Заказ Ритта сравнивает классифицировать из п и q. Ранг, обозначаемый рангом (п) непостоянного многочлена п определяется как степень его основной переменной: mvar (п)mdeg (п) и ранги сравниваются путем сравнения сначала переменных, а затем, в случае равенства переменных, степеней.

Порядок Ритта на треугольных наборах

Важным обобщением порядка Ритта является сравнение треугольных множеств. Т = { т1, ..., тты} и S = { s1, ..., sv} два треугольных множества, такие, что многочлены от Т и S все чаще сортируются по их основным переменным. Т меньше, чем S w.r.t. Порядок Ритта, если выполняется одно из следующих утверждений

(1) существует k ≤ мин (ты, v) такой, что rank (тя) = ранг (sя) для 1 ≤я < k и тk <р sk,
(2) ты > v и ранг (тя) = ранг (sя) для 1 ≤я ≤ v.

Кроме того, существуют несравнимые треугольные множества с упорядочением Ритта.

Набор характеристик Ritt

Пусть I - ненулевой идеал в k [x1, ..., Иксп]. Подмножество T в I является Набор характеристик Ritt I, если выполняется одно из следующих условий:

(1) T состоит из единственной ненулевой константы k,
(2) T - треугольное множество и T минимально относительно упорядочения Ритта в множестве всех треугольных множеств, содержащихся в I.

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

Ву набор характеристик

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

Непустое подмножество T идеала ⟨F⟩, порожденное F, является Ву набор характеристик F, если выполняется одно из следующих условий

(1) T = {a} с ненулевой константой,
(2) T - треугольное множество, и существует подмножество G в ⟨F⟩ такое, что F⟩ = ⟨G⟩ и каждый многочлен из G является псевдоредуцированный к нулю по T.

Характеристическое множество Wu определяется как множество F многочленов, а не идеал ⟨F⟩, порожденный F. Также можно показать, что характеристическое множество Ритта T для ⟨F⟩ является характеристическим набором Wu для F. вычисляться с помощью алгоритма Ву CHRST-REM, который требует только вычислений псевдо-остатка и не требует факторизации.

Метод набора характеристик Ву имеет экспоненциальную сложность; повышение эффективности вычислений за счет слабых цепей, регулярные цепи, насыщенные цепи были введены[6]

Разложение алгебраических многообразий

Приложение - это алгоритм решения систем алгебраических уравнений с помощью характеристических множеств. Более точно, для данного конечного подмножества F многочленов существует алгоритм вычисления характеристических множеств T1, ..., Те такой, что:

где W (Tя) - разность V (Tя) и V (hя), здесь hя является произведением инициалов многочленов из Tя.

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

Рекомендации

  1. ^ Коррочано, Эдуардо Байро; Собчик, Гаррет, ред. (2001). Геометрическая алгебра с приложениями в науке и технике. Бостон, Массачусетс: Birkhäuser. п. 110. ISBN  9780817641993.
  2. ^ П. Обри, Д. Лазард, М. Морено Маза (1999). К теории треугольных множеств. Журнал символических вычислений, 28 (1–2): 105–124
  3. ^ Юбер, Э. Алгоритмы разложения без факторизации в дифференциальной алгебре. Журнал символических вычислений (май 2000 г.): 641–662.
  4. ^ Maple (программное обеспечение) упаковка diffalg.
  5. ^ Чжоу, Шан-Цзин; Гао, Сяо Шань; Чжан, Цзин Чжун. Машинные доказательства в геометрии. Мировой научный, 1994.
  6. ^ Чжоу С.С., Гао Х.С. Алгоритм разложения Ритта – Ву и доказательство геометрической теоремы. Proc of CADE, 10 LNCS, # 449, Berlin, Springer Verlag, 1990, 207–220.

внешняя ссылка