[ruby-core:23598] [Bug #1532] Improved matrix.rb [patch]

Bug #1532: Improved matrix.rb [patch]
http://redmine.ruby-lang.org/issues/show/1532

Author: Marc-Andre Lafortune
Status: Open, Priority: Normal
Category: lib, Target version: 1.9.2
ruby -v: ruby 1.9.2dev (2009-05-24 trunk 23554) [i386-darwin9.7.0]

The fact that the 'matrix' library is included in Ruby is very helpful.
There are currently some open bugs, and some improvements could make it easier to use.

Propositions:

1) Matrix#trace should raise an ErrDimensionMismatch if the matrix is not square
  
  Mathematically speaking, the trace is only defined for square matrices (ref: wikipedia, mathworld)
    Currently, Matrix[[1,2]].trace raises a NoMethodError: undefined method `[]' for nil:NilClass
    Note that Matrix[[1,2]].transpose.trace returns 1, although in mathematically, trace(M) = trace(transpose(M))
  
  Raising an ErrDimensionMismatch would bring #trace in line with #inverse
  
2) Matrix creation methods should perform checks and conversion so that values are stored as an Array of Arrays.
  
  Currently, no checking is done, so the following will all be constructed without an error or a warning:
    Matrix[:hello]
    Matrix[nil]
    Matrix[4], etc...

  Later on, confusing results or strange errors will happen. E.g.:
    Matrix[42].transpose  # ==> Matrix[[42], [0], [0], [0]]

  A TypeError should be raised if the argument is not convertible to an Array of Arrays.

  Moreover, non arrays that should be converted using :to_ary, to be consistent
  with the builtin library methods that accept array arguments (e.g. Array#transpose)

  Finally, conversion from Vector to arrays should be always be performed. Currently, 
    a = Matrix[[1,2],[3,4]]   # => Matrix[[1, 2], [3, 4]]
    b = Matrix.rows([a.row(0), a.row(1)]) # => Matrix[Vector[1, 2], Vector[3, 4]]
    a == b  # => false
  It would be more useful, intuitive and mathematically correct if a == b and b.to_s == "Matrix[[1, 2], [3, 4]]"

  The same is true for Vector creation methods. For example currently:
    Vector.elements(42, false).size # ==> 4
    Vector.elements(Vector[1,2,3]) == Vector.elements([1,2,3])  # ==> false
  It would be more useful, intuitive and correct if the first example raises an error and the second returns true

3) Matrix creators should enforce that a matrix is rectangular.

  Currently, a matrix with irregular rows can be created, e.g. x = Matrix[[1,2],[3]].
  Mathematically speaking, that is not a matrix.
  Basically none of the Matrix methods are of any use for non-rectangular matrices.
  Moreover, many strange errors can occur later on. For example, x.inverse will
  raise a "NoMethodError: undefined method `*' for nil:NilClass"
  
  It would be helpful to catch these cases at creation time.
  Many creation methods don't have to make any extra checks (e.g. Matrix.scalar), and
  all methods of Matrix can bypass this extra check when they have created the arrays themselves
  (e.g. Matrix#*). There would be a small cost for creation using Matrix.[] and Matrix.rows,
  although it is in O(rows) while most other operations are usually in O(rows x columns),
  so the performance difference would be minimal.
  
4) Matrix should deal with empty matrices.

  Currently, empty matrices like Matrix[] cause problem.
  For example Matrix[].determinant raises an error, so does Matrix[] * Matrix[].
  
  Moreover, if h = Matrix[[], []], then currently h.transpose.transpose != h
  
  While an alternative would be to raise and error, the best solution is to handle
  empty matrices properly, both 0x0, 0xn and nx0, as does MatLab, GNU Octave, etc...
  See doc and references to the literature in:
    http://www.gnu.org/software/octave/doc/interpreter/Empty-Matrices.html

5) Out of bound indices should be dealt with.

  a) Matrix#[row,col] should behave in a consisten way if either row or col is out of bounds.
  Currently it returns nil vs raises an obscure error (See redmine #1518.)
  
  b) Matrix[[1]].row(2) raises an obscure error, while Matrix[[1]].column(2) returns Vector[nil, nil]
  
  c) In a similar vein, Matrix[[1]].minor(2..2,1..1) currently raises an error but not
  Matrix[[1]].minor(1..1,2..2)
  
  Solutions:
  a) To be consistent with array lookup using [], Matrix#[] should return nil for out of bounds elements.
  A #fetch method could be added, but the fact that matrices normally won't contain nil or false
  makes it easy to deal with out of bounds references, e.g. m[r, c] || 0
  
  b) Contrary to nil, it is not easy nor useful to deal with Vector[nil, nil, ...].
  #row, and #column could raise an IndexError, but it is more useful and
  more coherent with Array#at, etc... to return nil.

  c) The same way Matrix#row and #col can be related to Array#at,
  Matrix#minor should have similar semantics to Array#slice. If either starting point
  is out of bounds, nil is returned. Otherwise a Matrix is returned, although it can
  be smaller than what was requested. This is similar to
    [:a, :b].slice(3..10)  # => nil
    [:a, :b].slice(2..10)   # => []
    [:a, :b].slice(1..10)   # => [:b]
    Matrix[[1], [2]].minor(0..10, 2..10) # => nil
    Matrix[[1], [2]].minor(0..10, 1..10) # => Matrix[[], []]
    Matrix[[1], [2]].minor(1..10, 0..10) # => Matrix[[2]]

6) Matrix#collect, Vector#collect, #collect2, #map2 should return enumerators if no block is given

  This would be more useful and is consistent with Array#each, etc...

7) Matrix#hash should have less collisions

  Currently, the following matrices have the same hash:
    Matrix[]
    Matrix[[0,0], [0,0]]
    Matrix[[1,0], [0,1]]
    Matrix[[42,42], [666,666]]
    Matrix[[1,2,3,4], [5,6,1,2], [3,4,5,6]]
  
  Ideally, these should have different hashes, since they are different matrices.

8) Matrix#compare_by_row_vectors, Vector#compare_by and Vector#init_elements should be made private or disappear.

  As per the documentation, these are not meant to be used.
  As such it would be best if they didn't appear in the list of methods.


The attached patch addresses all these issues.

Moreover, it addresses all matrix-related issues I could find on redmine:
  http://redmine.ruby-lang.org/issues/show/1020
  http://redmine.ruby-lang.org/issues/show/1515
  http://redmine.ruby-lang.org/issues/show/1516
  http://redmine.ruby-lang.org/issues/show/1517
  http://redmine.ruby-lang.org/issues/show/1518
  http://redmine.ruby-lang.org/issues/show/1526
  http://redmine.ruby-lang.org/issues/show/1531

Also fixed a bug with #determinant and #determinant_e that would raise an error for some matrices
(for instance any square matrix with m[0][0] == 0, e.g. Matrix[[0,1],[2,3]].determinant  # => error raised)

Finally, the following methods are performing faster:
  Matrix#collect
  Matrix#transpose
  Matrix#==
  Matrix#eql?
  Matrix#hash
  Vector#collect
  Vector#map2

Note that the branch 'runpaint' of rubyspecs has specs to this patch.


----------------------------------------
http://redmine.ruby-lang.org