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.
I have uploaded a new snapshot (rev. 81) to my Solver page. In this release, the most significant change is the support for cell range constraint definition. Well, actually that’s the only visible change since all the other changes are just implementation details.
In my previous snapshot, each constraint entry was used for defining only one constraint. But after some feedback from one user in Belgium I realized that that can be very inconvenient. So I implemented the cell range method. Hopefully I didn’t introduce any new bug with this.
Everybody has a blog these days, so I have decided to have one for myself just so that when someone asks “what’s your blog URL?” I can point to this page.
My on-going project these days is to improve the Optimization Solver component for Calc. Since the day I coded my first solver prototype in Python almost a year ago, this project has come a long way! It was originally just a Python command-line program. Now it’s become a full-fledged C++ UNO component with a pretty functional UI and Calc interface.
Still, it has a lot to improve. For one, my solver at this time only solves a constrained linear model, yet most of real-world problems are unfortunately non-linear. On top of that, the algorithmic complexity also increases when going from linear to non-linear.
For another, the solver is still a Linux only program. Technically speaking, to make it work under other platforms the only thing I’d need to do is recompile the source under those platforms. But given the limited time I have for this project, at this point I’d like to focus on just adding more functionality than worrying about porting to other platforms. Working toward porting is also difficult at this point since I don’t have a development environment set up for other platforms.
Anyhow, porting will be done sooner or later provided there is demand. So, patience, my friend. :-)