[Date Index]
[Thread Index]
[Author Index]
Re: Homotopic algorithm to solve a system of equations
*To*: mathgroup at smc.vnet.net
*Subject*: [mg66875] Re: Homotopic algorithm to solve a system of equations
*From*: "aTn" <ayottes at dms.umontreal.ca>
*Date*: Fri, 2 Jun 2006 04:09:01 -0400 (EDT)
*References*: <e5mhml$kjl$1@smc.vnet.net>
*Sender*: owner-wri-mathgroup at wolfram.com
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 :)
Prev by Date:
**Re: A conditional random number generation problem (please help me!)**
Next by Date:
**Re: Installing AddOn**
Previous by thread:
**Homotopic algorithm to solve a system of equations**
Next by thread:
**Re: Re: Homotopic algorithm to solve a system of equations**
| |