From: Marc-Andre Lafortune Date: 2010-02-21T06:16:38+09:00 Subject: [ruby-core:28273] [Feature #2772] Matrix: Calculating determinant using Bareiss algorithm [patch] Feature #2772: Matrix: Calculating determinant using Bareiss algorithm [patch] http://redmine.ruby-lang.org/issues/show/2772 Author: Marc-Andre Lafortune Status: Open, Priority: Normal Assigned to: Keiju Ishitsuka, Category: lib, Target version: 1.9.2 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. ---------------------------------------- http://redmine.ruby-lang.org