## Inverse matrix now faster

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).

## LU Factorization

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. :(

## Studying…

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.

## Solver update (rev. 86)

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.

## Large model makes execution very slow

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.