Name
Abstract | ||
|---|---|---|
Let S\subset \bR^n be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We design an algorithm which takes as input a polynomial system defining S and an integer p\geq 0 and returns the n-dimensional volume of S at absolute precision 2^-p . Our algorithm relies on the relationship between volumes of semi-algebraic sets and periods of rational integrals. It makes use of algorithms computing the Picard-Fuchs differential equation of appropriate periods, properties of critical points, and high-precision numerical integration of differential equations. The algorithm runs in essentially linear time with respect to~p. This improves upon the previous exponential bounds obtained by Monte-Carlo or moment-based methods. Assuming a conjecture of Dimca, the arithmetic cost of the algebraic subroutines for computing Picard-Fuchs equations and critical points is singly exponential in n and polynomial in the maximum degree of the input.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3326229.3326262 | Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation |
Keywords | Field | DocType |
picard-fuchs equations, semi-algebraic sets, symbolic-numeric algorithms | Differential equation,Discrete mathematics,Algebraic number,Exponential function,Polynomial,Computer science,Numerical integration,Degree (graph theory),Solution set,Time complexity | Journal |
ISSN | ISBN | Citations |
International Symposium on Symbolic and Algebraic Computation, Jul
2019, Beijing, China | 978-1-4503-6084-5 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pierre Lairez | 1 | 27 | 4.46 |
| Marc Mezzarobba | 2 | 40 | 6.13 |
| Mohab Safey El Din | 3 | 450 | 35.64 |