Feature #2772


Matrix: Calculating determinant using Bareiss algorithm [patch]

Added by marcandre (Marc-Andre Lafortune) over 12 years ago. Updated over 11 years ago.

Target version:


Yu Ichino suggested to use a different algorithm to calculate the determinant of a matrix in [ruby-core:28166].

I second his proposal. To reduce the risk of this proposal to go without a response, I am creating this request.

Bareiss' algorithm has two big advantages:

  • can calculate the determinant of integer matrices using only integer intermediate results.
  • has minimal requirements on the number of bits required for intermediate results, thus reducing the floating point rounding errors.

Performance-wise, it has the same complexity O(n^3) as the current traditional method.
For Integer matrices, there is a big gain (say about 15 times faster) because the traditional version must use #quo and rationals, while the Bareiss algorithm can use #/ and keep the intermediate results as a Fixnum. The same goes for Bignum, of course (where the gain is even bigger).
For float version, the Bareiss algorithm is slightly slower (~33%):

                       user     system      total        real

Fixnum: det 8.660000 0.010000 8.670000 ( 8.672686)
Fixnum: det_bareiss 0.590000 0.000000 0.590000 ( 0.594747)
Float: det 0.160000 0.000000 0.160000 ( 0.154779)
Float: det_bareiss 0.240000 0.000000 0.240000 ( 0.237806)

I have revised Yu's code, and attached a patch.

I'm also attaching the performance test I used, for anyone interested.


matrix_bareiss.diff (1.65 KB) matrix_bareiss.diff Proposed patch marcandre (Marc-Andre Lafortune), 02/21/2010 06:16 AM
bareiss_test.rb (2.26 KB) bareiss_test.rb Performance test file marcandre (Marc-Andre Lafortune), 02/21/2010 06:16 AM
newdet.patch (8.77 KB) newdet.patch marcandre (Marc-Andre Lafortune), 04/26/2010 03:37 PM

Also available in: Atom PDF