2
$\begingroup$

I have a system of nonlinear algebraic equations which I'm wanting to solve numerically (for example with a Newton iteration based technique). I can formulate this either as the single system of size N:

f( x ) = 0

or as the nested systems of size P, Q:

g( y, z) = 0,

h( z ) = 0.

It may be that P+Q < N (ie, the nested problem reduces the size of my system to solve).

Is it known which approach is more computationally efficient?

$\endgroup$
  • 3
    $\begingroup$ You're kinda low on the detail level. "solve $f(x)=0$, with $f$ nonlinear" could easily describe 90% of the world's problems. $\endgroup$ – Federico Poloni Jun 9 '11 at 14:02
  • $\begingroup$ What is the nature of this decomposition? Do $h(z)$ and $g(y,z)$ have any special properties (linearity, etc.)? $\endgroup$ – Gilead Jun 9 '11 at 21:14
  • $\begingroup$ I think the key word that I missed was algebraic, and the example of Newton iteration. The particular applications are generalizations of the implicit algorithm described in section 9.2 of <a href="relativity.livingreviews.org/Articles/lrr-2003-7/">this review</a>. In particular, they involve a multi-dimensional implicit root-find for ${\bf x}$. There's two cases that I'm interested in; one will convert the 2d root-find for ${\bf x}$ into a pair of nested 1d root-finds. The other converts a 4d root find into a 2d nested within a 1d. I can't see any particular special properties. $\endgroup$ – Ian Jun 10 '11 at 7:40
2
$\begingroup$

There's a third option I'd consider: alternated iterations. Namely, call $N[p]$ the Newton iteration for a function $p(x)$, and solve $$ z_{k+1}=N[h](z_k) $$ $$ y_{k+1}=N[g(\cdot,z_{k+1})](y_k) $$ ` (I hope the notation is understandable).

Typically this kind of ideas get you slightly better results than vanilla Newton, since the updated $z_{k+1}$ is used "as soon as it's available". I do not have specific information or references to this approach for this exact problem though. Give it a try maybe and see if it works.

$\endgroup$
  • $\begingroup$ Thanks; I'm mainly using black boxes for the root finding, so this may take a while to check. $\endgroup$ – Ian Jun 10 '11 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.