Elimination Without Eliminating: Computing Complements of Real Hypersurfaces Using Pseudo-Witness Sets
This work addresses a computational bottleneck in algebraic geometry for researchers and practitioners by providing a more efficient alternative to existing elimination-based methods.
The paper tackles the problem of computing the real complement of a hypersurface in algebraic geometry, which partitions space into open regions, by introducing a method that avoids the computationally demanding step of explicit elimination. The result is an algorithm implemented in a Julia package that accurately recovers all regions, as demonstrated on several examples.
Many hypersurfaces in algebraic geometry, such as discriminants, arise as the projection of another variety. The real complement of such a hypersurface partitions its ambient space into open regions. In this paper, we propose a new method for computing these regions. Existing methods for computing regions require the explicit equation of the hypersurface as input. However, computing this equation by elimination can be computationally demanding or even infeasible. Our approach instead derives from univariate interpolation by computing the intersection of the hypersurface with a line. Such an intersection can be done using so-called pseudo-witness sets without computing a defining equation for the hypersurface - we perform elimination without actually eliminating. We implement our approach in a forthcoming Julia package and demonstrate, on several examples, that the resulting algorithm accurately recovers all regions of the real complement of a hypersurface.