1
$\begingroup$

What's the space-complexity of Newton-Raphson? I think it reduces to the space-complexity of storing the inverse hessian matrix.

$\endgroup$
2
$\begingroup$

No, it reduces to the space complexity of solving a linear system using the Hessian matrix.

As with all situations where you need to solve a linear system, computing and storing the inverse explicitly is a bad idea for any problem larger than about 4 by 4. The inverse of a matrix is usually not as well-conditioned as the matrix itself, the inverse of a sparse matrix is typically not sparse... all the usual reasons apply.

$\endgroup$
6
  • $\begingroup$ May you specify the big oh? $\endgroup$
    – Germania
    Aug 20 '21 at 4:38
  • $\begingroup$ No, because it depends on the method that you use to solve the linear system. For example, LU decomposition and Gauss-Siedel are in-place, BiCG-STAB is $O(n)$ (where $n$ is the number of variables you're solving for) if you don't use a preconditioner, and if you do use a preconditioner, then add the size of that. $\endgroup$
    – Pseudonym
    Aug 20 '21 at 4:44
  • $\begingroup$ Having said that, if you're using a solver that uses additional space that is superlinear in the size of the input matrix, then you're probably using the wrong solver. $\endgroup$
    – Pseudonym
    Aug 20 '21 at 5:20
  • $\begingroup$ Does GPU accelerate BiCG-STAB? $\endgroup$
    – Germania
    Aug 20 '21 at 11:48
  • $\begingroup$ @Germania Maybe? I would always look at using something out of the box with a library such as LAPACK or Eigen first, if it was a modest (say, up to 1000 or so variables) problem. If it was much bigger than that, it must be a sparse problem and I'd be testing algebraic multigrid methods (e.g. HYPRE). However, if the problem was that big, I'd also be questioning whether or not Newton-Raphson was really what I needed; Levenberg-Marquardt or expectation-maximisation may be a better solution to the underlying problem. $\endgroup$
    – Pseudonym
    Aug 21 '21 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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