Project

General

Profile

Actions

Feature #2772

closed

Matrix: Calculating determinant using Bareiss algorithm [patch]

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

Status:
Closed
Priority:
Normal
Target version:
[ruby-core:28273]

Description

=begin
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.
=end


Files

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
Actions

Also available in: Atom PDF