From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: Roots of multi-variate polynomials
Date: 9 Sep 1999 16:02:58 GMT
Newsgroups: sci.math.num-analysis
Keywords: Use Groebner bases on polynomials with inexact coefficients?
In article <37D76B49.1CE794B@geo.uu.nl>,
Dirk Kraaijpoel wrote:
>Meanwhile from another source I got mentioned
>"Groebner bases". I found some texts on it
>which are very mathematical (algebraic geometry).
>I do not mind diving into it though if I'm sure
>that this is what I'm looking for. In the
>texts all coefficient used are integers, which
>is of course unrealistic for practical (physical)
>applications. I don't know if it's essential.
Well, it's essential that you know the coefficients exactly.
Imagine trying to solve the system of equations
y - x^2 = 0
y + x^2 = a
where a is only known to be "zero to many decimal places".
So integer coefficients are prefered, but not essential.
In principle one could conduct Groebner-basis calculations with
polynomials whose coefficients are arbitrary real numbers, but one
would need to be able to decide from time to time whether various
algebraic combinations of those numbers are actually equal to
zero. Fortunately the solutions to the polynomial equations _usually_
depend continuously on the coefficients, so you can approximate real
coefficient with rational ones, then scale to integers. (You will need
a package which can handle large integers!) The solutions to the
original problem will be close by these solutions, in general.
Global characteristics of the solution set _can_ change with the
coefficients, as the example above indicates, but the sets of
coefficients at the boundaries themselves form an algebraic variety
(in the example above, there is a change at the variety a=0) so if
it's essential to get an accurate description of the global nature of
the solution set, you could do a Groebner-basis (or other elimination)
reduction of the polynomials, carrying along symbolic coefficients,
and then substitute in your real coefficients after the fact -- this
would give you an indication of how closely you need to approximate
your coefficients with rational numbers without affecting the number
of solutions, say.
But I have to say this is a lot of work, and the only real payoff is
that you can be assured you know you have computed _all_ the solutions,
even ones which are far from where you first thought to look. If you
have any idea at all where the solutions are (at least the solutions
which are relevant for your problem) it ought to be much easier to use
Newton's method, say, to converge to the points.
>I want to find isolated roots in systems
>of two bivariate (if that's a word) polynomials
>with real coefficients. So do you think this is
>also something that does what I'm looking for?
Of what degrees are the polynomials? If one has degree m and the other
degree n, a typical elimination calculation would return a single
univariate polynomial of degree m*n, each root of which is one coordinate
of one of the intersection points. If, say, m=n=20, you have to ask
whether the 400 expected points of intersection are really all relevant.
If you know that it's only the intersection points near the origin which
are of interest, for example, why not just retain the first few terms
of the Taylor series(es), use elimination on those to find out where
those altered curves meet, then use Newton's method starting with those
to approach points of intersection of the original curves? This is a
little fishy, theoretically, but as a practical matter seems like
a lot less work and ought to suffice "in general".
dave
PS - there are many packages which carry out GB computations; you
shouldn't have to re-invent the wheel. Maple and Mathematica can do them,
but not very efficiently. Magma, Macaulay, CoCoa, etc. are packages which
have efficient GB procedures included.
==============================================================================
From: Stephen Vavasis
Subject: Re: Roots of multi-variate polynomials
Date: Thu, 09 Sep 1999 15:15:27 -0400
Newsgroups: sci.math.num-analysis
An alternative to Groebner bases for finding all roots of multivariate
polynomials is Macaulay resultants. With Macaulay resultants you can
transform the system of polynomials very easily to a generalized
eigenvalue problem. There is high-quality free software, notably the
routine ZGEGV from Lapack, for solving generalized eigenvalue problems.
So, assuming you consider generalized eigenvalues to be a "solved
problem", Macaulay resultants are much simpler to implement than
Groebner bases.
There are some issues regarding the stability of this method on which
Bjorn Jonsson and I are currently conducting research. (We are pretty
sure that the method is stable if you implement it the right way. We
haven't written our paper yet.) There are also numerical stability
issues concerning Groebner bases that have not been fully solved as far
as I know.
You can learn about Macaulay resultants from a survey paper by Emiris
and Mourrain written at INRIA
ftp://ftp-sop.inria.fr/saga/mourrain/9711-EM-resultant.ps.gz
Unfortunately, I don't know of a treatment of them in a textbook.
-- Steve Vavasis
Dave Rusin wrote:
[previous article quoted -- djr]