[I had used my "===" in a mail message, so these are separated with "&&&"s--djr] &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& From: Richard Brankin Subject: Re: Any users of HOMPACK's POLSYS To: rusin@math.niu.edu (Dave Rusin) Date: Wed, 18 Sep 1996 11:26:41 +0100 (BST) Thanks for responding. > Well I'm not a user but I'm interested in solutions of systems of > polynomials. To me that means algebraic geometry, that is, we > solve these systems symbolically or over domains such as the rationals. > Is this system for the computations of real solutions? I would > imagine such solutions would be sought by variants of 1-dimensional > techniques such as Newton's method; is that what it does, or > does it compute complete solution sets using elimination, resultants, > Groebner bases, etc? HOMPACK, uses a numerical homotpy appraoch to compute solutions. It's the only public software available for treating such problems numerically. My reason for posting was on behalf of a colleague working on our symbolic solver package AXIOM. AXIOM has the ability to solve systems of polynomials - my colleague is searching out "applications", hence my posting. If people are using POLSYS from HOMPACK then I assume they have an application in mind or are numerical mathematicians interested in the subject. Hope that satisifes your enquiring mind. You're the only repsondent so far. Given your location, I guess you might know Mike Hosea. I believe he left to work for TI in Dallas. I met him a few times during visits to Southern Methodist in Dallas when he was there. Richard. -- | Dr. R.W.Brankin | NAG Ltd, Jordan Hill Rd | Tel: +44/0 1865 511 245 | | richard@nag.co.uk | OXFORD, UK, OX2 8DR | Fax: +44/0 1865 310 139 | &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& Date: Wed, 18 Sep 96 08:26:55 CDT From: rusin (Dave Rusin) To: richard@hela.nag.co.uk Subject: Re: Any users of HOMPACK's POLSYS Thank you for replying. >My reason for posting was on behalf of a colleague working on our >symbolic solver package AXIOM. AXIOM has the ability to solve systems of >polynomials - my colleague is searching out "applications", hence my >posting. If people are using POLSYS from HOMPACK then I assume they have >an application in mind or are numerical mathematicians interested in the >subject. I take it then that you expect systems of sufficiently many equations that you expect only discrete solution sets, the coordinates of whose members you would compute numerically. Presumably, though, you could also use this for numerical computations of _resolvents_. That is, given a set of polynomial equations whose solution set is a variety of positive dimension, one might hope to eliminate most of the variables and so to find a projection to a hypersurface in fewer dimensions. For example, given f1(x,y,z)=f2(x,y,z)=0, one could eliminate z and get a resolvent f3(x,y)=0 which we could compute by numerically computing the coefficients of each x^n y^m, thus using the packages you propose rather than the usual determinant descriptions of the resolvents. (This is a nice project in those applications in which the initial coefficients are integral, since the coefficients of the resolvent would also be integral and so need not be computed to much accuracy!) So let me interpret your original request to be more broadly a request for systems of polynomial equations for which existing software is useless at performing elimination. Very well then, here's an example of a system of polynomial equations which arose in a recent conversation. This is perhaps typical of what I encounter: a handful of small polynomials which no one in their right mind would try to solve symbolically since as we all know there is a huge intermediate swell when computing the necessary determinants. What follows is a recent sci.math.research post and my response to it. I don't really need a solution (nor, I think, does the original poster) but it strikes me as an interesting challenge problem. Try it, modify it, or ignore it as you wish. I can help you transform this into an explicit set of polynomial equations if it's not clear from my post what that system is supposed to be. If you do indeed have software capable of solving such systems of equations I would be most impressed and would like to add it to my arsenal. >Given your location, I guess you might know Mike Hosea. I believe he >left to work for TI in Dallas. "Yes indeed", and then "yes unfortunately". Quite an interesting fellow. For him and his family I think the move to TI will work out well. dave ====USENET posts attached================================================= From: gerard farmar Newsgroups: sci.math.research Subject: Applied problem. Date: 4 Sep 1996 16:45:12 GMT I have the following formula: g(x) = A^((B+x)^C) + D*exp(-E*(ln(x)-ln(F))^2) + GH^x where A,B,C,D,E,F,G and H are constants, and are positive real numbers, and where x is real. I wish to find a differential equation in terms of the function g(x) only (with terms such as df(x)/dx and d^2f(x)/dx^2) for which the above equation is the SOLUTION! (an interesting reversal) A differential equation for each part separated by the plus sign is easy to find. E.g. for f(x)=GH^x df(x)/dx = (ln(H))*f(x) But I have no idea how to do the same for the full expression. Just for background, this formula is a model for human mortality, and the three components are infant mortality, accidental mortality over the late teens and early twenties, and the mortality of ageing. All the parameters are positive real numbers. I need a differential equation for the purpose of "smoothing" some mortality data. I am not ignorant of mathematics, but know very little of the techniques and theory of differential equations. If you can help I'll be very grateful (and you'll get a mention in my master's thesis, for what it is worth!) ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math.research Subject: Re: Applied problem. Date: 5 Sep 1996 16:45:09 GMT In article <50kbmo$lki@baloo.pipex-sa.net>, gerard farmar wrote: >I have the following formula: > > g(x) = A^((B+x)^C) + D*exp(-E*(ln(x)-ln(F))^2) + GH^x > >where A,B,C,D,E,F,G and H are constants, and are positive real numbers, >and where x is real. > >I wish to find a differential equation in terms of the function g(x) only >(with terms such as df(x)/dx and d^2f(x)/dx^2) for which the above >equation is the SOLUTION! > >A differential equation for each part separated by the plus sign is easy >to find. E.g. >for f(x)=GH^x > >df(x)/dx = (ln(H))*f(x) > >But I have no idea how to do the same for the full expression. It's not immediately clear from this last comment what you want. I would have assumed from the first statement of the problem that you wanted a single differential equation F(x,y,y',y'',...)=0 which would be satisfied by the given g(x) for _every_ choice of A, B, ..., H; in particular, I assumed you wanted a DE not involving these constants. With that in mind, the appropriate equation for the last comment is f(x) * d^2f(x)/dx^2 = (df(x)/dx)^2. You can, in fact, find a polynomial F of _eleven_ variables with the property that F(x, y, dy/dx, ..., dy^9/dx^9) = 0 for all the functions y=g(x) which you described originally; that is, this is a polynomial 9-th order differential equation. I won't write out this polynomial explicitly but will explain how to find it. I have raised the degree of the DE by one more than expected to include the slightly larger family of functions g(x) = K*A^((B+x)^C) + D*exp(-E*(ln(x)-ln(F))^2) + G*H^x rather than simply those with K=1. This is not generosity on my part. Rather, the simplest differential equation satisfied by all functions y=A^((B+x)^C) is found by letting z=ln(y) and then noting z z' z'' - 2 z z''^2 + (z')^2 z'' = 0 You can of course express this as a DE satisfied by y but this would involve ln(y), taking us away from the simpler polynomial DE's. So I prefer to solve this last equation to say z=((z')^2 z'')/(2 z z''^2 - z' z'''), differentiate, and then substitute z'=y'/y and simplify the numerator. The resulting polynomial equation is linear in y'''', so you may express this differential equation in the form y'''' = F1(y, y', y'', y''') where F1 is a rational function of 4 variables (with constant coefficients). As noted earlier, the third summand of g(x) also satisfies a polynomial DE, which may be written y'' = (y')^2/y = F3(y, y'), again a rational function with constant coefficients. The second summand is just a bit different. Setting z=ln(y) again, we find z' + 3 x z'' + x^2 z''' = 0, where again we may set z'=y'/y to get a DE satisfied by y, a polynomial in y, y', y'', and y''', but this time with coefficients involving x. (One can actually eliminate x as well, at the expense of increasing the degree still further; this does not appear to be something you're interested in.) This time we would write y''' = F2(y, y', y'') where F2 is a rational function of the three variables, whose coefficients are polynomials in x. The next observation is to realize that these equations may in turn be differentiated with respect to x to express the higher derivatives of the functions in terms of the first few. For example, if y3 is the third summand of g(x), then we have seen y3'' = (y3')^2/y3 so that by differentiating and substituting back in we get y3''' = (2 y2 y3' y3'' - (y3')^3) / y3^2 = (y3')^3 / (y3)^2; likewise y3'''' and higher derivatives may be expressed as rational functions of y3 and y3' only. On the other hand, it's clear that the definition of g(x) g(x) = y1 + y2 + y3 may now be differentiated repeatedly to express each of the derivatives g^(n)(x) = (y1)^(n) + (y2)^(n) + (y3)^n, for n=0, 1, ..., 9, as a rational function of the nine functions y1 y1' y1'' y1''' y2 y2' y2'' y3 y3' (and x). Clear denominators if you like, and view these as 10 polynomial equations in 10 + 9 variables: the g^(n) and the above 9 functions. By elimination techniques, you can show that the 10 equations can be solved for the last 9 variables iff a polynomial condition on the other 10 variables is satisfied; equivalently, use resultants to eliminate the last 9 variables from these 10 polynomials, leaving a polynomial involving only g(x), ..., g^(9)(x) (and x itself). This is a polynomial differential equation satisfied by g. Since A through H (and K) have been eliminated, this same DE is satisfied by all functions in the family. I hope you didn't really need this equation explicitly; even writing out F1 in its most compact form would take several lines, so the equation g^(9)(x) = d^5 F1 / dx^5 + d^6 F2 / dx^6 + d^7 F3 / dx^7 is likely to be horrendous. Since in general eliminating a variable from two polynomial equations tends to give a resultant whose degree is the _product_ of the degrees on the starting two polynomials, one could only imagine that the final polynomial differential equation F(x, g, g', ..., g^(9) ) = 0 would have a degree well into the thousands. Any popular symbolic algebra package (e.g. Maple) would have the algorithms to substitute, simplify, differentiate, and eliminate; but the time and memory requirements may be beyond anything available. This is all quite formal, and glosses over some difficulties, such as the possibility that for some functions g in the family, some of the denominators in the rational functions above might vanish identically. dave &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& From: Richard Brankin Subject: Re: Any users of HOMPACK's POLSYS To: rusin@math.niu.edu Date: Wed, 18 Sep 1996 15:31:19 +0100 (BST) Thanks for your message. I've forwarded it on to my colleague ianm@nag.co.uk, who might follow it up. My involvemnt in the effort is essentially nil. The AXIOM developers have been working on polynomial solvers. I believe that they have one or two industrial examples and have been asking their more "applied" colleagues for ideas for further examples. For my sins, I'm deemed one of the "applied" guys, ie. a little bit more in touch with "real" problems. Diff Eqs is more my scene, hence my connection with Hosea. However, I did use POLSYS a long time ago for computing discrete solutions for systems of multivariate polynomials. So I thought I'd see if anyone in usenet land was using POLSYS still. I'm aware of a Matalb interface to it by some robotics guys in Switzerland. Otherwise I've not come across practical applications. I'm not sure about the availability or functionality associated with AXIOM's polynomial developments. but if your interested feel free to contact Ian Meikle at the above e-mail address or keep an eye on the AXIOM page on one of our web sites, http://www.nag.co.uk/ or http://www.nag.com/. R. | Dr. R.W.Brankin | NAG Ltd, Jordan Hill Rd | Tel: +44/0 1865 511 245 | | richard@nag.co.uk | OXFORD, UK, OX2 8DR | Fax: +44/0 1865 310 139 |