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

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

Продолжение гомотопии [ править ]

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

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

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

H(z,t)=(1-t)f(z)+tg(z).

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

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

У человека есть выбор в $g(z)$ , включая

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

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

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

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

Набор свидетелей [ править ]

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

Сертификация [ править ]

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

Программное обеспечение [ править ]

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

альфасертифицированный ^[9]
Бертини ^[5]
Хом4ПС ^[10]^[11]
HomotopyContinuation.jl ^[12]
Macaulay2 (основная реализация отслеживания гомотопий и NumericalAlgebraicGeometry^[3] упаковка)
PHPпак ^[13]

Ссылки [ править ]

^ Хауэнштайн, Джонатан Д.; Соммесе, Эндрю Дж. (март 2017 г.). «Что такое числовая алгебраическая геометрия?» . Журнал символических вычислений . 79 : 499–507. дои : 10.1016/j.jsc.2016.07.015 .
^ Соммесе, Эндрю Дж.; Вершельде, Ян; Вамплер, Чарльз В. (2005). «Введение в численную алгебраическую геометрию». У Бронштейна, Мануэля; Коэн, Арье М.; Коэн, Анри; Эйзенбуд, Дэвид; Штурмфельс, Бернд; Дикенштейн, Алисия; Эмирис, Иоаннис З. (ред.). Решение полиномиальных уравнений: основы, алгоритмы и приложения (PDF) . Издательство Спрингер. дои : 10.1007/3-540-27357-3_8 . ISBN 978-3-540-24326-7 .
^ Jump up to: ^а ^б Лейкин, Антон (01 января 2000 г.). «Численная алгебраическая геометрия» . Журнал программного обеспечения для алгебры и геометрии . 3 (1): 5–10. дои : 10.2140/jsag.2011.3.5 . ISSN 1948-7916 .
^ Соммесе, Эндрю Дж.; Уэмплер, II, Чарльз В. (2005). Численное решение систем полиномов, возникающих в технике и науке . Всемирная научная. ISBN 978-981-256-184-8 .
^ Jump up to: ^а ^б Бейтс, Дэниел Дж.; Соммесе, Эндрю Дж.; Хауэнштайн, Джонатан Д.; Уэмплер, Чарльз В. (2013). Численное решение полиномиальных систем с помощью Бертини . Общество промышленной и прикладной математики. ISBN 978-1-61197-269-6 .
^ Чен, Тяньрань; Ли, Тянь-Иен (2015). «Метод гомотопического продолжения решения систем нелинейных и полиномиальных уравнений» . Коммуникации в информации и системах . 15 (2): 276–277. дои : 10.4310/CIS.2015.v15.n2.a1 .
^ Бельтран, Карлос; Лейкин, Антон (01 марта 2012 г.). «Сертифицированное числовое отслеживание гомотопии». Экспериментальная математика . 21 (1): 69–83. arXiv : 0912.0920 . дои : 10.1080/10586458.2011.606184 . ISSN 1058-6458 . S2CID 2889087 .
^ Бельтран, Карлос; Лейкин, Антон (01 февраля 2013 г.). «Надежное сертифицированное числовое отслеживание гомотопий». Основы вычислительной математики . 13 (2): 253–295. arXiv : 1105.5992 . дои : 10.1007/s10208-013-9143-2 . ISSN 1615-3375 . S2CID 32990257 .
^ Jump up to: ^а ^б Хауэнштайн, Джонатан Д.; Соттайл, Фрэнк (август 2012 г.). «Алгоритм 921: AlphaCertified: сертификация решений полиномиальных систем». Транзакции ACM в математическом программном обеспечении . 38 (4): 1–20. дои : 10.1145/2331130.2331136 . S2CID 13821271 .
^ Чен, Т.; Ли, ТЛ; Ли, Тайвань (2014). «Hom4PS-3: параллельный численный решатель систем полиномиальных уравнений на основе методов продолжения полиэдральной гомотопии» . Ин Хонг, Х.; Яп, К. (ред.). Математическое программное обеспечение -- ICMS 2014: 4-й Международный конгресс, Сеул, Южная Корея, 5-9 августа 2014. Труды . стр. 183–190. дои : 10.1007/978-3-662-44199-2_30 . ISBN 978-3-662-44199-2 . Проверено 28 апреля 2020 г.
^ Команда Хом4ПС. «Рекомендуемые товары» . Хом4ПС-3 . Мичиганский государственный университет . Проверено 28 апреля 2020 г. {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )
^ Брейдинг, Пол; Тимме, Саша (май 2018 г.). «HomotopyContinuation.jl: пакет для продолжения гомотопии в Julia». arXiv : 1711.10911v2 [ cs.MS ].
^ Вершельде, январь (1 июня 1999 г.). «Алгоритм 795: PHCpack: универсальный решатель для полиномиальных систем путем гомотопического продолжения» . Транзакции ACM в математическом программном обеспечении . 25 (2): 251–276. дои : 10.1145/317275.317286 . S2CID 15485257 .

Внешние ссылки [ править ]

[1] Хауэнштайн, Джонатан Д.; Соммесе, Эндрю Дж. (март 2017 г.). «Что такое числовая алгебраическая геометрия?» . Журнал символических вычислений . 79 : 499–507. дои : 10.1016/j.jsc.2016.07.015 .

[2] Соммесе, Эндрю Дж.; Вершельде, Ян; Вамплер, Чарльз В. (2005). «Введение в численную алгебраическую геометрию». У Бронштейна, Мануэля; Коэн, Арье М.; Коэн, Анри; Эйзенбуд, Дэвид; Штурмфельс, Бернд; Дикенштейн, Алисия; Эмирис, Иоаннис З. (ред.). Решение полиномиальных уравнений: основы, алгоритмы и приложения (PDF) . Издательство Спрингер. дои : 10.1007/3-540-27357-3_8 . ISBN 978-3-540-24326-7 .

[Macaulay2-3] Jump up to: ^а ^б Лейкин, Антон (01 января 2000 г.). «Численная алгебраическая геометрия» . Журнал программного обеспечения для алгебры и геометрии . 3 (1): 5–10. дои : 10.2140/jsag.2011.3.5 . ISSN 1948-7916 .

[4] Соммесе, Эндрю Дж.; Уэмплер, II, Чарльз В. (2005). Численное решение систем полиномов, возникающих в технике и науке . Всемирная научная. ISBN 978-981-256-184-8 .

[Bertini-5] Jump up to: ^а ^б Бейтс, Дэниел Дж.; Соммесе, Эндрю Дж.; Хауэнштайн, Джонатан Д.; Уэмплер, Чарльз В. (2013). Численное решение полиномиальных систем с помощью Бертини . Общество промышленной и прикладной математики. ISBN 978-1-61197-269-6 .

[6] Чен, Тяньрань; Ли, Тянь-Иен (2015). «Метод гомотопического продолжения решения систем нелинейных и полиномиальных уравнений» . Коммуникации в информации и системах . 15 (2): 276–277. дои : 10.4310/CIS.2015.v15.n2.a1 .

[7] Бельтран, Карлос; Лейкин, Антон (01 марта 2012 г.). «Сертифицированное числовое отслеживание гомотопии». Экспериментальная математика . 21 (1): 69–83. arXiv : 0912.0920 . дои : 10.1080/10586458.2011.606184 . ISSN 1058-6458 . S2CID 2889087 .

[8] Бельтран, Карлос; Лейкин, Антон (01 февраля 2013 г.). «Надежное сертифицированное числовое отслеживание гомотопий». Основы вычислительной математики . 13 (2): 253–295. arXiv : 1105.5992 . дои : 10.1007/s10208-013-9143-2 . ISSN 1615-3375 . S2CID 32990257 .

[alphaCertified-9] Jump up to: ^а ^б Хауэнштайн, Джонатан Д.; Соттайл, Фрэнк (август 2012 г.). «Алгоритм 921: AlphaCertified: сертификация решений полиномиальных систем». Транзакции ACM в математическом программном обеспечении . 38 (4): 1–20. дои : 10.1145/2331130.2331136 . S2CID 13821271 .

[10] Чен, Т.; Ли, ТЛ; Ли, Тайвань (2014). «Hom4PS-3: параллельный численный решатель систем полиномиальных уравнений на основе методов продолжения полиэдральной гомотопии» . Ин Хонг, Х.; Яп, К. (ред.). Математическое программное обеспечение -- ICMS 2014: 4-й Международный конгресс, Сеул, Южная Корея, 5-9 августа 2014. Труды . стр. 183–190. дои : 10.1007/978-3-662-44199-2_30 . ISBN 978-3-662-44199-2 . Проверено 28 апреля 2020 г.

[11] Команда Хом4ПС. «Рекомендуемые товары» . Хом4ПС-3 . Мичиганский государственный университет . Проверено 28 апреля 2020 г. {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )

[12] Брейдинг, Пол; Тимме, Саша (май 2018 г.). «HomotopyContinuation.jl: пакет для продолжения гомотопии в Julia». arXiv : 1711.10911v2 [ cs.MS ].

[13] Вершельде, январь (1 июня 1999 г.). «Алгоритм 795: PHCpack: универсальный решатель для полиномиальных систем путем гомотопического продолжения» . Транзакции ACM в математическом программном обеспечении . 25 (2): 251–276. дои : 10.1145/317275.317286 . S2CID 15485257 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

v т и Основные математики области
History Timeline Future Lists Glossary
Foundations	Category theory Information theory Mathematical logic Philosophy of mathematics Set theory Type theory
Algebra	Abstract Commutative Elementary Group theory Linear Multilinear Universal Homological
Analysis	Calculus Real analysis Complex analysis Hypercomplex analysis Differential equations Functional analysis Harmonic analysis Measure theory
Discrete	Combinatorics Graph theory Order theory
Geometry	Algebraic Analytic Arithmetic Differential Discrete Euclidean Finite
Number theory	Arithmetic Algebraic number theory Analytic number theory Diophantine geometry
Topology	General Algebraic Differential Geometric Homotopy theory
Applied	Engineering mathematics Mathematical biology Mathematical chemistry Mathematical economics Mathematical finance Mathematical physics Mathematical psychology Mathematical sociology Mathematical statistics Probability Statistics Systems science Control theory Game theory Operations research
Computational	Computer science Theory of computation Computational complexity theory Numerical analysis Optimization Computer algebra
Related topics	Mathematicians lists Informal mathematics Films about mathematicians Recreational mathematics Mathematics and art Mathematics education
Mathematics portal Category Commons WikiProject