[Maxima-bugs] [ maxima-Bugs-2718162 ] determinant of large numerical matrices cannot be calculated

[SourceForge.net <no...@so...>]

Bugs item #2718162, was opened at 2009-03-27 23:49
Message generated for change (Comment added) made by willisbl
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=104933&aid=2718162&group_id=4933

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Lisp Core - Floating point
Group: None
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Nobody/Anonymous (nobody)
Assigned to: Nobody/Anonymous (nobody)
Summary: determinant of large numerical matrices cannot be calculated

Initial Comment:
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.

----------------------------------------------------------------------

>Comment By: Barton Willis (willisbl)
Date: 2009-03-31 07:13

Message:
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))))

----------------------------------------------------------------------

Comment By: Nobody/Anonymous (nobody)
Date: 2009-03-28 14:58

Message:
(%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.

----------------------------------------------------------------------

Comment By: Barton Willis (willisbl)
Date: 2009-03-28 07:03

Message:
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

----------------------------------------------------------------------

Comment By: Nobody/Anonymous (nobody)
Date: 2009-03-27 23:51

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

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=104933&aid=2718162&group_id=4933