ICMS 2014 Session: Software for Algebraic Curves and Surfaces

ICMS 2014: Home, Sessions

Organizers

Aim and Scope

Curves and Surfaces play a fundamental role in many fields, such as Computational Geometry, Computer Aided Design, Computer Graphics, Geometric Modeling to name a few. Consequently, softwares that provide functionalities to handle them are very important. The aim of this session is to facilitate communication between researchers who have developed or plan to develop mathematical software related to curves and surfaces. The softwares could be, for instance, for handling arrangements of curves and surfaces, or visualizing them, or using them as a tool in various applications. We welcome talks that highlight some of the mathematical and algorithmic challenges that are faced in designing softwares for curves and surfaces, and demonstrate some of the recent advances made in this direction.

Topics (including, but not limited to)

Publications

Submission Guidelines

Talks/Abstracts

  1. Robustly and Efficiently Computing Algebraic Curves and Surfaces

    Eric Berberich (Max-Planck-Institut f¨¹r Informatik)

    Abstract: Computing with curved geometric objects forms the basis for many algorithms in areas such as geometric modeling, computer aided design and robot motion planning. In general, such computations cannot be carried out reliably with standard machine precision arithmetic.

    Slightly more than a decade ago robustly and efficiently dealing with conics and B\'ezier curves in 2D and quadrics and splines in 3D was considered an enormous challenge. This picture has changed. Our first successes were achieved for conics and quadrics, mainly relying on properties of the involved low-degree polynomials. In a second step, to tackle general algebraic curves and surfaces, we exploited more involved mathematical tools such as subresultants. In addition with clever filtering techniques, these methods already beat the previous specialized solutions. The most recent drastical success in performance gain for algebraic curves is due to several ingredients: The central one consists of a cylindrical algebraic decomposition with a revised lifting step. Using results from algebraic geometry we avoid any change of coordinates and replace the costly symbolic operations by numerical tools. The new algorithms for curve topology computation only need to compute the resultant and the gcd of bivariate polynomials and to perform numerical root finding. For the symbolic operations, we can rely on implementations exploiting graphics hardware, which is several magnitudes faster than corresponding CPU implementations.

    All algorithms have been implemented as contributions to the C++ project CGAL. Excellent practical behavior of our algorithms has been shown in exhaustive sets of experiments, where we compared them with our previous and recent competing approaches. Beyond, the algorithms are also proven to be efficient in theory. Recent work shows that our implemented and practical algorithm needs O(d^6 + d^5\tau) bit operations ($d$ degree, $\tau$ bitsize of coefficients, ignoring log factors) to compute the topology of an algebraic curve and for solving bivariate systems.

    Joint work with Pavel Emeliyanenko, Michael Kerber, Kurt Mehlhorn, Michael Sagraloff, Alexander Kobel, and Pengming Wang.

  2. Numerical algebraic geometric techniques for real curves and surfaces

    Jonathan Hauenstein (North Carolina State University/University of Notre Dame)

    Abstract: The computation of the real points on a complex algebraic set has many applications in biology, chemistry, engineering, and physics as well as visualization and 3D printing. In 2007, Lu, Bates, Sommese, and Wampler proposed a numerical algebraic geometric approach for computing the real points on a complex curve. This approach was extended to surfaces in 2013 in joint work with Besana, Di Rocco, Sommese, and Wampler. This talk will summarize these techniques, discuss recently developed algorithms in numerical real algebraic geometry, and demonstrate these techniques via the software package BertiniReal, which is an ongoing joint project with D. Bates (Colorado State), D. Brake (North Carolina State), W. Hao (MBI), A. Sommese (Notre Dame), and C. Wampler (General Motors).

  3. Root Refinement for Real Polynomials

    Michael Kerber (Max-Planck-Institut f¨¹r Informatik ,Germany)

    Abstract: We consider the problem of approximating all real roots of a square-free polynomial $f$. Given isolating intervals, our algorithm refines each of them to a width of $2^{-L}$ or less, that is, each of the roots is approximated to $L$ bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only considering finite approximations of the polynomial coefficients and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating $f$, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of the degree of the polynomial, the size and the separation of the roots, that is, parameters exclusively related to the geometric location of the roots. Our bound is near optimal and significantly improves previous work on integer polynomials. Furthermore, it essentially matches the best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms. We also investigate the practical behavior of the algorithm and demonstrate how closely the practical performance matches our asymptotic bounds. It is a joint work with Michael Sagraloff.

  4. Isotopic Epsilon-approximation of algebraic curves

    Kai Jin (Key Lab of Mathematics Mechanization, AMSS, CAS)

    Abstract: In this paper, we will introduce our implementation for isotopic approximation of plane and space algebraic curves.

    The important basic algorithm used in our implementation is real solving of zero-dimensional polynomial systems, especially for bivariate polynomial systems. We use a generic position based method for the solving. It mainly involves resultant computation and real root isolation for univariate polynomials. The roots of the system have a linear univariate representation. The implementation shows that the method is efficient, especially for bivariate polynomial systems.

    We present an algorithm to compute the topology of a plane curve. Compared to other symbolic methods based on elimination technique, the novelty of our method is that we can get many simple roots of the fibers when computing the critical points of the plane curve, which improves the lifting step since we need not compute the left simple roots on the fibers any more. We also give the complexity analysis. After the topology is computed, we also give a certified approximation for the plane curve, which is a basic operation for approximating a space curve.

    As to the topology computation for the space curve, we first present a method to check whether an algebraic space curve is in a generic position or not. Then we give a method to find a shearing transformation such that the sheared space curve is in a generic position. The most important is, the bitsizes of the transformed polynomials are much smaller compared to the ones of former method's. Thus the efficiency of the algorithm is highly improved. We also give an isotopic approximation of the space curve after we obtain its topology.

    We implemented our algorithms in Maple 15. The benchmarks show the efficiency of our implementation.

  5. Computing The Orthogonal Projection of Rational Curves Onto Rational Parameterized Surface by Symbolic Methods

    Zhiwang Gan, Meng Zhou (School of mathematics and system science,Beihang university)

    Abstract: This paper presents three algorithms to compute orthogonal projection of rational curves onto rational parameterized surface. One of them, based on regular systems, is able to compute the exact parametric loci of projection. The one based on Grobner basis can compute the minimal variety that contains the parametric loci. The rest one computes a variety that contains the parametric loci via resultant. Examples show that our algorithms are efficient and valuable. Joint work with Meng Zhou.

  6. An Exact Numerical Approach based on Subdivision to Isotopic Arrangement of Simple Curves

    Vikram Sharma (The Institute of Mathematical Sciences, Chennai, India)

    Abstract: We consider This paper presents the first purely numerical (i.e., non-algebraic) subdivision algorithm for the isotopic approximation of a simple arrangement of curves. The arrangement is ?simple? in the sense that any three curves have no common intersection, any two curves intersect transversally, and each curve is non-singular. A curve is given as the zero set of an analytic function $f$ on the euclidean plane, and effective interval forms of $f$, and its partial derivatives wrt $x$ and $y$ are available. Our solution generalizes the isotopic curve approximation algorithms of Plantinga-Vegter (2004) and Lin-Yap (2009). We use certified numerical primitives based on interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, suffer no implementation gaps, integrate topological with geometric computation, and have adaptive as well as local complexity. Joint work with Jyh-Ming Lien, Gert Vegter, and Chee Yap.