MathGroup Archive 2006

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

Search the Archive

Re: Homotopic algorithm to solve a system of equations

  • To: mathgroup at
  • Subject: [mg66930] Re: Homotopic algorithm to solve a system of equations
  • From: "aTn" <ayottes at>
  • Date: Sun, 4 Jun 2006 01:10:25 -0400 (EDT)
  • References: <e5mhml$kjl$><> <e5resj$h3k$>
  • Sender: owner-wri-mathgroup at

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.


  • 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?