search

sloisel / numeric

Numerical analysis in Javascript
http://www.numericjs.com/
Other
1.42k stars 177 forks source link

LU decomposition (Solving Ax = b for square A) #5

Closed yuzeh closed 12 years ago

yuzeh commented 12 years ago

Hi, I've written some code that performs LU decomposition square matrices.

The added functions:

numeric.LU(A, fast=false): performs LU decomposition on a square matrix A. If fast=true, then this decomposition destructively modifies A.

numeric.solve(A, b, fast=false): solves Ax=b for x on square matrix A. If fast=true, then this decomposition destructively modifies A.

I added a unit test that tests the functionality of the solver. It shows the answers from doing solve(A, b) and dot(inv(A), b) are the same.

In addition, I added a benchmark (benchmark2.html) that compares performance of solve(A, b) and dot(inv(A), b). At high dimensions (n > 200), the solve operation is dominated by the matrix clone (which doesn't happen when you pass in fast=true). I also noticed that if you tried to compare the fast version to the slow version (at least in Chrome), V8's static branch prediction kicks in and messes the results. In Firefox, though, they are equally fast.

sloisel commented 12 years ago

Wow with my performance tweaks this is hilariously faster than numeric.inv/numeric.dot. I did not see that coming (although I should have guessed from the operation counts).