Computational complexity of Newton's method

The name of the pictureThe name of the pictureThe name of the pictureClash 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)$?










share|cite|improve this question

























    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)$?










    share|cite|improve this question























      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)$?










      share|cite|improve this question













      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






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Nov 17 at 18:19









      VoB

      1285




      1285




















          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.






          share|cite|improve this answer




















          • 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










          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "363"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













           

          draft saved


          draft discarded


















          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

























          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.






          share|cite|improve this answer




















          • 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














          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.






          share|cite|improve this answer




















          • 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












          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.






          share|cite|improve this answer












          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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          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
















          • 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

















           

          draft saved


          draft discarded















































           


          draft saved


          draft discarded














          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





















































          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






          Popular posts from this blog

          How to check contact read email or not when send email to Individual?

          Displaying single band from multi-band raster using QGIS

          How many registers does an x86_64 CPU actually have?