#1629 determinant of large numerical matrices cannot be calculated

open
Barton Willis
4
2009-05-02
2009-03-28
Anonymous
No

I have a 16x16 complex numerical matrix of which I need to calculate the determinant. Maxima cannot do that. It seems to be caused by the fact that complex numbers are not automatically simplified. At least, if I restrict myself to a 3x3 submatrix, I get a value like the following:

0.022747564417433*(1.7248389564175436*10^-4*(0.87091047526227-0.49144169957224*%i)-1.7248389564175436*10^-4*(0.75680249530793*%i-0.65364362086361))*%i+0.0031407832308855*(0.0012492388804478*(-0.90929742682568*%i-0.41614683654714)*(0.87091047526227-0.49144169957224*%i)-0.0012492388804478*(0.25405661252734*%i-0.96718934941982)*(0.75680249530793*%i-0.65364362086361))-0.054917478527522*(7.1445168865760247*10^-5*(0.25405661252734*%i-0.96718934941982)-7.1445168865760247*10^-5*(-0.90929742682568*%i-0.41614683654714))

This is the output from a 3x3-Matrix, so it is no wonder that it can't handle a 16x16-matrix. I am not sure if that is really a bug, even though I cannot see a reason that such a behavior should be desirable.

Discussion

  • I forgot to include: working on ubuntu 8.04 and maxima 0.7.1 supplied in the ubuntu universe repositories.

     
  • Barton Willis
    Barton Willis
    2009-03-28

    I agree that this behavior is undesirable. For a possible workaround, try setting ratmx to
    true:

    (%i3) m : matrix([4+%i, 5],[1-%i,7]);
    (%o3) matrix([%i+4,5],[1-%i,7])

    (%i4) determinant(m), ratmx : false;
    (%o4) 7*(%i+4)-5*(1-%i)

    (%i5) determinant(m), ratmx : true;
    (%o5) 12*%i+23

     
  • (%i6) M:matrix([0.5+1.5*%i,0.67*%i],[1,2]);
    (%o6) matrix([1.5*%i+0.5,0.67*%i],[1,2])
    (%i7) determinant(M);
    (%o7) 2*(1.5*%i+0.5)-0.67*%i
    (%i8) determinant(M),ratmx:true;
    `rat' replaced 0.5 by 1/2 = 0.5
    `rat' replaced 1.5 by 3/2 = 1.5
    `rat' replaced 0.67 by 67/100 = 0.67
    (%o8) (233*%i+100)/100
    (%i9) rectform(determinant(M));
    (%o9) 2.33*%i+1.0

    For floating point numbers, rectform might be the better workaround. However, both workarounds only help, beautify the output, they do not help the basic problem that for larger matrices the computing time grows quickly towards infinity. I would guess that to resolve the problem, the internal handling of floating point complex numbers has to be changed so that they are added up right away internally and not kept as one long equation until we simplify it with rectform or ratmx. Btw: already for a real 16x16 matrix, it takes maxima a few minutes to calculate the determinant, while mathematica needs a few milliseconds for exactly the same matrix. Maybe a more efficient algorithm for the calculation of a numerical determinant could also be useful.

     
  • Barton Willis
    Barton Willis
    2009-03-31

    The function determinant is untested, so be careful:

    (%i28) m : genmatrix(lambda([i,j], random(2.0) + random(2.0) * %i - (1.0 + 1.0*%i)), 16,16)$
    Evaluation took 0.0700 seconds (0.0700 elapsed)

    (%i29) determinant_by_lu(m, 'complexfield);
    Evaluation took 0.0200 seconds (0.0200 elapsed)
    (%o29) -47713.90022880313*%i-6649.759043787237

    (%i30) m : genmatrix(lambda([i,j], random(2.0) + random(2.0) * %i - (1.0 + 1.0*%i)), 32,32)$
    Evaluation took 0.1100 seconds (0.1100 elapsed)

    (%i31) determinant_by_lu(m, 'complexfield);
    Evaluation took 0.0600 seconds (0.0600 elapsed)
    (%o31) 3.2540557083226812*10^+14*%i+3.663603682227415*10^+14

    (%i34) m : genmatrix(lambda([i,j], random(2.0) + random(2.0) * %i - (1.0 + 1.0*%i)), 64,64)$
    Evaluation took 0.4200 seconds (0.4200 elapsed)
    (%i35) determinant_by_lu(m, 'complexfield);

    Evaluation took 0.3400 seconds (0.3400 elapsed)
    (%o35) -5.100608386826365*10^+37*%i-1.9076027933472101*10^+37

    (defun $determinant_by_lu (m &optional (fld-name '$generalring))
    ($require_square_matrix m "$first" "$determinant_by_lu")

    (let* ((fld ($require_ring fld-name "$second" "$determinant_by_lu"))
    (acc (funcall (mring-mult-id fld)))
    (fmult (mring-mult fld))
    (fconvert (mring-maxima-to-mring fld))
    (n ($first ($matrix_size m)))
    (perm) (d))

    (setq m ($lu_factor m fld-name))
    (setq perm ($second m))

    (setq m ($first m))
    (loop for i from 1 to n do
    (setq d (funcall fconvert (m-elem m perm i i)))
    ;;(if ($matrixp d) (setq d ($determinant_by_lu d fld)))
    (setq acc (funcall fmult acc d)))
    (bbsort1 (cdr perm))
    (funcall (mring-mring-to-maxima fld) (if sign (funcall (mring-negate fld) acc) acc))))

     
  • Looks great! I know this is not a help forum, but I couldn't find anything, so I will still ask: How can I get wxmaxima to use this function? I tried just pasting it into the command line and I tried pasting it into the command line adding a :lisp in front, but both ways didn't work. Do I have to put it somehow into the source code?

     
  • Barton Willis
    Barton Willis
    2009-04-04

    Save the function in a file "determinant_by_lu.lisp" . First, you must
    load("linearalgebra"); after that load("determinant_by_lu.lisp"). Depending
    on where you save the file determinant_by_lu.lisp, you may need to use
    a full pathname. That's all you need to do. Your method of doing :lisp(defun ...
    should work; maybe a paren got dropped when you tried it.

    (%i5) load("linearalgebra")$
    (%i6) load("determinant_by_lu.lisp")$

    (%i7) m : genmatrix(lambda([i,j], random(2.0) + random(2.0) * %i - (1.0 +1.0*%i)), 32,32)$

    (%i8) determinant_by_lu(m, 'complexfield);
    (%o8) 8.2553048649832906*10^+13*%i+1.8063356113996187*10^+14

    If you think this function is useful, I'll appended it to the linearalgebra package, update
    the user documentation, and append testing code

     
  • Uwe Schilling
    Uwe Schilling
    2009-04-28

    Ok, it works now, I had a few problems making it run, though, maybe due to my old maxima version (5.13)

    I do think it is useful. In fact, I think the best thing would be not to only include it in the linear algebra package, but to make maxima call it automatically, if a purely numerical matrix is handed over to the function determinant. If that is not possible or desired, I guess including it in the linearalgebra package is the best option.

     
  • Barton Willis
    Barton Willis
    2009-05-02

    • labels: 887077 --> Share Libraries
    • priority: 5 --> 4
    • assigned_to: nobody --> willisbl