Browse Theses

This thesis proposes efficient algorithmic solutions to problems in computational algebra and computational algebraic geometry. Moreover, it considers their application to different areas where algebraic systems describe kinematic and geometric constraints.

Given an arbitrary system of nonlinear multivariate polynomial equations, its resultant serves in eliminating variables and reduces root finding to a linear eigenproblem. Our contribution is to describe the first efficient and general algorithms for computing the sparse resultant. The sparse resultant generalizes the classical homogeneous resultant and exploits the structure of the given polynomials. Its size depends only on the geometry of the input Newton polytopes.

The first algorithm uses a subdivision of the Minkowski sum and produces matrix formulae whose sizes are well-characterized. The second algorithm uses a heuristic in order to construct smaller matrices, which are typically within a factor of three of optimal size. For most systems an optimal matrix formula does not exist, yet the second algorithm produces optimal matrices in all cases where they are known to exist.

The sparseness of the system is expressed by its mixed volume, which gives an upper bound on the number of isolated roots. A refinement of Sturmfels' algorithm is proposed which is very fast and has been used to derive new degree bounds for a class of benchmarks.

Two methods based on the sparse resultant are implemented for calculating the common roots and then applied to concrete problems in robotics, vision and molecular kinematics. This illustrates our claim that problems from these areas often exhibit structure that can be exploited in the context of sparse elimination. Our solver finds all isolated solutions to satisfactory accuracy and speed; furthermore, its generality should establish it as the method of choice for systems of moderate size.

The last chapter discusses the problem of input degeneracy which frequently arises in implementations of geometric as well as algebraic algorithms. The perturbation methods proposed are computationally optimal for certain classes of algorithms and simple to implement as illustrated by our convex hull implementation.