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?
1 Answer
$\begingroup$
$\endgroup$
4
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}]]
-
$\begingroup$ Thanks! Do you know where to find what Det exactly does? $\endgroup$– SofJul 24, 2014 at 17:51
-
$\begingroup$ Documentation Center page tutorial/SomeNotesOnInternalImplementation#7441 says, "
Detuses direct cofactor expansion for small matrices and Gaussian elimination for larger ones." $\endgroup$– murrayJul 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$– SofJul 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