search

scijs / contributing

Contribution guide lines
10 stars 0 forks source link

Direct linear solvers #6

Open mikolalysenko opened 9 years ago

mikolalysenko commented 9 years ago

SciJS doesn't yet have a good linear solver. At the moment, we have the following simple package (thanks @substack) which works ok for smaller systems using an LU decomposition:

One step beyond this would be to implement some kind of pivoting/preconditioning to improve numerical stability, (that is do an LUP decomposition ). However, we'll also eventually need solvers which are optimized for more specialized types of matrices like positive semidefinite problems which frequently occur in solving linear least squares problems.

Eventually, I would like to get something which is equivalent in power/sophistication to MATLAB's \ operator (though this is a big and ambitious project). Still, I think we could eventually get there by moving in small steps. As a sketch of what we would need to get to that level of functionality:

These are roughly prioritized in the order of importance and ease of implementation. There would also be some final project to put them all together into one planner which selects an optimized algorithm based on the types of the inputs at run time.

rreusser commented 9 years ago

Added module for Gram-Schmidt QR decomposition. Still getting the hang of this. Will continue adding other algorithms/solvers.

mikolalysenko commented 9 years ago

Yes! Thank you so much for this work!

I added you to the organization, if you like you can now push commits directly to all the scijs repos.

Also, fyi you should start semver packages at version 1.0.0. Version 0.0.0 has some bad semantics which are best avoided (namely semver doesn't apply). It is better to just start 1 and aggressively increment versions as needed to document your changes.

rreusser commented 9 years ago

Not 100% sure what's best for triangular matrices. It's not hard to pack them into an n*(n+1)/2 length vector—BLAS has lots of methods for that—and would even be easy to extend and create triangular packed matrix getter/setter, but it feels ugly. Would be nice if triangular matrices could be passed around without double the zeros though.

rreusser commented 9 years ago

@mikolalysenko @Planeshifter — Not so necessary but so that we don't step on toes :smile:

Linear algebra roadmap:

Beyond that, we can get into iterative algorithms — SVG, eigenvectors, etc… Hoping to get through the above n-iterative algorithms in the next day or so.

rreusser commented 8 years ago

So todo items. Will check off once I've given them a once-over, confirmed that they work with generic matrices (this is totally neglected at the moment), and maybe an additional note for handling complex numbers, which probably isn't much of a priority. Also need to revisit the API. It wasn't until I tried to summarize how to use these that I realized some of them are a little tricky to understand (in-place vs out-of-place etc. just needs a once-over and maybe minor cleanup)