3
$\begingroup$

the classical Newton's method for non-linear systems of equations is $x_{k+1} =x_k-J_F(x_n)^{-1} F(x_n)$. In pratice, rather than compute the inverse of the Jacobian matrix, one solves the systems $J_F(x_k) (x_{k+1}-x_k)=-F(x_k)$, for the unknown $x_{k+1}-x_k$.

In my notes (about ODE) I found:

Newton's method requires the computation of the Jacobian matrix and its "inversion" at every step $k$. This could be too expensive ($\mathcal{O}(N^3)$), where $N$ is the dimension of the matrix.

My doubt is how to get that computational complexity. Is it talking about the way to invert a matrix using LU decomposition, which I know to be $\mathcal{O}(N^3)$ ?

Then it states:

A standard way to reduce computational complexity is to use always the same Jacobian matrix, compute its LU decomposition and use it to solve the linear systems. This is $\mathcal{O}(N^2)$

Here I have still a question: the complexity of the computation of the LU decomposition of $J_F$ should be $\mathcal{O}(\frac{N^3}{3})$. While the computational complexity of the resolution of a triangular system is $\mathcal{O}(\frac{N^2}{2})$. Since there are two triangular systems, it amounts to $2 \mathcal{O}(\frac{N^2}{2})$.

Shouldn't it be, totally, $\mathcal{O}(\frac{N^3}{3})$ instead of $\mathcal{O}(N^2)$?

$\endgroup$

1 Answer 1

4
$\begingroup$

If you take $m$ steps, and update the Jacobian every $t$ steps, the time complexity will be $O(m N^2 + (m/t)N^3)$. So the time taken per step is $O(N^2+N^3/t)$. You're reducing the amount of work you do by a factor of $1/t$, and it's $O(N^2)$ when $t\geq N$. But $t$ is determined adaptively by the behaviour of the loss function, so the point is just that you're saving some unknown, significant amount of time.

In the quote, "this" probably refers to the immediately preceding sentence, the complexity of solving an already-factored linear system, not to the time taken for the whole step like in the paragraph before it.

$\endgroup$
4
  • $\begingroup$ I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$. $\endgroup$
    – VoB
    Nov 17, 2018 at 21:54
  • $\begingroup$ sorry, just edited my comment. I mean, why does Newton's method have that complexity? $\endgroup$
    – VoB
    Nov 17, 2018 at 21:57
  • $\begingroup$ $N^2$ is the time to solve a linear system, $N^3$ is the time to compute an LU factorization. So counting only the time spent doing linear algebra (not function or Jacobian evaluations), that's the time complexity of Newton's method. $\endgroup$
    – Kirill
    Nov 17, 2018 at 21:58
  • $\begingroup$ More precisely $O(N^2)$ is the time to solve $LU x = b$. $\endgroup$
    – AnilJ
    Apr 19, 2021 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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