3
$\begingroup$

I'm in search for a library for solving large systems of non-linear equations, similar to MINPACK, but unlike MINPACK, can accept a Jacobian in band-storage.

My Jacobian is sometimes not invertible, so a method like the Levenberg-Marquardt algorithm in MINPACK, which can deal with singular Jacobians is important. Also, it would be nice if the package was in Fortran, but C/C++ is ok too.

I'm solving a system of ~10,000 nonlinear equations, with a non-zero diagonal about ~200 wide, so using band-storage is necessary. Thanks for any suggestions.

$\endgroup$
0
2
$\begingroup$

A few options are

Alternatively you could try and use a nonlinear minimizer like the Ceres solver from Google. This library supports sparse Jacobian matrices, but their Levenberg-Marquardt implementation is primarily aimed at nonlinear least squares problems. An answer over at Stack Overflow explains how you might still be able to use it, but it involves the risk of converging to a minimum instead of the root.

Apart from KINSOL, none of these codes appear to be particularly adapted to banded matrices. In general if you store your Jacobian as a sparse matrix (e.g. CSR format) a back-of-the-envelope calculation says you should be able to reduce your memory consumption from ~100 MB to ~2 MB (assuming you are using 64-bit reals). Compared to a general sparse array, the LAPACK banded storage does not require the integer pointer arrays, so you would have some additional savings (~1 MB). In both cases I think you could expect to see a significant performance increase.

$\endgroup$
2
  • $\begingroup$ Thanks! I'm pretty optimistic about KINSOL. I'll try that. I did try scipy.optimize.root and I didn't work out - I couldn't work out to tell scipy the jacobian was sparse. $\endgroup$ Jan 21 at 17:12
  • $\begingroup$ Let us know if it works out. One potential problem I see is the banded routines from LAPACK apply a LU factorization. To deal with a singular Jacobian it might be that a QR factorization is necessary (like used in MINPACK). I have located some routines for a banded matrix QR factorization here: people.sc.fsu.edu/~jburkardt/f77_src/band_qr/band_qr.html, but in this scenario you might need to modify MINPACK yourself. $\endgroup$
    – IPribec
    Jan 22 at 18:10

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.