josdejong/mathjs — pull request #158 by bcuccioli (2014-04-07 07:15:18+00:00)
Title: Implement poly-time determinant without divisions.

This is an implementation of det that runs in O(n^4) time and does not use any divisions, eliminating the rounding issues. While the time complexity has regressed from O(n^3), there is no longer a need for rounding, and the implementation is now amenable to matrices over rings, i.e. matrices whose entries are polynomials, other matrices, etc. (There is currently no known determinant algorithm in O(n^3) which does not use divisions. It's theoretically possible to get it down to O(n^3.188) but this is a lot more complicated).

This is based on the paper 'A Simple Division-Free Algorithm for Computing Determinants' (Bird 2011), which can be found at http://www.sciencedirect.com/science/article/pii/S0020019011002353