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$
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 '14 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 '14 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 '14 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$ – Daniel Lichtblau Jul 27 '14 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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