Computing over Quadratic Maps I: Sampling in Real Algebraic Sets

Title: Computing over Quadratic Maps I: Sampling in Real Algebraic Sets

Research Question: How can we efficiently compute the zero set of a quadratic map in a real closed field?

Methodology: The authors use symbolic computation, a technique where all data is represented exactly, as real univariate representations. They extend the real field by infinitesimals and perform limit computations to achieve their results.

Results: The authors present a procedure that computes, in ( dn)O(k)arithmetic operations in D, a set S of sampling points that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the standard methods that have exponential dependence on n. They also provide a bound ( dn)O(k) on the number of connected components of Z.

Implications: This research has significant implications for the field of real algebraic geometry. The procedure provides a faster way to compute the zero set of a quadratic map, which is a fundamental problem in this field. The results also have practical applications in areas such as computer graphics, computer-aided design, and scientific computing.

Link to Article: https://arxiv.org/abs/0403008v3 Authors: arXiv ID: 0403008v3