Feature #2772: Matrix: Calculating determinant using Bareiss algorithm [patch]

• Status: Closed
• Assignee: marcandre (Marc-Andre Lafortune)
• Target version: 1.9.2

[marcandre (Marc-Andre Lafortune)]

=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

[keiju (Keiju Ishitsuka)]

=begin
Hi, Marc-André

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

Please commit it if it was tested.
=end

[marcandre (Marc-Andre Lafortune)]

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

=begin

=end

[marcandre (Marc-Andre Lafortune)]

=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

[keiju (Keiju Ishitsuka)]

=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

[marcandre (Marc-Andre Lafortune)]

• File newdet.patch newdet.patch added

=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 Matrix[[0,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

[marcandre (Marc-Andre Lafortune)]

• 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