### Subdivision and Algebraic Geometry for Certified Correct Computations

- Series
- Algebra Seminar
- Time
- Monday, February 11, 2013 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Michael Burr – Clemson University

Many real-world problems require an approximation to an algebraic
variety (e.g., determination of the roots of a polynomial). To solve
such problems, the standard techniques are either symbolic or numeric.
Symbolic techniques are globally correct, but they are often time
consuming to compute. Numerical techniques are typically fast, but
include more limited correctness statements. Recently, attention has
shifted to hybrid techniques that combine symbolic and numerical
techniques.
In this talk, I will discuss hybrid subdivision algorithms for
approximating a variety. These methods recursively subdivide an initial
region into smaller and simpler domains which are easier to
characterize. These algorithms are typically recursive, making them
both easy to implement (in practice) and adaptive (performing more work
near difficult features). There are two challenges: to develop
algorithms with global correctness guarantees and to determine the
efficiency of such algorithms. I will discuss solutions to these
challenges by presenting two hybrid subdivision algorithms.
The first algorithm computes a piecewise-linear approximation to a real
planar curve. This is one of the first numerical algorithms whose
output is guaranteed to be topologically correct, even in the presence
of singularities. The primitives in this algorithm are numerical (i.e.,
they evaluate a polynomial and its derivatives), but its correctness is
justified with algebraic geometry and symbolic algebra.
The second algorithm isolates the real roots of a univariate polynomial.
I will analyze the number of subdivisions performed by this algorithm
using a new technique called continuous amortization. I will show that
the number of subdivisions performed by this algorithm is nearly optimal
and is comparable with standard symbolic techniques for solving this
problem (e.g., Descartes' rule of signs or Sturm sequences).