ICMS 2020 Session

Real Algebraic Geometry

Accepted Talk

Akshar Nair (University of Bath)
Curtains in CAD: Why are they a problem and how do we fix them?
Abstract: When computing a Cylindrical Algebraic Decomposition via McCallum’s method, we require that the polynomials are well-oriented. Rather than just saying well-oriented, we have introduced a more geometric term: curtain. We say that f in R[x1, ...,xn] has a curtain over the subset W of R^(n-1) if for all x in W and y in R$ we have f(x,y)=0. Curtains have been an inherent problem (known as badly oriented in McCallum's work) whilst computing a Cylindrical Algebraic Decomposition of R^n. Lazard's method of computing CAD, which computes lex-least valuation invariant CADs rather than order or sign invariant CADs, is also the first to address the problems that curtains pose. In this talk I will discuss the problem of having curtains in the equational constraint and provide various approaches to dealing with them. Further to this I will discuss our extension to Lazard's work for single level propagation of equational constraint, curtain detection and using partial CADs.