Computing the volume of compact semi-algebraic sets

DOI10.1145/3326229.3326262MaRDI QIDQ5121115zbMATH OpenOpenAlexFDO

Authors Pierre Lairez, Marc Mezzarobba, Mohab Safey El Din

Publication date 10 September 2020

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

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

zbMATH Keywords

Picard-Fuchs equationssemi-algebraic setssymbolic-numeric algorithms

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: Let $Ssubset{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 $pgeq0$ 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.

Recommendations

• Approximate volume and integration for basic semialgebraic sets
• scientific article; zbMATH DE number 1254270
• Computing periods
• Exploiting sparsity for semi-algebraic set volume computation
• Computing the volume, counting integral points, and exponential sums

Cited in

(13)

• High-order quadrature on multi-component domains implicitly defined by multivariate polynomials
• Computing periods
• Efficient sampling in spectrahedra and volume approximation
• Efficient and validated numerical evaluation of abelian integrals
• Minimizing rational functions: a hierarchy of approximations via pushforward measures
• Approximate volume and integration for basic semialgebraic sets
• Nonlinear algebra and applications
• D-modules and holonomic functions
• scientific article; zbMATH DE number 1254270 (Why is no real title available?)
• Computing the Hausdorff boundary measure of semialgebraic sets
• Linear differential equations as a data structure
• Stokes, Gibbs, and volume computation of semi-algebraic sets
• Exploiting sparsity for semi-algebraic set volume computation

This page was built for publication: Computing the volume of compact semi-algebraic sets

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