## Feature #2772

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

**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**

### History

#### 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

#### 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

#### 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

#### 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

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

**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 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

#### Updated by marcandre (Marc-Andre Lafortune) over 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