GuideNonlinear systemsadvanced

Cost and efficiency in dimension n

Accounting of per-iteration cost in systems: $n$ evaluations per $F$ , $n^2$ per Jacobian, cost of the linear solves, efficiency indices and the multidimensional optimality conjecture.

What each iteration costs

In dimension $n$ , each evaluation of the vector function $F$ is $n$ scalar evaluations, and each Jacobian $F'$ is $n^2$ . Moreover, each directly solved linear system costs $\frac{n^3}{3}+n^2-\frac{n}{3}$ products/quotients, and solving $q$ systems with the same coefficient matrix (factorizing only once) costs $\frac{n^3}{3}+qn^2-\frac{n}{3}$ . This cost makes frozen-Jacobian methods attractive.

ExampleEfficiency of Newton's method

Compute the efficiency indices of Newton for systems in dimension $n$ .

Per iteration there is one evaluation of $F$ ( $n$ scalars) and one of the Jacobian ( $n^2$ ): in total $d=n^2+n$ functional evaluations.
A single linear system is solved per iteration, so $op=\frac{n^3}{3}+n^2-\frac{n}{3}$ products/quotients.
With order $p=2$ , the indices become:
$I_N=2^{1/(n^2+n)},\qquad IC_N=2^{1/\left(\frac{n^3}{3}+2n^2+\frac{2n}{3}\right)}$

Both indices tend to 1 as $n$ grows: in high dimensions all efficiencies compress and the cost of the linear solves rules.

Multidimensional optimality

The scalar Kung-Traub conjecture ( $p\le 2^{d-1}$ ) does not hold in several variables. The multidimensional conjecture bounds the order by

p\le 2^{k_1+k_2-1},\qquad k_1\le k_2

k_1

= Jacobian evaluations and

k_2

= evaluations of

F

per iteration (

d=k_1+k_2