5
$\begingroup$

I am solving differential equations that require inverting dense square matrices, and I wanted to know what algorithm(s) do numpy and scipy use to calculate matrix inverses?

$\endgroup$
1
  • 1
    $\begingroup$ By way of comparison, there are R libraries which use the Crout method and the Doolittle method of LU decomposition. $\endgroup$ Dec 10, 2023 at 22:13

2 Answers 2

11
$\begingroup$

Documentation to numpy.linalg.inv and scipy.linalg.inv does not mention the algorithm used.

Judging from the source, numpy.linalg.inv calls a C++ wrapper to LAPACK gesv subroutine, which uses LU decomposition (more specifically, LU with partial pivoting, $A = P L U$), and scipy.linalg.inv uses slightly more low-level LAPACK computational routines, performing the same decomposition.

$\endgroup$
2
  • 3
    $\begingroup$ Note that there are various different ways to obtain an inverse from the PLU decomposition of a matrix, so even the step following PLU is not completely trivial. Higham's "Accuracy and stability of numerical algorithms" has an entire chapter on it. $\endgroup$ Dec 9, 2023 at 20:14
  • 1
    $\begingroup$ This is also the default algorithm choice for numpy and scipy's solve function, so that can be used instead for solving linear systems. $\endgroup$
    – whpowell96
    Dec 9, 2023 at 23:04
2
$\begingroup$

First of all, they don't take matrix inverses. They perform linear solves. Typically this is done via LU factorization.

$\endgroup$
4
  • 5
    $\begingroup$ Sure they do compute inverses, if you call inv. $\endgroup$ Dec 9, 2023 at 20:12
  • 1
    $\begingroup$ Sure, but don't do that. $\endgroup$ Dec 10, 2023 at 2:11
  • $\begingroup$ I was sure that the documentation page for numpy.linalg.inv had a comment recommending to use numpy.linalg.solve instead whenever possible, but apparently I remember wrong. $\endgroup$
    – Stef
    Dec 10, 2023 at 18:27
  • $\begingroup$ They use the exact same algorithm under the hood but obviously less work is done in using solve compared to inv because you just do fewer operations. $\endgroup$
    – whpowell96
    Dec 11, 2023 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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