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.
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).
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.
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.
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.
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.