From: Yu Ichino <noagony@...>
Date: 2010-02-13T20:02:56+09:00
Subject: [ruby-core:28166] Improved Matrix Determinant

Hi,
I have an idea on the stability and performance of matrix determinant.
Improved algorithm with complete source code is at the end of this post.
I hope someone would test it and give me a feed-back :-)

note:
 Similar issues have discussed in ruby-dev around 2005.
 They compromised to the current state.

Good Day,
Yu (Kyoto JAPAN)

------------------------
Ruby Matrix Library (matrix.rb) is easygoing and I love it.
Determinant (presumably rank too), however, contains critical flaws.
Ruby 1.9 API document says;
 [determinant] require 'mathn' for integer matrices. (already resolved?)
 [determinant_e] doesn't work for matrices with Float elements.

Flaws in current version (1.9.1)
 0. typo bug (http://redmine.ruby-lang.org/issues/show/1531)
    Matrix[[0,1],[1,0].determinant #=> nil error
 1. returns Rational without mathn (unnatural)
    Matrix[[0,1],[1,0]].det #=> (-1/1)
 2. indivisible fraction (quo) must be avoided (not exact)
 3. unnecessary swap operation (slow)

Solution
 fraction-free version of Gaussian elimination (Bareiss algorithm)
 1. mathn is unnecessary
 2. exact for integer matrix
 3. modest speed

Benchmark
 A: 10 random (Integer) matrix with size 44
  det:   10.0 sec
  det_e: 10.3 sec
  det_b:  1.3 sec
 B: 10 random (Float) matrix with size 44
  det:   0.36 sec
  det_b: 0.88 sec

Issue
 - what is the reason det is faster in Float?
 - many test cases required

#############################################
require 'matrix'
class Matrix
 def det_b
  abort '!error: not square!' unless square?
  n=row_size
  a=to_a
  (0...n).inject(1) do |det,k|
   i=a.transpose[k].slice(k...n).index{|e| e!=0}
   return 0 if i.nil? #not full ranked
   if i!=0 then
    a[k],a[k+i]=a[k+i],a[k]
    det*=-1
   end
   for i in (k+1)...n
    for j in (k...n).to_a.reverse
     a[i][j]=a[k][k]*a[i][j]-a[i][k]*a[k][j]
     a[i][j]/=a[k-1][k-1] if k!=0
    end
   end
   det/=a[k-1][k-1] if k!=0
   det*a[k][k]
  end
 end
end
#############################################

EOF the post.