rockbot/vektor — pull request #17 by BillMills (2014-01-03 09:41:30+00:00)
Title: Fast Matrix Determinants & Benchmarking Example

As promised, here's a speed upgrade to Vektor's determinant calculator, by way of the Doolittle algorithm. Matrix.det() now tries this fast factorization, and falls back on the existing cofactor calculation when Doolittle fails (typically for sparse matrices). Benchmark gave me the following results comparing Doolittle and Cofactor calculations of the 5x5 determinant from the test suite:

node benchtest.js
cofactor det x 1,163 ops/sec ±0.52% (87 runs sampled)
doolittle det x 3,388 ops/sec ±0.50% (97 runs sampled)
Fastest is doolittle det

So for this calculation, Doolittle runs almost triple the ops/s.

This brings us to two important points that also came up in this development:

1. Benchmarking. I used [benchmark](https://npmjs.org/package/benchmark), mostly because it seemed popular and worked out of the box - does anyone have an opinion on this package? The /tests directory has an example, benchtest.js, of how to use this package; running this example will re-run the test on Doolittle v. Cofactor determinants I quoted above. I think it would behoove us to choose a standard prescription for settling "who's fastest" contests - either benchmark or something else.

2. Precision and testing. I never noticed before, but prior to this PR, vektor matrices rounded their entries off to 6 decimal places. This is fine in principle, but this rounding can compound itself in iterative calculations like Doolittle and cause tests to fail spuriously. I assume the number 6 was chosen because people really do want at least 6 decimal places of accuracy, so I upped this to 12 decimal places, and required the determinant calculations to be accurate to 10 decimal places in the tests. In general, we are certainly going to have to write tests with tolerances comparable to our roundoff; I erred on the side of super duper precise here, hopefully this is acceptable at least until we can agree on a prescription.