algorithms for 'invert', was: program works with maxima 5.29.1 but freezes with maxima 5.30.0

Thanks, Stavros, for your timings.

There are various ways to speed up adjoint, determinant, Cramer, etc., by using 'hash consing' and 'memoization'.

'Hash consing' converts expressions that are EQUAL into expressions that are EQ.  This enables the use of EQ hash tables for memoization.

'Memoization' remembers the results from a function so that it doesn't have to be recomputed if the function is called with the same (i.e., EQ) arguments again.  Memoization can convert poorly performing programs like 'naive Fibonacci' into decent performers.  Memoization is closely related to so-called 'dynamic programming'.

But in a symbolic algebra system, hash consing + memoization can produce deeply nested expressions _with lots of shared substructure_.  Thus, although the result of det(M) may be polynomial in the number of CONS cells, if you 'deep copied' it, it could blow up exponentially, since expand(det(M)) in the worse case has n! terms for an nxn matrix M.  (It might also blow up exponentially if you tried to simply print it out using standard non-shared notation.)

So the complexity of det(M) might depend critically on what form you want the answer in: expanded or factored.

Thus, it isn't clear if you want to wait until you get a deeply nested & shared answer before simplification, or whether you want to simplify at each submatrix determinant.

An interesting test case for symbolic det(M) are Vandermonde matrices, whose determinants factor nicely.

At 05:16 PM 4/19/2013, Stavros Macrakis wrote:
>One of the rationales for preferring LU was speed.  I believe it is indeed faster in the float case, but it seems to be much slower and produce bigger results in many symbolic cases, especially dense ones (see measurements below).  If you eyeball them, the LU results are also much more deeply nested and don't seem to be a particularly simple/useful form for humans. The big disadvantage of ^^ is that it converts floats and bignums to rationals.
>
>So it doesn't looks like we should use LU for anything but floats and bfloats.  Of course, the measurements below are pretty simple-minded.  In particular, I didn't measure rational number, mixed rational/symbolic cases, elements in more exotic rings, etc.
>
>          -s