[Date Index] [Thread Index] [Author Index]

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>