Algorithm 976: Bertini_real: Numerical Decomposition of Real Algebraic Curves and Surfaces

作者：Brake Daniel A^*; Bates Daniel J; Hao Wenrui; Hauenstein Jonathan D; Sommese Andrew J; Wampler Charles W

来源：ACM Transactions on Mathematical Software, 2017, 44(1): 10.

DOI：10.1145/3056528

• Solvers
• Nonlinear Equations
• Computations on Polynomials
• Numerical algebraic geometry
• homotopy continuation
• polynomial system
• real solutions
• cell decompositions

Bertini_real is a compiled command line program for numerically decomposing the real portion of a positive-dimensional complex component of an algebraic set. The software uses homotopy continuation to solve a series of systems via regeneration from a witness set to compute a cell decomposition. The implemented decomposition algorithms are similar to the well-known cylindrical algebraic decomposition (CAD) first established by Collins in that they produce a set of connected cells. In contrast to the CAD, Bertini_real produces cells with midpoints connected to boundary points by homotopies, which can easily be numerically tracked. Furthermore, the implemented decomposition for surfaces naturally yields a triangulation. This CAD-like decomposition captures the topological information and permits further computation on the real sets, such as sampling, visualization, and three-dimensional printing.

• 出版日期2017-7