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].
|