Re: Re: Re: Homotopic algorithm to solve a system of equations

*To*: mathgroup at smc.vnet.net*Subject*: [mg66942] Re: [mg66914] Re: [mg66875] Re: Homotopic algorithm to solve a system of equations*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Sun, 4 Jun 2006 02:01:19 -0400 (EDT)*References*: <e5mhml$kjl$1@smc.vnet.net> <200606020809.EAA18052@smc.vnet.net> <200606030726.DAA17296@smc.vnet.net> <2A4A2745-0F59-4312-B649-95C84A1AF645@mimuw.edu.pl>*Sender*: owner-wri-mathgroup at wolfram.com

I got a bit confused writing the stuff below, as often happens when I try to write faster than I can think. Although the confusion does not relate to the main point, I thought it would better to correct it so are the Errata. What got me confused it the fact is that there is more than one way to view a differential equation as an algebraic equation. When we think of as an equation in the space of jets, each partial derivative is viewed as an independent variable. But there is also another approach : a partial derivative like D[f[x,y],{x,3}] is replaced by x^3, a mixed derivative D[f[x,y],{x,1},{y,1}] by x y etc. Both approaches turn a system of partial differential equations into a system of polynomial equations but I don't think there is any relationship between them. In the case of the Gromov's h-principle it is the first approach that is relevant, and in the case of the analogy between Janet and Groebner bases the second. Andrzej Kozlowski Tokyo, Japan On 3 Jun 2006, at 21:38, Andrzej Kozlowski wrote: > Homotopy (which is actually what I do during day hours ;-)) has > nothing in particular to do with differential equations, or rather, > differential equations are just one of many different kinds of > mathematical objects to which the methods of homotopy theory can be > applied. To speak of "homotopy" you simply need two topological > spaces (they can be the same) and the notion of continuous maps > between them. Two such maps are said to be homotopic if one can be > "continuously deformed" into the other. For example, an example > homotopy between two maps f and g between a topological space X and > an affine (topological) space Y would be just the map F(x,t)= (1-t) > g(x)+ t f(x). F is a map from the Cartesian product of X and the > unit interval to Y, but you can think of it as a continuous family > of maps F( ,t), such that F( ,0)= g() and F( ,1) = f( ). F is a > very simple example of a homotopy. The basic idea of homotopy > methods in problems like the one discussed by Etienne is that to > solve a certain problem about the map f you try to find a homotopy > between it and another map g, for which the problem is much simpler > to solve. If the problem is "invariant under homotopy" (which is > the kind of problem that algebraic topologists like myself usually > study) than solving if for the simpler map will automatically > produce a solution for the more complicated map. However, the > problem of solving a polynomial equation f==0 is obviously not > homotopy invariant: the roots of the equation g==0 will obviously > not be the same as the roots of a "homotopic" equation f==0. So > what one needs to do is to take an explicit homotopy F and study > its zero set i.e. the set of points (x,t) such that F[x,t)==0. > More precisely, we want to find a path x(t) such that F(x(t),t)==0 > and x(0) is the well known root of g==0. In that case x(1) will > be a root of f=0. If we can find such a path path x(t) than the > problem of finding a root of f will be solved. > It is in the process of finding the path x(t) that ordinary > differential equations come in. If the homotopy is "regular" than > indeed the problem can be reduced to that of solving a system of > ordinary differential equations. But actually that is not > necessary: one can simply work with the original homotopy F(x(t),t) > ==0 and try to solve it using an interative method: for example the > Newton-Raphson. So differential equations are really quite > incidental here. Homotopy techniques can be enormously powerful, > particularly in the global setting, when we are considering > equations on manifolds. Actually, systems of partial differential > equations can be viewed simply as a special case of systems > algebraic equations: but they have to be viewed as polynomial > equations in the so called space (or bundle) of jets. In > particular, all the apparatus of polynomial equation solving, > including Groebner basis, etc. can be applied to system of PDEs > ( One can even argue that the famous Buchberger algorithm for > computing Groebner basis was first discovered in the PDE setting by > Janet in 1920, that is 45 years before Buchberger). > Now, once we come to the bundle of jets: homotopy methods shows > there true power. Probably the most spectacular achievement is the > work of Gromov on the so called h-principle (h for homotopy): among > the vast number of things that can be deduced form it is Smale's > famous proof that the 2-dimensional sphere in three space can be > turned inside out by a regular homotopy (it will have to intersect > itself in the process of doing so). > > Anyway, this is taking me too far afield, but the best answer to > your question is, I think, : not necessarily. > > Andrzej Kozlowski > > > On 3 Jun 2006, at 16:26, Chris Chiasson wrote: > >> Are you talking about using differential equations to go from the >> solution of a system of equations to which one _does_ know the >> answer >> to the solution of a system of equations to which one _does not_ >> (yet) >> know the answer? >> >> On 6/2/06, aTn <ayottes at dms.umontreal.ca> wrote: >>> >>> Ok, some of you wrote back to me wondering if such algorithms >>> exist and >>> how they work. Here is a quick explanation. >>> >>> The methods I'm referring to are know as "probability one globally >>> convergent homotopy algorithms" (see L. Waston's great introductory >>> paper) that were developped to help solve a system of equations >>> (polynomial with real coefficients). >>> >>> The basic result used in these algorithms is a parametrized >>> version of >>> Sards theorem: >>> >>> Let U be an open set in R^m and let p: U x R^n x [0,1[ ---> R^n be a >>> C^2 map. If p is transversal to zero (i.e. 0 is a regular value >>> of p), >>> then the set of points 'v' in the open set U such that p_v : R^n x >>> [0,1[ --> R^n : (x,t) ---> p(v,x,t) is transversal to 0, is of >>> measure >>> one. >>> >>> The way to apply this result to equation solving is the following. >>> Consider a finite set of n polynomials with n indeterminates (and >>> real >>> coefficients). To it corresponds a (smooth) function F:R^n---> >>> R^n. The >>> idea is to find an open set U in R^m, a C^2 map p: U x R^n x [0,1 >>> [ --> >>> R^n which is transversal to zero, such that a solution of p_v(x, >>> 0) = 0 >>> is known explicitly for all v in U, p_v(x,1)= F(x) for all v in >>> U and >>> all x in R^n, and finally for which p_v^(-1)(0) is bounded for >>> all v in >>> U. Then (by the previous theorem) you can find a path in p_a^(-1)(0) >>> for some 'v' for which the differential of p_v is of full rank >>> linking >>> a zero of p_v(. , 0) to a zero of p_v(. , 1) = F. We want the >>> differential to be of full rank so we can use algorithms such as the >>> Newton method to solve successive problems along the chosen path. >>> >>> I'm looking for a package implementing known probability one >>> globally >>> convergent homotopy algorithms. I hope this message makes my >>> question >>> clearer. >>> >>> Regards, >>> >>> Etienne (aTn) >>> >>> P.S.: I typed fast, so feel free to point out mystakes I might have >>> made :) >>> >>> >> >> >> -- >> http://chris.chiasson.name/ >> >

**References**:**Re: Homotopic algorithm to solve a system of equations***From:*"aTn" <ayottes@dms.umontreal.ca>

**Re: Re: Homotopic algorithm to solve a system of equations***From:*"Chris Chiasson" <chris@chiasson.name>