Hans J. Stetter,
Technical University of Vienna,
Vienna, Austria.

Iterative Solution of Algebraic Problems with Polynomials

In Numerical Analysis, it is standard to use an iterative solution procedure for a nonlinear problem. In Computer Algebra, one prefers exact finite manipulations which preserve the algebraic structure (like in Groebner basis computation); but often, in the end, an iterative numerical procedure can not be avoided (e.g. for zeros of a polynomial system). Furthermore, algebraic problems from Scientific Computing generally contain some ``empiric'' data so that their results are only defined to a limited accuracy. In this situation, an iterative approach may reduce to a few (or just one) step(s).
We will attempt to demonstrate how iterative procedures can be built upon the algebraic structure of a variety of problems for which such an approach has not been considered so far: After some discussion of zero clusters of univariate and systems of multivariate polynomials, we will mainly consider overdetermined problems like greatest common divisors, multivariate factorization, etc.; here the solution concept must be generalized to that of a pseudosolution which is an exact solution of a problem within the data tolerance neighborhood of the specified problem. Our iterative approach to the determination of pseudosolutions of such problems will prove computationally more flexible and efficient than recent ``classical'' approaches like [1] and [2].
  • [1] N.K. Karmarkar, Y.N. Lakshman: On Approximate GCDs of Univariate Polynomials, J. Symb.Comp., 26 (1998) 653-666.
  • [2] M.A. Hitz, E. Kaltofen, Y.N. Lakshman: Efficient Algorithms for Computing the Nearest Polynomial with a Real Root and Related Problems, in: Proc. ISSAC'99 (Ed. S.Dooley) (1999) 205-212.