Численная алгебраическая геометрия - Numerical algebraic geometry

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

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

Смотрите также: Система полиномиальных уравнений § Метод продолжения гомотопии

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

Позволять ${\displaystyle z}$ представляют собой переменные системы. Из-за злоупотребления обозначениями и для облегчения спектра окружающих пространств, по которым можно решить систему, мы не используем векторные обозначения для ${\displaystyle z}$. Аналогично для полиномиальных систем ${\displaystyle f}$ и ${\displaystyle g}$.

Текущие канонические обозначения называют стартовой системой ${\displaystyle g}$, и целевая система, т. е. решаемая система, ${\displaystyle f}$.^[4][5] Очень распространенная гомотопия, прямолинейная гомотопия между ${\displaystyle f}$ и ${\displaystyle g}$ является

$${\displaystyle H(z,t)=(1-t)f(z)+tg(z).}$$

В приведенной выше гомотопии переменная пути начинается с ${\displaystyle t_{\text{start}}=1}$ и продолжает к ${\displaystyle t_{\text{end}}=0}$. Другой распространенный выбор - бежать от ${\displaystyle 0}$ к ${\displaystyle 1}$. В принципе выбор совершенно произвольный. На практике, что касается методов эндшпиля для вычисления сингулярных решений с использованием продолжения гомотопии, целевым временем является ${\displaystyle 0}$ может значительно упростить анализ, поэтому здесь используется именно эта точка зрения.^{[нужна цитата ]}

Независимо от выбора времени начала и цели, ${\displaystyle H}$ следует сформулировать так, чтобы ${\displaystyle H(z,t_{\text{start}})=g(z)}$, и ${\displaystyle H(z,t_{\text{end}})=f(z)}$.

Есть выбор в ${\displaystyle g(z)}$, в том числе

• Корни единства
• Общая степень
• Многогранник
• Мульти-однородный

и помимо этого, конкретные стартовые системы которые точно отражают структуру ${\displaystyle f}$ могут быть сформированы для конкретных систем. Выбор системы запуска влияет на время вычислений, необходимое для решения ${\displaystyle f}$в том, что те, которые легко сформулировать (например, общая степень), как правило, имеют большее количество путей для отслеживания, а те, которые требуют значительных усилий (например, многогранный метод), намного острее. В настоящее время нет хорошего способа предсказать, что приведет к наиболее быстрому решению.^{[нужна цитата ]}

Фактическое продолжение обычно выполняется с помощью методы предиктора – корректора, с дополнительными функциями. Прогнозирование осуществляется с использованием стандартного ODE метод предиктора, например Рунге-Кутта, а для коррекции часто используется итерация Ньютона – Рафсона.

Потому что ${\displaystyle f}$ и ${\displaystyle g}$ являются полиномиальными, продолжение гомотопии в этом контексте теоретически гарантирует вычисление всех решений ${\displaystyle f}$, из-за Теорема Бертини. Однако на практике эта гарантия не всегда достигается из-за проблем, возникающих из-за ограничений современного компьютера, а именно из-за конечной точности. То есть, несмотря на силу аргумента «вероятность 1», лежащего в основе этой теории, без использования априори сертифицированных методов отслеживания некоторые пути могут не отслеживаться идеально по разным причинам.

Набор свидетелей

Набор свидетелей ${\displaystyle W}$ это структура данных, используемая для описания алгебраические многообразия. Набор свидетелей для аффинного многообразия, которое равноразмерно, состоит из трех частей информации. Первая часть информации - это система уравнений ${\displaystyle F}$. Эти уравнения определяют алгебраическое многообразие ${\displaystyle {\mathbf {V} }(F)}$ это изучается. Вторая часть информации - это линейное пространство. ${\displaystyle {\mathcal {L}}}$. Размер ${\displaystyle {\mathcal {L}}}$ коразмерность ${\displaystyle {\mathbf {V} }(F)}$, и выбрал пересечение ${\displaystyle {\mathbf {V} }(F)}$ поперечно. Третья информация - это список точек пересечения. ${\displaystyle {\mathcal {L}}\cap {\mathbf {V} }(F)}$. Это пересечение имеет конечное число точек, и число точек - это степень алгебраического многообразия ${\displaystyle {\mathbf {V} }(F)}$. Таким образом, наборы свидетелей кодируют ответ на первые два вопроса об алгебраическом разнообразии: каково измерение и какова степень? Наборы свидетелей также позволяют выполнять числовую неразложимую декомпозицию, тесты на принадлежность компонентов и выборку компонентов. Это делает наборы свидетелей хорошим описанием алгебраического многообразия.

Сертификация

Решения полиномиальных систем, вычисленные с использованием методов численной алгебраической геометрии, могут быть проверенный, что означает, что приблизительное решение "правильное". Этого можно добиться несколькими способами: либо априори с помощью сертифицированного трекера, либо^[6][7] или a posteriori, показывая, что дело, скажем, в области сходимости метода Ньютона.^[8]

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

Несколько программных пакетов реализуют части теоретической части числовой алгебраической геометрии. К ним относятся, в алфавитном порядке:

• alphaCertified^[8]
• Бертини ^[5]
• Hom4PS^[9][10]
• HomotopyContinuation.jl^[11]
• Маколей2 (основная реализация гомотопического отслеживания и Числовойалгебраическая геометрия^[3] пакет)
• PHCPack^[12]

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

1. Hauenstein, Jonathan D .; Сомме, Эндрю Дж. (Март 2017 г.). "Что такое числовая алгебраическая геометрия?". Журнал символических вычислений. 79: 499–507. Дои:10.1016 / j.jsc.2016.07.015.
2. Сомме, Эндрю Дж .; Вершельде, Ян; Уэмплер, Чарльз В. (2005). «Введение в числовую алгебраическую геометрию». В Бронштейне, Мануэль; Cohen, Arjeh M .; Коэн, Анри; Эйзенбуд, Дэвид; Штурмфельс, Бернд; Диккенштейн, Алисия; Эмирис, Иоаннис З. (ред.). Решение полиномиальных уравнений: основы, алгоритмы и приложения (PDF). Springer-verlag. Дои:10.1007/3-540-27357-3_8. ISBN  978-3-540-24326-7.
3. Лейкин, Антон (01.01.2000). «Числовая алгебраическая геометрия». Журнал программного обеспечения для алгебры и геометрии. 3 (1): 5–10. Дои:10.2140 / jsag.2011.3.5. ISSN  1948-7916.
4. Сомме, Эндрю Дж .; Wampler, II, Чарльз В. (2005). Численное решение систем многочленов, возникающих в технике и науке.. World Scientific. ISBN  978-981-256-184-8.
5. Бейтс, Дэниел Дж .; Сомме, Эндрю Дж .; Хауэнштейн, Джонатан Д; Уэмплер, Чарльз В. (2013). Численное решение полиномиальных систем с помощью Бертини. Общество промышленной и прикладной математики. ISBN  978-1-61197-269-6.
6. Бельтран, Карлос; Лейкин, Антон (2012-03-01). «Сертифицированное численное отслеживание гомотопий». Экспериментальная математика. 21 (1): 69–83. arXiv:0912.0920. Дои:10.1080/10586458.2011.606184. ISSN  1058-6458.
7. Бельтран, Карлос; Лейкин, Антон (01.02.2013). «Надежное сертифицированное численное отслеживание гомотопий». Основы вычислительной математики. 13 (2): 253–295. arXiv:1105.5992. Дои:10.1007 / s10208-013-9143-2. ISSN  1615-3375.
8. Hauenstein, Jonathan D .; Соттиле, Франк (август 2012). «Алгоритм 921: alphaCertified: Сертификация решений для полиномиальных систем». Транзакции ACM на математическом ПО. 38 (4): 1–20. Дои:10.1145/2331130.2331136.
9. Chen, T .; Lee, T. L .; Ли, Т. Ю. (2014). "Hom4PS-3: Параллельное численное решение для систем полиномиальных уравнений, основанное на методах продолжения многогранных гомотопий". In Hong, H .; Яп, К. (ред.). Математическое программное обеспечение - ICMS 2014: 4-й Международный конгресс, Сеул, Южная Корея, 5-9 августа 2014 г. Труды. С. 183–190. ISBN  978-3-662-44199-2. Получено 28 апреля 2020.
10. Команда Hom4PS. «Рекомендуемые товары». Хом4ПС-3. Университет штата Мичиган. Получено 28 апреля 2020.
11. Брейдинг, Пол; Тимме, Саша (май 2018 г.). "HomotopyContinuation.jl: Пакет для продолжения гомотопии в Джулии". arXiv:1711.10911v2 [cs.MS ].
12. Вершельде, янв (1 июня 1999 г.). «Алгоритм 795: PHCpack: универсальный решатель для полиномиальных систем путем гомотопического продолжения». Транзакции ACM на математическом ПО. 25 (2): 251–276. Дои:10.1145/317275.317286.

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

• Домашняя страница Бертини
• Хом4ПС-3
• HomotopyContinuation.jl