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]