Approximate Algebraic Computation

Robert M. Corless ( University of Western Ontario, rcorless@uwo.ca )
Tateaki Sasaki ( University of Tsukuba, sasaki@math.tsukuba.ac.jp )
Matu-Tarow Noda ( Ehime University, noda@cite.ehime-u.ac.jp )
Kiyoshi Shirayanagi ( NTT Corporation, shirayan@theory.brl.ntt.co.jp )

Aim and Scope
In conventional computer algebra, the usual aim is to perform algebraic computation exactly using rational number arithmetic and the introduction of algebraic and transcendental numbers. But many problems coming from areas like computer vision, robotics, computational biology, physics, etc, are described with inexact numbers ("empirical" numbers) as the input parameters or coefficients. In this context, the usual exact algorithms of computer algebra may not be easily applicable, or may be inefficient. Recent years have witnessed the emergence of new research combining symbolic-numeric computations and leading to new kinds of algorithms, involving algebraic computations with approximate numeric arithmetic, such as floating-point number arithmetic. A typical example of the new research is SNAP (Symbolic-Numeric Algebra for Polynomials, also called Numerical Polynomial Algebra) which is increasingly becoming active. New workshop SNAP (Symbolic-Numeric Computation) will be held in this July. The concept of AAC (Approximate Algebraic Computation) is strongly related to SNAP and SNC. The aim of this session is not only to discuss problems in AAC, but also to make interaction between AAC to create even more powerful theories and real-world applications. Of course, discussions from SNAP and/or SNC are extremely welcome. In the future, it would be wonderful if researches from AAC, SNAP, SNC and others could be combined into a new scientific computing to support a reliable and satisfying network society.

Problems to be discussed in the session: Approximate algebraic computation, stabilization and regularization have great potential for many application problems, because they are quite efficient in both computation time and space while attaining useful accuracy. However, research is still in an early stage and many problems remain open. In this session, we will focus our attention (but not restrictively) on instability problems, static and dynamic error analysis, certification of the output, continuity, flatness, ... and also on algorithmic development, system building and applications.

Typical subjects to be discussed
  • Approximate GCD, approximate factorization.
  • How to solve polynomial equations with inexact coefficients, concentrating on how to solve multivariate polynomial systems.
  • Connections between commutative algebra and numerical computations.
  • Error analysis of algorithms.
  • Certification of the output.
  • Applications of approximate algebraic computation, such as hybrid integration and rational function approximation.
  • Software systems for approximate algebraic computation.
  • Certificated algorithm in Geometry.
  • Applications of Symbolic-Numeric algorithms in scientific computations.
  • Examples of symbolic-numeric applications.
  • Applications of stabilization.
  • Rate of convergence from stabilization.
  • Estimation of precision after stabilization.
  • Algorithm stabilization techniques and automatic stabilization systems.

List of talks
  1. The Nearest Multivariate System with Given Root Structure
    by Scott Pope (North Carolina State University, USA)

  2. On the Location of Zeros of a Complex Interval Polynomial
    by Hiroshi Sekigawa and Kiyoshi Shirayanagi (NTT, Japan)

  3. Polynomial root-finding with matrix eigen-solving
    by Victor Pan (City Univ. of New York, USA)

  4. An Algebraic Method for Separating Close-root Clusters and the Minimum Root Separation
    by Tateaki Sasaki (Univ. of Tsukuba, Japan)
    and Fujio Kako (Nara Women's Univ., Japan)

  5. A fast rank-revealing method for Sylvester matrix
    by Bingyu Li, Zhuojun Liu and Lihong Zhi (AMSS, China)

  6. On the Approximate GCD in Initial Value Problems
    by Stephen Watt (Univ. of Western Ontario, Canada)

  7. An implementation issue on SNAP and significant digits
    by Kosaku Nagasaka (Kobe Univ., Japan)