Rafael Mohr

• Algebraic sets, i.e. solution sets of polynomial systems of equations,model a wide variety of nonlinear problems, both in applied and pure mathematics. One of the most foundational results in algebraic geometry sais that every algebraic set has a unique decomposition into irreducible algebraic sets and a frequent task is to decompose such an algebraic set into its irreducible components, or to produce some kind of coarser decomposition of the algebraic set in question. This task comes up for example in certain problems in robotics on the applied side and enumerative geometry on the pure side. In this thesis, we present a series of algorithms solving such decomposition problems for algebraic sets. All of these algorithms use Gröbner bases for polynomial ideals at their core. Gröbner bases are an ubiquitous tool in symbolic computation. They form the core of many higher level algorithms and are implemented in all prominent computer algebra systems. Three of these algorithms produce so-called equidimensional decompositions of an algebraic set, i.e. they partition a given algebraic set dimension-by-dimension. They are designed to avoid potentially costly elimination operations and, partially, use features of so-called {\em signature-based} Gröbner basis algorithms. Our software implementations of these algorithms showcase their practical efficiency compared to state-of-the-art computer algebra systems on examples of interest. Another set of algorithms (respectively based on the F4 algorithm and the FGLM algorithm use Hensel lifting methods in a novel way to compute Gröbner bases for generic fibers of polynomial ideals. We outline how these algorithms can be used as a core piece in known algorithms for equidimensional or irreducible decomposition of an algebraic set and exhibit their quasi-linear complexity in the precision up to which certain power series are computed. Finally, we give an extension of generic fiber techniques for equidimensional decomposition of algebraic sets to compute Whitney stratifications of singular algebraic sets, improving on the state of the art. A Whitney stratification partitions a singular algebraic set into smooth pieces in a desirable way and has applications, for example, in physics. We, in addition, give an algorithm to minimize a given Whitney stratification.