Journal
PROCEEDINGS OF THE 2019 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION (ISSAC '19)
Volume -, Issue -, Pages 259-266Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3326229.3326262
Keywords
Semi-algebraic sets; Picard-Fuchs equations; Symbolic-numeric algorithms
Funding
- ANR [ANR-17-CE40-0009, ANR-18-CE33-0011, ANR-14-CE25-0018-01]
- PGMO grant Gamma
- European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant [813211]
- Agence Nationale de la Recherche (ANR) [ANR-14-CE25-0018] Funding Source: Agence Nationale de la Recherche (ANR)
Ask authors/readers for more resources
Let S subset of R-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 >= 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available