Electronic Thesis and Dissertation Repository

Degree

Doctor of Philosophy

Program

Computer Science

Supervisor

Marc Moreno Maza

Abstract

Finding the solutions of a polynomial system is a fundamental problem with numerous applications in both the academic and industrial world. In this thesis, we target on computing symbolically both the real and the complex solutions of nonlinear polynomial systems with or without parameters. To this end, we improve existing algorithms for computing triangular decompositions. Based on that, we develop various new tools for solving polynomial systems and illustrate their effectiveness by applications.

We propose new algorithms for computing triangular decompositions of polynomial systems incrementally. With respect to previous works, our improvements are based on a weakened notion of a polynomial GCD modulo a regular chain, which permits to greatly simplify and optimize the sub-algorithms. Extracting common work from similar expensive computations is also a key feature of our algorithms.

We adapt the concepts of regular chain and triangular decomposition, originally designed for studying the complex solutions of polynomial systems, to describing the solutions of semi-algebraic systems. We show that any such system can be decomposed into finitely many regular semi-algebraic systems. We propose two specifications (full and lazy) of such a decomposition and present corresponding algorithms. Under some assumptions, the lazy decomposition can be computed in singly exponential time w.r.t. the number of variables.

We introduce the concept of {\em comprehensive triangular decomposition} for solving parametric polynomial systems. It partitions the parametric space into disjoint cells such that the complex or real solutions of a polynomial system depend continuously on the parameters in each cell. In the real case, we rely on cylindrical algebraic decomposition (CAD) to decompose a cell into connected components. CAD itself is one of the most important tools for computing with semi-algebraic sets. We present a brand new algorithm for computing it based on triangular decomposition.

Download

Share

COinS