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

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

Timings on Maxima 5.28/SBCL (from before the replacement of 'invert' by
'invert_by_lu'). Size is slength(string(m[3,4])).

m5: genmatrix(m,5,5)$

       Time  Size ratsimp time
^^:    55mS  2929    305mS
inv:    4mS  2931    289mS
lu:  2370mS  7089   5999mS

ndiag(m,n):=genmatrix(lambda([i,j],if abs(i-j)<=n then q[i,j] else 0),m,m)$
n102: ndiag(10,2)$

       Time  Size ratsimp time
^^:   292mS  3230   1209mS
inv:  204mS  3346   1168mS
lu:  6891mS  3700  27633mS

A very sparse matrix with small determinant; Size is total size, not just
one element
sp12:
matrix([0,q[1,2],0,0,0,0,0,0,q[1,9],0,0,0],[0,0,0,q[2,4],0,q[2,6],q[2,7],0,0,0,0,0],
[0,0,0,0,0,0,q[3,7],0,0,0,0,0],[q[4,1],0,0,0,0,q[4,6],0,0,0,0,q[4,11],0],
[0,0,q[5,3],0,0,0,0,0,q[5,9],0,0,0],[0,0,0,0,0,0,0,0,q[6,9],0,0,0],
[0,0,0,q[7,4],0,q[7,6],0,0,0,0,0,0],[0,0,0,0,0,0,0,q[8,8],0,0,q[8,11],0],
[0,0,0,0,0,0,0,0,0,0,0,q[9,12]],[0,0,0,0,q[10,5],0,0,q[10,8],0,0,0,0],
[q[11,1],0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,q[12,6],0,0,q[12,9],q[12,10],0,0])

       Time  Size ratsimp time
^^:     6mS  1848      9mS
inv: 1775mS 10447    240mS
lu:   730mS  1856      8mS




On Fri, Apr 19, 2013 at 3:51 AM, Robert Dodier <robert.dodier at gmail.com>wrote:

> On 2013-04-16, Dmitry Shkirmanov <piminusmeson at bk.ru> wrote:
>
> > Hello, list. I have wxmaxima program that takes a few seconds to run
> > with maxima 5.29.1. But  in maxima 5.30.0 it freezes.  Is there any way
> > to make it work with maxima 5.30?
>
> Well, it turns out the problem is very simple. The previous version of
> the function 'invert' used the adjoint method, while the current version
> uses the LU decomposition. (Yes, it was yours truly who made the change,
> after some discussion on the mailing list.) For the matrices in the
> program given, the results are substantially different -- the ones
> produced by the adjoint method are "simpler".
>
> Not sure where to go from here. I remember from working on the code that
> the adjoint method often produces 'simpler' results, but it is practical
> only for small matrices. Maybe use the adjoint method for small matrices
> and punt to LU otherwise? Just guessing.
>
> In the case at hand, I think all you have to do is load(invert) before
> loading the temp3.wxm script -- share/matrix/invert.mac is an
> implementation of the adjoint method (in fact the previous 'invert'
> function was a Lisp version of that code).
>
> best
>
> Robert Dodier
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>