From: Marc-Andre Lafortune Date: 2009-05-29T04:18:59+09:00 Subject: [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