A numerical approach toward approximate algebraic computation
Wednesday, October 18, 2006 - 11:15am - 12:15pm
From the perspective of numerical analysts, algebraic problems are frequently ill-posed as characterized by Hardamard, where a tiny perturbation in the problem data or roundoff can completely alter the solution structure. Such problems include matrix rank/kernel, singular root-finding, greatest common divisors, irreducible factorization, dual basis of a polynomial ideal, Jordan Canonical Form, etc, and arise in applications as simple as solving linear systems. Due to unbounded sensitivity, ill-posed problems are not suitable for straightforward computation using floating point arithmetic. In this talk we shall discuss the notion of the approximate solution to ill-posed algebraic problems and present a strategy for its numerical computation. This approach consists of a three-strike reformulation principle that removes the ill-posedness, and a two-staged computing strategy for finding approximate solutions. Numerical algorithms have been developed and implemented for several basic algebraic problems with remarkable robustness and accuracy.