Monodromy solver. Sequential and parallel

DOI10.1145/3208976.3209007MaRDI QIDQ5120182zbMATH OpenOpenAlexFDO

Authors Nathan Bliss, Timothy Duff, Anton Leykin, Jeff Sommars

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.12212

zbMATH Keywords

homotopy continuationmonodromyparallel computationprobabilistic algorithmsolving systems of polynomial equations

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Randomized algorithms (68W20)

Abstract: We describe, study, and experiment with an algorithm for finding all solutions of systems of polynomial equations using homotopy continuation and monodromy. This algorithm follows a framework developed in previous work and can operate in the presence of a large number of failures of the homotopy continuation subroutine. We give special attention to parallelization and probabilistic analysis of a model adapted to parallelization and failures. Apart from theoretical results, we developed a simulator that allows us to run a large number of experiments without recomputing the outcomes of the continuation subroutine.

Recommendations

• Solving polynomial systems via homotopy continuation and monodromy
• The granularity of parallel homotopy algorithms for polynomial systems of equations
• Parallel Homotopy Algorithms to Solve Polynomial Systems
• Algorithm 857
• Computing all solutions to polynomial systems using homotopy continuation

Cited in

(10)

• A blackbox polynomial system solver on parallel shared memory computers
• Using monodromy to statistically estimate the number of solutions
• Real monodromy action
• MonodromySolver
• Using monodromy to avoid high precision in homotopy continuation
• Exploiting symmetry in the power flow equations using monodromy
• Solving polynomial systems via homotopy continuation and monodromy
• Computing monodromy via continuation methods on random Riemann surfaces
• Monodromy coordinates
• Pure D-brane black holes: BPS counting and non-BPS vacua

Describes a project that uses

Uses Software

• PHCpack
• PHoMpara
• Macaulay2

This page was built for publication: Monodromy solver. Sequential and parallel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120182)