Out of memory when solving large system of non-linear equations (fsolve, fminunc, ...)

Hi all,

the system of non-linear equation that I want to solve is large, Diagnostics=on tells me I have more then 50000 variables. And ideally, I still want to scale up to number of variables.

When I can fsolve I get an Out of Memory error:

Error using zeros
Out of memory. Type HELP MEMORY for your options.

Error in trustnleqn (line 114)
    JACfindiff = zeros(sizes.nFun,sizes.nVar); % pre-allocate derivative array

Error in fsolve (line 388)
        trustnleqn(funfcn,x,verbosity,gradflag,options,defaultopt,f,JAC,...

I'm looking for ideas how to solve this. This is what I have tried:

• The documentation metions that some algorithms are largescale. My understanding is that these algorithms will use as little memory as possible by exploiting scarceness of matrices etc. (is this understanding correct?). My reading of the documentation is also that all algorithms in fsolve are largescale, hence I believe this option is already exhausted – or do I need to enable this somehow?
• My understanding of the error message is that the trustnleqn algorithm builds a Jacobian matrix. This is what exhausts my memory. So I tried looking for algorithms that do not use Jacobian matrices. I tried fminunc and patternsearch but it had a similar memory footprint.

In a nutshell, I want to solve a large system of equations with an algorithm that has very little memory needs.

Cheers, kai

Answer 1

[Matt J]

I have more then 50000 variables. And ideally, I still want to scale up to number of variables.

This means your Jacobian matrix will be at least 50000x50000 which will consume at least 18 GB. It is understandable that that might strain the RAM resources of some systems, particularly those from 2021, when this question was posted.

To deal with this, you should look to some of fsolve's options to avoid computing the Jacobian explicitly, such as JacobianMultiplyFcn or JacobPattern, see

https://www.mathworks.com/help/optim/ug/fsolve.html#buta__s-options

Or you could use SpecifyObjectiveGradient to supply your own Jacobian computation, where you might be able to represent the Jacobian in sparse form, depending on the form of your equations.

Answer 2

[Ayush Modi]

Hi Kai,

While it is difficult to pinpoint exact solution for "Out of memory" error, you can try the following workarounds:

Additional options of fsolve function:

You can save memory (and possibly save time) by setting the Algorithm option to 'trust-region' and the SubproblemAlgorithm option to 'cg'.

You can enable this options by using options in "fsolve" function. Refer to the following MathWorks documentation for more information:

https://www.mathworks.com/help/optim/ug/fsolve.html#buta__s_sep_shared-jacobian:~:text=Optimization%20Options.-,All%20Algorithms,Algorithm,-Choose%20between%20%27trust

Sparse matrix:

If a matrix contains many zeros, converting the matrix to sparse storage saves memory. You can read more about it in the following MathWorks documentation:

https://www.mathworks.com/help/matlab/ref/sparse.html#mw_21ca0260-4c30-46a4-925b-4f237d57c458

https://www.mathworks.com/help/matlab/sparse-matrices.html

Other algorithms:

While "fsolve" function is widely used, sometimes other solvers might be more efficient for specific types of problems. Refer to the below MathWorks documentation for a few of them:

lsqcurvefit - https://www.mathworks.com/help/optim/ug/lsqcurvefit.html

lsqnonlin- https://www.mathworks.com/help/optim/ug/lsqnonlin.html