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)
>
> 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
>> 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
>>
>>
>
>
> --
> http://chris.chiasson.name/
>

```

• Prev by Date: Re: Mathematica Font problems
• Next by Date: Re: New Analytical Functions - Mathematica Verified
• Previous by thread: Re: Re: Homotopic algorithm to solve a system of equations
• Next by thread: Re: Re: Re: Homotopic algorithm to solve a system of equations