1
$\begingroup$

I'm using the Det function in Mathematica to compute the determinant of an $n\times n$ matrix $A$ with entries of the form $a+bt$ with $a,b$ integers and $t$ a variable, and I would like to know what the computational complexity of this function is. For a non-symbolic matrix one can find its determinant in time $O(n^3)$ by Gaussian elimination, but it seems to be more expensive to compute the determinant of my matrix $A$. Does someone know how expensive?

$\endgroup$

1 Answer 1

2
$\begingroup$

I get a better fit with an asymptotic complexity between n^4 and n^5. I think Det is doing a lot of simplification of symbolic expressions, which may account for some of the increased complexity.

nMax = 35;
entry[] := RandomInteger[{-9, 9}] + RandomInteger[{-9, 9}]*t
findTime[n_] := Block[{m, time, det},
  m = Table[entry[], {i, 1, n}, {j, 1, n}];
  {time, det} = Timing[Det[m]];
  Return[{n, time}]
]
timingData = findTime /@ Range[nMax];

curve = Fit[timingData, x^4.5, x];
Show[ListPlot[timingData], Plot[curve, {x, 0, nMax}]]

Contrast this with floating-point matrix determinants, which nicely follow the x^3 asymptotic complexity:

nMax = 4000;
nSkip = 100;
findTime[n_] := Block[{m, time, det},
  m = RandomReal[{-9, 9}, {n, n}];
  {time, det} = Timing[Det[m]];
  Return[{n, time}]
]
timingData = findTime /@ Range[1, nMax + 1, nSkip];

curve = Fit[timingData, x^3, x];
Show[ListPlot[timingData], Plot[curve, {x, 0, nMax}]]
$\endgroup$
4
  • $\begingroup$ Thanks! Do you know where to find what Det exactly does? $\endgroup$
    – Sof
    Jul 24, 2014 at 17:51
  • $\begingroup$ Documentation Center page tutorial/SomeNotesOnInternalImplementation#7441 says, "Det uses direct cofactor expansion for small matrices and Gaussian elimination for larger ones." $\endgroup$
    – murray
    Jul 24, 2014 at 18:23
  • $\begingroup$ Is it possible to argue theoretically that it can be bounded by $O(n^5)$? I don't know how to use the fact that the entries contain a variable t and not just floating points.. $\endgroup$
    – Sof
    Jul 25, 2014 at 16:51
  • $\begingroup$ I think best possible is O(n^4) or possibly better with asymptoticvally fast matrix multiplication. Also there will be a factor to account for integer coefficient size. For a practical approach you might try doing it by explicit polynomial interpolation. $\endgroup$ Jul 27, 2014 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.