Roundtrip to Shanghai via Tokyo
Kohei Yoshida's Webspace
Ok. I’ve just finished coding a new matrix inversion algorithm which uses LU factorization with forward and backward substitutions to derive an inverse matrix. This one should be a lot faster than the one I currently use in my simplex algorithm.
An update of the solver package with this new algorithm integrated will follow soon (probably tomorrow).
Wrote up an LU factorization algorithm for a square matrix of arbitrary size, and observed it to work pretty well on several small-sized matrices (n < 10). I expect this algorithm to perform reasonably on larger-sized matrices, though I still need to run some confirmation testing using larger-sized matrices (it does O(n^2) comparisons and 2n^3/3 flops). Once that’s done, I can then use this LU factorization algorithm as the building block for developing a matrix inversion algorithm.
I was somewhat frustrated by how the majority of matrix-related resources I’ve checked avoid showing specifics of matrix inversion algorithm. The reasoning is that such algorithm would be highly inefficient and one should consider directly solving a system of linear equations instead of inverting a matrix first then solving it. I have no doubt what they say is true, but the sad fact is that, sometimes one may need to explicitly compute an inverse matrix as part of another larger algorithm. :(
I have been busy studying data structure for the past week to partly refresh and partly deepen my understanding of the subject. The obvious side-effect of this is that I haven’t been able to spend much time coding. But hopefully this study effort will pay off.
Also, I’m firmly convinced that I need to spend significant amount of time studying on matrix computation essentials in order to be able to develop reasonably-fast matrix calculation algorithms (I got the book by the way). The algorithms I use for linear programming relies heavily on matrix operations, so this effort is absolutely important. And yes, I am aware that there are libraries out there that already do fast matrix computations, but using them without having some idea of what they may be doing internally bothers me quite a bit.
Meanwhile, my patch for fixing Calc’s erf/erfc functions (i55735) is proposed for 2.0.2. Jody helped me on minor performance improvement.
Ok. I’ve done a new snapshot (rev. 86). This time it supports saving and loading of a model with a current document, which should help those who are interested in testing it do repeat-testing on the same optimization models (that’s usually the case). Plus it’s simply more convenient to not have to define same models time and time again. Now, that can be a pain!
As for the slow execution of inverse matrix computation that I discussed in my previous blog entry, I did a minor, very simple performance tweak which fortunately resulted in a pretty darn good improvement on sparse matrices (i.e. matrices with many zero elements). But for the real fix I still need a new algorithm. Hopefully the new book I’ve ordered (it’s on its way from amazon.com) will help me toward finding a fix. Maho-san told me that, that surprisingly slow algorithm that’s in my code right now is called Cramer’s formula. Well, good to know its name…
I should also mention this: someone has given me a licensed copy of Microsoft Visual Studio 2003 (thank you Brandon!). Now I need to find a reasonably-capable Windows machine so that I can set it up and play around and eventually release a Windows binary package.
One user has reported a case where the Solver stops responding when trying to solve a moderately-sized model. So I investigated. After hours of wading through my code and test runs, here is what I’ve found.
First, this was not a case of infinite loop, although at first sight it seemed that way. The computation was progressing very, very slowly. Second, this “freeze” was caused by a very inefficient algorithm for calculating an inverse matrix. It was fast enough for a small sized matrix, but once the matrix size grew its inefficiency started rearing its ugly head. Conclusion: I need to come up with a new and efficient way for inverse matrix calculation.
Well, no big deal, right? I suppose I just need a good reference book on matrix computations.