Solving polynomial systems via homotopy continuation and monodromy

被引：35

作者：

Duff, Timothy ^{[1
]}

Hill, Cvetelina ^{[1
]}

Jensen, Anders ^{[2
]}

Lee, Kisun ^{[1
]}

Leykin, Anton ^{[1
]}

Sommars, Jeff ^{[3
]}

机构：

[1] Georgia Inst Technol, Dept Math, Atlanta, GA 30332 USA

[2] Aarhus Univ, Dept Math, Aarhus, Denmark

[3] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60680 USA

来源：

IMA JOURNAL OF NUMERICAL ANALYSIS | 2019年 / 39卷 / 03期

基金：

美国国家科学基金会;

关键词：

homotopy continuation; monodromy; polynomial system solvers; SOLUTION SETS; PROBABILITY;

D O I：

10.1093/imanum/dry017

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study methods for finding the solution set of a generic system in a family of polynomial systems with parametric coefficients. We present a framework for describing monodromy-based solvers in terms of decorated graphs. Under the theoretical. that monodromy actions are generated uniformly, we show that the expected number of homotopy paths tracked by an algorithm following this framework is linear in the number of solutions. We demonstrate that our software implementation is competitive with the existing state-of-the-art methods implemented in other software packages.

引用

页码：1421 / 1446

页数：26

共 34 条

[21] Leykin A., 2016, ARXIV160800540
[22] Decomposing solution sets of polynomial systems: a new parallel monodromy breakup algorithm
Leykin, Anton
Verschelde, Jan
[J]. INTERNATIONAL JOURNAL OF COMPUTATIONAL SCIENCE AND ENGINEERING, 2009, 4 (02) : 94 - 101
[23] GALOIS GROUPS OF SCHUBERT PROBLEMS VIA HOMOTOPY COMPUTATION
Leykin, Anton
Sottile, Frank
[J]. MATHEMATICS OF COMPUTATION, 2009, 78 (267) : 1749 - 1765
[24] Parameter-free methods distinguish Wnt pathway models and guide design of experiments
MacLean, Adam L.
Rosen, Zvi
Byrne, Helen M.
Harrington, Heather A.
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2015, 112 (09) : 2652 - 2657
[25] Computing Mixed Volume and All Mixed Cells in Quermassintegral Time
Malajovich, Gregorio
[J]. FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2017, 17 (05) : 1293 - 1334
[26] Critical points via monodromy and local methods
Martin del Campo, Abraham
Rodriguez, Jose Israel
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 2017, 79 : 559 - 574
[27] MORGAN A. P., 1987, Solving Polynomial Systems Using Continuationfor Engineering and Scientific Computations
[28] A NEURAL NETWORK MODELED BY AN ADAPTIVE LOTKA-VOLTERRA SYSTEM
NOONBURG, VW
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1989, 49 (06) : 1779 - 1792
[29] Sommese AJ, 2005, ALGORITHM COMP MATH, V14, P301
[30] Sommese AJ, 2003, SIAM J NUMER ANAL, V40, P2026

← 1 2 3 4 →