Project

General

Profile

Feature #2772

Matrix: Calculating determinant using Bareiss algorithm [patch]

Added by marcandre (Marc-Andre Lafortune) over 9 years ago. Updated about 8 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(n3) 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

History

#1

Updated by keiju (Keiju Ishitsuka) over 9 years ago

=begin
Hi, Marc-André

Did you test for Integer, Rational, Complex, and these mixed Matrix?

Please commit it if it was tested.
=end

#2

Updated by marcandre (Marc-Andre Lafortune) over 9 years ago

  • Status changed from Open to Assigned
  • Assignee changed from keiju (Keiju Ishitsuka) to marcandre (Marc-Andre Lafortune)

=begin

=end

#3

Updated by marcandre (Marc-Andre Lafortune) over 9 years ago

=begin
Unless there is objection, the official spec of determinant will be to calculate the determinant using the algorithm of its choice.

Implementation will rely on #determinant_bareiss and #determinant_gaussian (depending on types of the elements), and users needing a specific algorithm can call those directly.

=end

#4

Updated by keiju (Keiju Ishitsuka) over 9 years ago

=begin
Hi. Marc-Andre,

In [ruby-core:29154] the message: "[ruby-core:29154] [Feature #2772]
Matrix: Calculating determinant using Bareiss algorithm [patch]", on
Mar/31 12:14(JST) Marc-Andre Lafortune writes:

Unless there is objection, the official spec of determinant will be
to calculate the determinant using the algorithm of its choice.

Implementation will rely on #determinant_bareiss and
#determinant_gaussian (depending on types of the elements), and users
needing a specific algorithm can call those directly.

I agree the idea that the choice is possible.
Which is the default det defined, determinant_bareiss or determinant_gaussian?

-- keiju

=end

#5

Updated by marcandre (Marc-Andre Lafortune) about 9 years ago

=begin
I have worked on the determinant (and the rank) methods for Matrix.

Unless I hear arguments against it, the methods #determinant_e and #rank_e will be deprecated. I don't know where the algorithm comes from, but it checks to see if the elimination didn't succeed, i.e. the float calculation introduced some small rounding error and that error remains instead of 0 (a sort of noise). In that case, the noise is then used as a pivot, so many values get divided by a small noisy value that should have been 0. Seems like a bad idea to me, and my informal tests seem to confirm that this gives erroneous results more often than the straight gaussian elimination (and much more than the bareiss-gauss elimination).

I've attached the patch I have so far if anyone is interested.

Note: this patch fixes a bug with #rank causing many rectangular matrices to not have the right rank (e.g Matrix0,1],[0,1],[0,1.rank returned 2, now returns 1)

Also, Matrix#singular? and #regular? will raise an error for non-square matrices.
=end

#6

Updated by marcandre (Marc-Andre Lafortune) about 9 years ago

  • Status changed from Assigned to Closed
  • % Done changed from 0 to 100

=begin
This issue was solved with changeset r27554.
Marc-Andre, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end

Also available in: Atom PDF