Down the rabbit hole... That's where I've been going, in my bits and pieces of spare time. The particular rabbit hole of the moment is matrix operations on gigantic (m x n on the order of 10M) but quite sparse (non-zero entries less than a couple percent). These matrices are used to solve large systems of linear equations, where most operations are done on rows. There are some special challenges here. For instance, the sparsity changes (both up and down) as the calculations proceed.
I'm far from the first person to ever solve such problems – people were working on this exact problem back in the '50s and '60s. There's an enormous body of both research and practical implementations – but remarkably little that's open source, and none that I've been able to find in Java that's well-suited to my problem (circuit simulation). I'm quite surprised by this. On digging into what it would to implement it myself, I've discovered that it's not really all that hard, and that most of the challenges are in optimizing for the large scale of the operations involved. Some of the optimization is actually compression. That all feels like familiar territory – I know very little about matrix arithmetic, but there are a lot of articles and papers on implementation freely available on the web, and it all looks like stuff I should be able to do a good job implementing.
So down the sparse matrix arithmetic implementation rabbit hole I go :)
No comments:
Post a Comment