Newsgroups: sci.math.num-analysis From: softel@actcom.co.il Subject: building of two dimensional polynoms ( a0 + a1x + a2y + a3xy + a4x^2 ...) Date: Tue, 25 Jul 1995 18:11:14 GMT Hi ! Does anybody know how to build two dimensional polynom ( polynom of two variables ) with N predefined roots ( xi , yi ) 1 <= i <= N of minimal degree. Can the degree be less than SQRT(N) ? Any help will be appriciated. Regards Zevin Shaul ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis Subject: Re: building of two dimensional polynoms ( a0 + a1x + a2y + a3xy + a4x^2 ...) Date: 28 Jul 1995 06:05:41 GMT In article , wrote: >Does anybody know how to build two dimensional polynom >( polynom of two variables ) with N predefined roots ( xi , yi ) 1 <= i <= N >of minimal degree. I don't know why this is in num-analysis exactly, since it looks more like algebraic geometry to me. You are asking for an element in the ring S = R[x,y] which vanishes at each point (xi, yi). The set of such elements forms an ideal; you're just looking for the element(s) of the ideal of minimal degree. This ideal can be described as the intersection of the ideals of polynomials vanishing at each single point, that is, the intersection of the ideals (x - xi) S + (y - yi) S. Now if you want to _calculate_ this ideal in an efficient way, you want the theory of Groebner bases. As a practical matter I would fire up a symbolic algebra program which handles these -- my preference is for Macaulay, which was designed precisely for algebraic geometry/ commutative ring theory questions. (You can get it from harvard via ftp. Be forwarned that Macaulay intends to work over a field of positive characteristic < 2^15.) I confess to not really understanding how Groebner bases work, but Macaulay can be induced to calculate intersections of ideals as follows: given ideals I1 = a1 S + a2 S + ... and I2 = b1 S + b2 S + ... (that is, the ai and bi are ideal generators for I1 and I2), the elements in the intersection are the ring elements which can be expressed as both a1 u1 + a2 u2 + ... and b1 v1 + b2 v2 + ... for some ring elements ui and vi. Well, that means that multiplying the ai and the bi by ui or (-vi), respectively, and then summing, gives zero. Thus the ui and (-vi) form a syzygy of the module generators (a1, a2, ..., b1, b2, ...). Macaulay has a 'syz' command, which finds all possible sets of (u1, u2, ..., -v1, -v2, ...); take each, throw away the -vi, multiply the ui by the ai, and sum. The set of these generate (I1 intersect I2). In your case, proceed by induction to find the ideals vanishing at larger and larger numbers of points. A general-position argument shows that a polynomial of degree n is determined by most sets of (n+1)(n+2)/2 points on the curve, so typically N points require a polynomial of degree sqrt(2N), but of course a collection of collinear points, for example, satisfy a curve of the smaller degree 1. dave ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Polynom in two variables creation Date: 31 Jul 1995 17:54:26 GMT In article , wrote: >Having N points in 2D (xi , yi ) , how can we build a polynom in two variables (x,y) >with roots in (xi , yi ) , 1 <= i <= N , with MINIMAL degree. This question was recently posted to another newsgroup. In the hopes of spurring others to respond with more complete information, let me summarize the response I made to the previous post. The posters seek a polynomial (of minimal degree) which vanishes at each of the given points, that is, a polynomial in R[x,y] (I assume the coefficient ring is the set of real numbers) which lies in the ideal (x - xi, y - yi) for each i. Thus the answer is simply to compute the intersection of finitely many ideals in this ring, and then to find in that intersection an element of minimal degree. There are two difficulties of which I am aware, which may have the same solution. One is that, given two finitely generated ideals, one needs a mechanism to create a finite set of generators for their intersection (obviously one then need only iterate this procedure). The second is that, given a set of generators for the ideal, one must find the minimum degree of an element in the ideal. (An upper bound for this minimum is then the smallest of the degrees of the generators, but the example I = (x^2, x^2+x) shows that an ideal may contain polynomials of degree smaller than those of the generators). The solution in both cases appears to be the use of Groebner bases. I have had great success using the Macaulay software package to compute the intersections of ideals in polynomial rings over finite fields; the process is a small extension of the computations of syzygies, a task Macaulay was designed for, and which it accomplishes speedily by using Groebner bases. I believe it's also true that Groebner bases are sets of generators of ideals which have the property (among others) that the second difficulty mentioned above _cannot_ occur. Thus as a practical matter one may simply find a Groebner basis for the ideal and scan to see which generators have the smallest degree. However, I never did follow through and learn the theory which explains just what it is that Groebner bases are supposed to do. Perhaps someone can clarify this situation here. All I know is that they list generators of the ideal in such a way as to allow a sort of division algorithm. It may also be that a practitioner in that area can provide a distilled algorithm which serves for the specific ideal intersections of this problem. >Can the degree of such polynom be less equal SQRN(N) ( square root of N ) ? Again I think I might assist the posters by clarifying the question. Certainly for _some_ sets of N points, the polynomial of smallest degree might have degree much less than Sqrt(N); for example, if the points are (0,0), (1,1), ..., (N,N) then the linear polynomial y-x will do. I assume the question is whether one may _always_ write down a polynomial of a smaller degree. I would expect the answer is negative, since the polynomials of degree d form a (d+1)(d+2)/2-dimensional vector space; attempting to find such a polynomial which vanishes at more than (d+1)(d+2)/2 points would require a linear dependence among the defining equations. I did not prove this to be true but I certainly expect that for "points in general position" the equations defined by distinct points are linearly independent. Thus _in general_, when N points are given, the degree of the polynomial which vanishes at each of them must be a number d so large that (d+1)(d+2)/2 > N; roughly, d must be larger than sqrt(2N). Somewhat more speculatively I might also expect that once this inequality is met one _would_ be able to find a polynomial of degree d. But if the posters expected a generic formula whose degree is "about sqrt(2N)", it seems difficult to imagine what one would look like. In any event, for N specific points, there is no reason to think that the resulting formula would give the polynomial of _lowest_ degree, as noted at the beginning of the previous paragraph. There are a number of pitfalls which arise which I will not dwell upon, such as the non-uniqueness of the answer, and the difficulty of finding a polynomial of _minimal_ degree by induction. But in a pinch I would probably compute d as above, write N linear equations (one for each point) and solve for the coefficients. Good luck. dave ============================================================================== From: wcw@math.psu.edu (William C Waterhouse) Newsgroups: sci.math Subject: Re: Polynom in two variables creation Date: 31 Jul 1995 20:32:36 GMT In article j22@watson.math.niu.edu, rusin@washington.math.niu.edu (Dave Rusin) writes: > In article , wrote: > >Having N points in 2D (xi , yi ) , how can we build a polynom in > >two variables (x,y) > >with roots in (xi , yi ) , 1 <= i <= N , with MINIMAL degree. > ... > >Can the degree of such polynom be less equal SQRN(N) ( square root of N ) ? > Certainly for _some_ sets of N points, the polynomial of smallest degree > might have degree much less than Sqrt(N); for example, if the points are > (0,0), (1,1), ..., (N,N) then the linear polynomial y-x will do. > I assume the question is whether one may _always_ write down a polynomial > of a smaller degree. I would expect the answer is negative, since the > polynomials of degree d form a (d+1)(d+2)/2-dimensional vector space; > attempting to find such a polynomial which vanishes at more than > (d+1)(d+2)/2 points would require a linear dependence among the > defining equations. I did not prove this to be true but I certainly expect > that... _in general_, when N points are > given, the degree of the polynomial which vanishes at each of them must > be a number d so large that (d+1)(d+2)/2 > N; roughly, d must be > larger than sqrt(2N). > > Somewhat more speculatively I might also expect that once this inequality > is met one _would_ be able to find a polynomial of degree d.> The speculation is true. The key is that the condition of vanishing at a specified point is a _homogeneous_ linear equation on the coefficients of the polynomial. So long as there are fewer equations than coefficients in the polynomial, there is sure to be a nontrivial set of coefficients that satisfies them. It's also true that no lower degree will suffice "in general". To see this, consider polynomials of degree f with (f+1)(f+2)/2 less than or equal to N. No nonzero polynomial will vanish at _all_ points, so the linear equations coming from all points span the space of linear functions on coefficients. That space has dimension at most N, so there are N of these linear equations that span the space (and thus together force the coefficients all to be zero). The N corresponding points then do not satify any nontrivial polynomial of degree f. William C. Waterhouse Penn State ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Polynom in two variables creation Date: 31 Jul 1995 21:27:28 GMT In article , wrote: >Having N points in 2D (xi , yi ) , how can we build a polynom in two variables (x,y) >with roots in (xi , yi ) , 1 <= i <= N , with MINIMAL degree. > >Can the degree of such polynom be less equal SQRN(N) ( square root of N ) ? Then, in article <3vj5ci$j22@watson.math.niu.edu>, I wrote: >I assume the question is whether one may _always_ write down a polynomial >of a smaller degree. I would expect the answer is negative, since the >polynomials of degree d form a (d+1)(d+2)/2-dimensional vector space; >attempting to find such a polynomial which vanishes at more than >(d+1)(d+2)/2 points would require a linear dependence among the >defining equations. I did not prove this to be true but I certainly expect >that for "points in general position" the equations defined by distinct >points are linearly independent. Thus _in general_, when N points are >given, the degree of the polynomial which vanishes at each of them must >be a number d so large that (d+1)(d+2)/2 > N; roughly, d must be >larger than sqrt(2N). OK, this was a little hasty of me. I should have remembered that the multivariate polynomials of degree up to d are distinguished by their values on the lattice points with all entries non-negative and summing to d or less. In English, that means there is no non-zero polynomial of degree d or less which vanishes at all the integral points (i,j) with i>=0, j>=0, and i+j <= d. So, yes, you will in general need a polynomial of degree roughly sqrt(2N) if you want it to vanish at all N points. >Somewhat more speculatively I might also expect that once this inequality >is met one _would_ be able to find a polynomial of degree d. But if the >posters expected a generic formula whose degree is "about sqrt(2N)", it >seems difficult to imagine what one would look like. Here I was being a little pessimistic. The following procedure will generate a polynomial of degree roughly sqrt(2N) which vanishes at all N points; in fact, this procedure will generate all such, if the N points are "in general position". I rather like this answer. First calculate d so that N1=(d+1)(d+2)/2 is larger than N. Add N1-N-1 points at random to the list to ensure that the total number of points to be included is N1-1. Now create an N1 x N1 matrix, one row for each point in the set and one additional row for the "variable point" (x,y); for each point, compute the N1 entries in that point's row by evaluating the possible monomials x^n * y^m there (n>=0, m>=0, n+m<=d). The determinant of this matrix is the desired polynomial. (You can replace the N1 x N1 matrix by an N x N matrix using only the original points and selecting just some of the monomials, but it may take some trial and error to make a selection which does not yield the zero polynomial.) This procedure may be likened to the ones used to compute cross products or orthogonal lines. When N1=2, this lets us compute the line through (x1, y1) and (x2, y2) as the zero locus of | 1 x y | det | 1 x1 y1 | = (y1-y2) x + (x2-x1) y + (y2 x1 - x2 y1) | 1 x2 y2 | Similarly this gives us the unique quadratic curve passing through 5 generic points. Certainly this is a polynomial in x and y, and the degree is at most the degree of the highest terms in the first row, which are of degree d (~ sqrt(2N) ) by construction. It vanishes at each of the points (xi, yi) because in those cases the matrix has two identical rows, and hence a determinant of zero (shades of the Vandermonde matrix!) As I indicated earlier there are at least some sets of N1 points for which this polynomial is not identically zero. There is a difficulty here if the polynomial vanishes identically (for example, if two of the points are the same). My inclination would be to stand with the algebraic-geometry version of the problem if a zero polynomial results, since from that perspective one immediately gets the polynomials of lowest degree, and needn't monkey around with subdeterminants of a singular matrix. >There are a number of pitfalls which arise which I will not dwell upon, >such as the non-uniqueness of the answer, and the difficulty of finding >a polynomial of _minimal_ degree by induction. But in a pinch I would probably >compute d as above, write N linear equations (one for each point) >and solve for the coefficients. Good luck. I should perhaps remind the reader as well that the problem as stated can be quite sensitive to the position of the points; the points (i,i) (for i=1,2,...,N) satisfy a polynomial of degree 1; but for most choices of small pertubations ei, the points (i, i + ei) will not lie on any curve of degree less than sqrt(2N). You'd have to compute very carefully to know you had a nonzero polynomial of _minimal_ degree. If as in this case numerical accuracy is problematic, the solution proposed in this post is unwise, as determinant calculations are well known to be both slow and unstable. Better, I suppose, to treat the problem as the solution of N equations in N unknowns, as suggested in the previous post, since more robust methods for solving linear systems exist. dave