New LU factorization in matrix inverse algorithm

One of the things I wanted to do as a remedy to my simplex algorithm (refer to my last blog entry) was to switch to another algorithm for LU factorization which is used in my matrix inverse algorithm. The original LU factorization algorithm obviously was not robust enough to inverse an initial matrix generated in solving Markus’ model. This time, instead of blindly looking for a new algorithm to use all over the net, I decided to dive into Calc’s code to see what algorithm Calc uses internally for matrix inversion since Calc was able to inverse the very matrix my own algorithm was not.

Of course, I can’t just copy and paste Calc’s matrix inverse code, but luckily there was a reference within the code from which it was derived, and I just happened to have a copy of that very same reference which one of my friends was kind enough to lend to me a few weeks ago. Lucky me!

Anyway, now my solver can at least solves Markus’ model, though my solution differs from the Excel Solver’s solution that he included because of simplex’s positive variable limitation (his Excel solution included negative numbers). Adding support for negative numbers shouldn’t be too complex, but requires a bit more work.

The new snapshot (revision 101) is up which includes this new LU factorization algorithm.

4 thoughts on “New LU factorization in matrix inverse algorithm”

  1. Great work Kohei !
    Why was it not possible to use Calc matrix inversion tooling by UNO call ?

  2. Thanks Laurent. :-)

    But this is actually an old blog entry (see the date?) somehow bumped up to latest date on the planet page.

    Anyway, the reason I didn’t use UNO was simple; the performance. My code needed to perform inverse matrix calculation in a numerically intensive iteration, and I didn’t want to have UNO’s overhead which would have affected runtime speed.

    Kohei

  3. hi Kohei

    that’s strange for the planet, but great as i did not see this entry :)

    Regarding not using UNO, did you benchmark ? This approach is against any re-uability of code, no ?

    Btw, great work !

    Laurent

  4. Hi Laurent,

    I did not benchmark, but since using UNO would have required that I convert my matrix object before passing it to the UNO call, and convert it back to my own matrix object for each iteration of the loop, I wasn\\\’t very attracted to that extra conversion work (for each iteration). Since all I needed was just a 20-lines of factorization code, using UNO for that didn\\\’t seem like the right path to me.

    Also, doing so would have required an instance of OO.o even for running the backend algorithm alone, which I wanted to make it as independent as I could make it so that I could unit-test the algorithm independently from the UI part. My code is partitioned into the independent numeric part and the UI part that is somewhat dependent of UNO. This design choice was precisely because of the need to run independent testing of the algorithms.

    Regarding the planet, there was some spam comments on this entry which I had to filter out. Somehow that caused this entry to appear on the planet page. No idea why. :-)

Comments are closed.