[ruby-core:28273] [Feature #2772] Matrix: Calculating determinant using Bareiss algorithm [patch]

Feature #2772: Matrix: Calculating determinant using Bareiss algorithm [patch]
http://redmine.ruby-lang.org/issues/show/2772

Author: Marc-Andre Lafortune
Status: Open, Priority: Normal
Assigned to: Keiju Ishitsuka, Category: lib, Target version: 1.9.2

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.


----------------------------------------
http://redmine.ruby-lang.org