Re: Re: Re: Homotopic algorithm to solve a system of equations
- To: mathgroup at smc.vnet.net
- Subject: [mg66940] 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:15 -0400 (EDT)
- References: <e5mhml$kjl$1@smc.vnet.net> <200606020809.EAA18052@smc.vnet.net> <200606030726.DAA17296@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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>
- Re: Homotopic algorithm to solve a system of equations