Back to search

University of Waterloo

Analysis of Randomized Algorithms in Real Algebraic Geometry

Abstract

dc:description.abstract

Consider the problem of computing at least one point in each connected component of a smooth real algebraic set. This is a basic and important operation in real and semi-algebraic geometry: it gives an upper bound on the number of connected components of the algebraic set, it can be used to decide if the algebraic set has real solutions, and it is also used as a subroutine in many higher-level algorithms. We consider an algorithm for this problem by Safey El Din and Schost: "Polar varieties and computation of one point in each connected component of a smooth real algebraic set," (ISSAC'03). This algorithm uses random changes of variables that are proven to generically ensure certain desirable geometric properties. The cost of the algorithm was given in an algebraic complexity model, and the analysis of the bit complexity and the error probability were left for future work. We also consider another algorithm that solves a special case of the problem. Namely, when the algebraic set is a compact hypersurface. We determine the bit complexity and error probability of these algorithms. Our main contribution is a quantitative analysis of several genericity statements, such as Thom's weak transversality theorem and Noether normalization properties for polar varieties. Furthermore, in doing this work, we have developed techniques that can be used in the analysis of further randomized algorithms in real algebraic geometry, which rely on related genericity properties.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Elliott, Jesse
Advisors dc:contributor.advisor
  • Schost, Eric
  • Giesbrecht, Mark

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/16236

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Elliott, Jesse. Analysis of Randomized Algorithms in Real Algebraic Geometry. University of Waterloo, 2020. http://hdl.handle.net/10012/16236