Design, Analysis and Implementation of Efficient and Reliable Algorithms for Complex Geometric Objects

Project Description

A crucial building block for algorithms in exact geometric computing (e.g., arrangement computation of (semi-)algebraic curves or surfaces) is devoted to polynomial system solving for zero-dimensional systems in one, two or three variables. The proposed research focuses on the combination of fast approximate and exact symbolic methods. Moreover, we aim for methods that are well suited for parallel computation and may therefore profit from being implemented on modern graphics hardware. Through this approach, we intend to achieve adaptiveness and a significant speedup for the most important basic operations within geometric algorithms.

All existing exact and practical methods to isolate the roots of a zero-dimensional polynomial system are based on elimination techniques such as multivariate resultants, rational univariate representation (RUR) or Gröbner bases. These are well-studied tools to obtain the solution set of a system with respect to a projection direction. They are usually combined with a certified univariate root isolator. In one step, this is done in order to isolate the roots of the elimination polynomial, and in another step, in order to lift the solutions to the initial dimension. In taking this approach, a severe drawback in regard to performance results from the coefficient explosion during computations of the elimination polynomial. Another drawback is that the lifting operation assumes additional knowledge (e.g., from computation of a sub-resultant sequence) which can only be obtained by costly symbolic operations. Moreover, existing approaches have to detect degenerate situations (e.g., more than one solution with the same x-coordinate) and perform a shearing of the system, an operation which causes high additional costs in the subsequent steps.

There is an algorithm for bivariate resultant computation and its implementation on graphics hardware. In comparison to existing implementations on the CPU, where a signed remainder sequence is computed, we directly evaluate the determinant of the Sylvester matrix. In a first step, this computation is carried out for many interpolation points in a modular field and for many different prime numbers; thus, it profits from the parallel architecture on the GPU. Furthermore, we exploit the special structure (low displacement rank) of the Sylvester matrix to speed up the evaluation of the determinant. Finally, the modular results are lifted to a solution, an operation which is also partially carried out on the GPU. The results are very promising, because for the resultant computation, we achieve a speedup by a factor in the case of typical examples. Hence, the resultant computation is no longer the bottleneck of an algorithm to isolate the roots of a polynomial system or to compute the topology of an algebraic curve.

In collaboration with Eric Berberich (MPII, D1), we are working on a solver for bivariate polynomial systems which is built on top of the above resultant algorithm. It uses a new lifting method which allows the costly computation of a sub-resultant sequence to be eliminated. Furthermore, a general position assumption is no longer needed. For several examples, we compared our implementation to other existing, efficient methods such as those provided by Maple or CGAL. With respect to the corresponding timings, our new method far outperforms the other implementations. In the future, we aim to finalize our implementation and to determine the bit complexity of the overall method. We are confident that we will, at minimum, match the currently known record bounds.