Publication:2819779

DOI10.1145/2755996.2756677zbMATH Open1345.68296arXiv1501.04836OpenAlexW1982469375MaRDI QIDQ2819779FDOQ2819779

Thomas Sturm

Publication date: 29 September 2016

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

Abstract: We describe a new incomplete but terminating method for real root finding for large multivariate polynomials. We take an abstract view of the polynomial as the set of exponent vectors associated with sign information on the coefficients. Then we employ linear programming to heuristically find roots. There is a specialized variant for roots with exclusively positive coordinates, which is of considerable interest for applications in chemistry and systems biology. An implementation of our method combining the computer algebra system Reduce with the linear programming solver Gurobi has been successfully applied to input data originating from established mathematical models used in these areas. We have solved several hundred problems with up to more than 800000 monomials in up to 10 variables with degrees up to 12. Our method has failed due to its incompleteness in less than 8 percent of the cases.

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

zbMATH Keywords

linear programmingreal rootlarge polynomial

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Linear programming (90C05) Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Cited In (2)

• A survey of some methods for real quantifier elimination, decision, and satisfiability and their applications
• raSAT: an SMT solver for polynomial constraints

Uses Software

• REDUCE
• Gurobi

This page was built for publication: Subtropical real root finding

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