# What is the space-complexity of the Newton-Raphson algorithm?

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

## 1 Answer

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.

• May you specify the big oh? Aug 20 '21 at 4:38
• 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. Aug 20 '21 at 4:44
• 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. Aug 20 '21 at 5:20
• Does GPU accelerate BiCG-STAB? Aug 20 '21 at 11:48
• @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. Aug 21 '21 at 4:31