Computational complexity of Newton's method
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
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 ($mathcalO(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 $mathcalO(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 $mathcalO(N^2)$
Here I have still a question: the complexity of the computation of the LU decomposition of $J_F$ should be $mathcalO(fracN^33)$. While the computational complexity of the resolution of a triangular system is $mathcalO(fracN^22)$. Since there are two triangular systems, it amounts to $2 mathcalO(fracN^22)$.
Shouldn't it be, totally, $mathcalO(fracN^33)$ instead of $mathcalO(N^2)$?
newton-method complexity numerics quasi-newton
add a comment |
up vote
3
down vote
favorite
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 ($mathcalO(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 $mathcalO(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 $mathcalO(N^2)$
Here I have still a question: the complexity of the computation of the LU decomposition of $J_F$ should be $mathcalO(fracN^33)$. While the computational complexity of the resolution of a triangular system is $mathcalO(fracN^22)$. Since there are two triangular systems, it amounts to $2 mathcalO(fracN^22)$.
Shouldn't it be, totally, $mathcalO(fracN^33)$ instead of $mathcalO(N^2)$?
newton-method complexity numerics quasi-newton
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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 ($mathcalO(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 $mathcalO(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 $mathcalO(N^2)$
Here I have still a question: the complexity of the computation of the LU decomposition of $J_F$ should be $mathcalO(fracN^33)$. While the computational complexity of the resolution of a triangular system is $mathcalO(fracN^22)$. Since there are two triangular systems, it amounts to $2 mathcalO(fracN^22)$.
Shouldn't it be, totally, $mathcalO(fracN^33)$ instead of $mathcalO(N^2)$?
newton-method complexity numerics quasi-newton
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 ($mathcalO(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 $mathcalO(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 $mathcalO(N^2)$
Here I have still a question: the complexity of the computation of the LU decomposition of $J_F$ should be $mathcalO(fracN^33)$. While the computational complexity of the resolution of a triangular system is $mathcalO(fracN^22)$. Since there are two triangular systems, it amounts to $2 mathcalO(fracN^22)$.
Shouldn't it be, totally, $mathcalO(fracN^33)$ instead of $mathcalO(N^2)$?
newton-method complexity numerics quasi-newton
newton-method complexity numerics quasi-newton
asked Nov 17 at 18:19
VoB
1285
1285
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
3
down vote
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 $tgeq 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.
I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
– VoB
Nov 17 at 21:54
sorry, just edited my comment. I mean, why does Newton's method have that complexity?
– VoB
Nov 17 at 21:57
$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.
– Kirill
Nov 17 at 21:58
Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence
– VoB
Nov 17 at 22:02
Or am I completely wrong?
– VoB
Nov 17 at 23:13
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
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 $tgeq 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.
I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
– VoB
Nov 17 at 21:54
sorry, just edited my comment. I mean, why does Newton's method have that complexity?
– VoB
Nov 17 at 21:57
$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.
– Kirill
Nov 17 at 21:58
Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence
– VoB
Nov 17 at 22:02
Or am I completely wrong?
– VoB
Nov 17 at 23:13
add a comment |
up vote
3
down vote
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 $tgeq 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.
I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
– VoB
Nov 17 at 21:54
sorry, just edited my comment. I mean, why does Newton's method have that complexity?
– VoB
Nov 17 at 21:57
$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.
– Kirill
Nov 17 at 21:58
Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence
– VoB
Nov 17 at 22:02
Or am I completely wrong?
– VoB
Nov 17 at 23:13
add a comment |
up vote
3
down vote
up vote
3
down vote
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 $tgeq 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.
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 $tgeq 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.
answered Nov 17 at 18:29
Kirill
10k21741
10k21741
I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
– VoB
Nov 17 at 21:54
sorry, just edited my comment. I mean, why does Newton's method have that complexity?
– VoB
Nov 17 at 21:57
$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.
– Kirill
Nov 17 at 21:58
Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence
– VoB
Nov 17 at 22:02
Or am I completely wrong?
– VoB
Nov 17 at 23:13
add a comment |
I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
– VoB
Nov 17 at 21:54
sorry, just edited my comment. I mean, why does Newton's method have that complexity?
– VoB
Nov 17 at 21:57
$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.
– Kirill
Nov 17 at 21:58
Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence
– VoB
Nov 17 at 22:02
Or am I completely wrong?
– VoB
Nov 17 at 23:13
I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
– VoB
Nov 17 at 21:54
I can't understand why you say that the time complexity is $O(m N^2 + (m/t)N^3)$.
– VoB
Nov 17 at 21:54
sorry, just edited my comment. I mean, why does Newton's method have that complexity?
– VoB
Nov 17 at 21:57
sorry, just edited my comment. I mean, why does Newton's method have that complexity?
– VoB
Nov 17 at 21:57
$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.
– Kirill
Nov 17 at 21:58
$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.
– Kirill
Nov 17 at 21:58
Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence
– VoB
Nov 17 at 22:02
Ok, that's clear. One last question: if I do not want to use the LU decomposition, what is the compexity of Newton's method? I'd say $C cdot O(N^2)$, since I need to solve linear systems until the method achieve convergence
– VoB
Nov 17 at 22:02
Or am I completely wrong?
– VoB
Nov 17 at 23:13
Or am I completely wrong?
– VoB
Nov 17 at 23:13
add a comment |
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fscicomp.stackexchange.com%2fquestions%2f30551%2fcomputational-complexity-of-newtons-method%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown