Stephen M. Watt
University of Western Ontario, Canada

Title:
An Introduction to Modern Symbolic-Numeric Computation

Abstract:
This tutorial presents a modern framework for hybridized symbolic-numeric computation. This approach enriches both numeric computation with algebraic ideas and the symbolic world with analytic structure.

For decades, the worlds of numerical analysis and computer algebra were largely separate. However, since hardware floating point offered significantly faster computation compared to exact rational arithmetic, there were several preliminary attempts bridging the two disciplines. An early approach was to take the exact algorithms of computer algebra and replace the zero tests with approximate tests in floating point. For example, one would compute the gcd of polynomials with floating point coefficients using the Euclidean algorithm with a fuzzy zero test for termination. The problem with this is that the meaning of the results is is unclear and is determined by the choice of algorithm rather than by the definition of the mathematical problem.

In the 1990s a new approach emerged: to define the symbolic mathematical problem analytically and to look for new methods to solve the problem as reformulated. A key element of this approach was to view problem instances as elements of a topological space and to look for exact solutions to problems nearby the original. For example, the univariate gcd could be reformulated as follows: Given p, q in R[x], polynomial norm |.|, and error tolerance epsilon, find perturbed polynomials p’ and q’ such that |p’-p| and |q’-q| are both less than epsilon and gcd(p’, q’) has maximal degree. Notice that this formulation is purely mathematical and does not presume any particular algorithm and nor does it presume floating point arithmetic.

The present tutorial lays out the foundations of this modern analytic and geometric approach to symbolic-numeric computation and presents some applications. Following the tutorial, participants will be equipped to follow current research in the field, such as that presented in the ISSAC and Symbolic-Numeric Computing conferences.