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

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

• To: mathgroup at smc.vnet.net
• Subject: [mg66914] Re: [mg66875] Re: Homotopic algorithm to solve a system of equations
• From: "Chris Chiasson" <chris at chiasson.name>
• Date: Sat, 3 Jun 2006 03:26:22 -0400 (EDT)
• References: <e5mhml$kjl$1@smc.vnet.net> <200606020809.EAA18052@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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/

• Follow-Ups:
  • Re: Re: Re: Homotopic algorithm to solve a system of equations
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>

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