# Nested root finding algorithm

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?

• You're kinda low on the detail level. "solve $f(x)=0$, with $f$ nonlinear" could easily describe 90% of the world's problems. – Federico Poloni Jun 9 '11 at 14:02
• What is the nature of this decomposition? Do $h(z)$ and $g(y,z)$ have any special properties (linearity, etc.)? – Gilead Jun 9 '11 at 21:14
• 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. – Ian Jun 10 '11 at 7:40

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.