Re: Symbolic inverse of a 12x12 matrix

Bob Lewis and Susan Lewis wrote:

>> spasmous wrote:
>>
>> > Actually I retract what I said - MATLAB bails out
>> after a few minutes
>> > for a 10x10 symbolic inverse.
>> > .......
>>
>> Thanks for the two posts though. I could have wasted
>> some time trying out
>> matlab for this.
>>
>> Mathematica is happily handling the problem (the raw
>> inverse of the 12x12
>> matrix takes about 11 seconds), except that a
>> subsequent FullSimplify step
>> to clean up the expressions is causing some memory
>> problems on some
>> machines.
>>
>> Matlab/octave are good for numerical problems
>> involving matrices (though I
>> would always code anything that needed a lot of speed
>> in f95) but as far as
>> symbolic stuff goes, Mathematica is very nearly the
>> king (my experience of
>> maxima is limited, and of maple, almost
>> non-existent).
>
> I just noticed this thread. Sorry to be jumping in so late.
>
> (1) Can we see the actual matrix you want to invert? In my experience
> the number of symbolics and their placement will make a huge difference.
> If it is a secret, can you post an "equivalent" or slightly reduced case
> to test? I get the impression that the matrix contains only polynomials.
> Is that right?
>
> (2) In the experience of me and quite a few other people Mathematica does
> poorly at this kind of problem. The two best systems for polynomials and
> matrices are Fermat (written by me) and Magma.
>
> (3) You say Mathematica "finished" in 11 seconds but wouldn't or couldn't
> simplify. That is a common behavior with several large systems; they
> really are no way near completion -- at least as most people would define
> completion. When Michael Wester and I tested CA systems in 1999 [ref
> below] we met this behavior often.
>
> (4) I took an example from my web site [below] and reduced it to 12x12 to
> invert. The matrix has 12 different symbolic vars and about 98 entries
> that are 0 or 1. It takes Fermat about 12 minutes to invert, and about
> 400 meg of RAM. The entries in the inverse have around 10000 terms.
>
> (5) Someone mentioned LU decomposition. I used Fermat to produce the
> fraction-free LU decomposition [ref below] of the above matrix. The L
> part has several entries with more than 1000000 terms.
>
> Hope this helps.
>
> Robert H. Lewis
> Fordham University
>
> www.bway.net/~lewis
>
> R. Lewis and M. Wester, Comparison of Polynomial-oriented Computer Algebra
> Systems, SIGSAM Bulletin, Jan 2000.
>
> Nakos, Turner, and Williams, Fraction-free Algorithms for Linear and
> Polynomial Equations, SIGSAM Bulletin Sept 1997.
>
> Corless and Jeffrey, The Turing Factorization of a Rectangular Matrix,
> SIGSAM Bulletin Sept 1997.

Thanks for your post.

I managed to work out the memory problems and finish the simplification in
two steps (memory ran out halfway through simplification).

Finally, taking the inverse took 11 seconds. Taking the dot product with RHS
took 1 second, and simplification of the resulting 12 components took about
2 hours in all.

.