  Let $S\subset 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\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.

Symbolic Computation