       Re: Homotopic algorithm to solve a system of equations

• To: mathgroup at smc.vnet.net
• Subject: [mg66930] Re: Homotopic algorithm to solve a system of equations
• From: "aTn" <ayottes at dms.umontreal.ca>
• Date: Sun, 4 Jun 2006 01:10:25 -0400 (EDT)
• References: <e5mhml\$kjl\$1@smc.vnet.net><200606020809.EAA18052@smc.vnet.net> <e5resj\$h3k\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```I think you got the idea right, but I would NOT use differential
equations (read the post above yours carefully; you can also check out
the tutorial by Watson, its available on the net for you to download).
The idea is to 'deform' (precisely, to do a homotopy) of a 'simple' set
of equations to which you know the solution into the system of
equations you want to solve. The deformation creates a 'path' of
systems of equations starting from the simple problem g: R^n-->R^n (to
which you know a solution x0) and ending at the hard problem
f:R^n--->R^n. Say the system of equations at time ' t ' is noted f_t (
t goes from 0 to 1). We have f_0 = g and f_1 = f.

The procedure you use is iterative. The idea is to start at time 0 and
increment ' t ' by a small value epsilon. More precisely, say at time '
t ' you know the solution to f_t (x) = 0 (lets note that solution as
xt). You use xt as an initial point for the Newton method to solve the
problem f_(t + epsilon) (x) = 0. You go from t = 0 to t = 1 and find a
solution to you problem f(x) = 0.

Some problems may arise. To work, the Newton algorithm requires that
the differential of f_t be non-singular for all t (in other words, the
determinant of the jacobian of f_t is non-zero for all t). Sards
theorem (see my post above) insures us that there exists a path going
from f_0 to f_1  for which f_t has a non-singular differential at all
times t.

Hope this clarifies the idea.

Etienne

```

• Prev by Date: Re: Simplifying algebraic expressions
• Next by Date: Re: Colored Tick Labels?
• Previous by thread: Re: Homotopic algorithm to solve a system of equations
• Next by thread: Re: Closed Form solution too much to hope for?