2
$\begingroup$

I at the moment try to fully understand the Bareiss algorithm for calculating determinants. One question that came to my mind is the following: Why is LU-decomposition much more often used than the Bareiss algorithm? I mean, they both have a complexity of $\mathcal{O}{(n^3)}$, so what's the problem with Bareiss?

$\endgroup$
5
  • 2
    $\begingroup$ Note that Bareiss is for calculating the determinant of an integer matrix by using only integer arithmetic. $\endgroup$ – Alone Programmer Feb 26 '20 at 17:24
  • $\begingroup$ So LU-decomposition is used to be able to also calculate determinants of complex matrices? $\endgroup$ – user34175 Feb 26 '20 at 17:52
  • $\begingroup$ I believe at least scipy.linalg.lu could handle complex matrices as well. $\endgroup$ – Alone Programmer Feb 26 '20 at 18:03
  • $\begingroup$ Between integers and complex numbers there are real numbers, which are by far the most common case in practice. $\endgroup$ – Federico Poloni Feb 27 '20 at 7:56
  • $\begingroup$ I know, but I don't really get the comment of @AloneProgrammer, because bareiss works fine with real numbers. $\endgroup$ – user34175 Feb 27 '20 at 7:58
3
$\begingroup$

Bareiss' algorithm is a better choice if you have to compute exactly determinants of integer matrices, as noted in the comments.

When it comes to real (floating-point) or complex matrices, the main point to understand is that computing determinants is not a common task. In scientific computing, determinants are often a wrong choice: whatever you wish to do, there is usually a faster and more stable choice that does not involve them. Want to know if a matrix is singular or find its rank? Use SVD or RRQR. Want to solve linear systems? Use LU, not Cramer's rule. Want to compute eigenvalues? Use the QR/Francis algorithm, not the characteristic polynomial.

Moreover, overflow and underflow are often practical issues that discourage the use of determinants (exercise: use your favorite programming language to compute $\det(0.1 I_{350\times 350})$). See also this answer of mine on [math.se], which has similar arguments.

So there is little interest in their computation. LU is more used because it does much more than computing the determinant, and typically that "much more" is the reason you wanted to compute a determinant in the first place. Bareiss algorithm, as far as I understand, is a "one-trick pony algorithm": it computes the determinant, and that's it.

So it is not surprising that when you asked a question about determinants on this site the very first comment you got was "But, what do you really need it for?". :)

$\endgroup$

Your Answer

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