1
$\begingroup$

I've implemented an algorithm that can calculate the cofactor-matrix of a matrix in $\mathcal{O}(n^5)$.

The algorithm just step-by-step iterates over the whole matrix ($\mathcal{O}(n^2)$) and for every $(i,j)$ in the matrix, it then calculates the determinant of the "sub-matrix" (leaving off row $i$ and column $j$) by using the bareiss algorithm in $\mathcal{O}(n^3)$.

Is there a faster way to do this?

$\endgroup$
11
  • 3
    $\begingroup$ Computing determinants of anything is so vastly expensive that it is almost always a good question to ask what you actually need it for, and whether what you want to do could not also be done without actually computing determinants. $\endgroup$ – Wolfgang Bangerth Feb 22 '20 at 1:12
  • $\begingroup$ Your are working on integers, do I understand correctly? And you need an exact integer answer even if it is going to be astronomically huge? $\endgroup$ – Federico Poloni Feb 22 '20 at 9:45
  • $\begingroup$ No, I am working with vector<vector<double>> in C++. $\endgroup$ – user34175 Feb 22 '20 at 14:31
  • $\begingroup$ @chrysaetos99 then I would suggest switching to proper structures for matrices (raw double*, wrappers, external libraries), as while keeping the same asymptotic complexity, you will get the results much faster. Not sure it is your goal, though. $\endgroup$ – Anton Menshov Feb 22 '20 at 19:38
  • 1
    $\begingroup$ It seems to me that this question still does not have a satisfying answer. The most interesting case is the one when the matrix is singular or almost singular, and in this case using the formula $\det(A) A^{-T}$ is either outright impossible, or otherwise it probably still is a bad idea in terms of stability. It looks like there should be an $O(n^3)$ solution even for this case. $\endgroup$ – Federico Poloni Feb 23 '20 at 11:04
1
$\begingroup$

I prefer to use SVD (singular value decomposition) instead of calculating inverse and determinant directly. SVD is still $\mathcal{O}(n^{3})$ in time complexity, but I think is much more stable. For singular decomposition of $A$ you have:

$$A = U \Sigma V^{T}$$

Where $U$ and $V$ are orthogonal matrices and $\Sigma$ is just a diagonal matrix. So:

$$|\mathrm{det}(A)| = \prod_{i} \mathrm{diag}(\Sigma)_{i}$$

Please pay attention to the abs in the above formula, cause the only thing that we know is $\mathrm{det}(U),\mathrm{det}(V) = \pm 1$. Also, an inverse could be calculated from SVD as because $U$ and $V$ are orthogonal matrices:

$$A^{-1} = V \Sigma^{-1} U^{T}$$

So the co-factor is:

$$\mathbf{C} = \mathrm{det}(A) A^{-T}$$

$\endgroup$
2
  • 1
    $\begingroup$ I know that A^T is the transposed matrix, but what is meant by A^(-T)? Is it the transposed of the inverse? This also doesn't work, if det(A) = 0, right? $\endgroup$ – user34175 Feb 22 '20 at 16:52
  • $\begingroup$ @chrysaetos99 $A^{-T} = (A^{-1})^T$ of course a matrix with zero determinant does not have co-factor. $\endgroup$ – Alone Programmer Feb 22 '20 at 20:34
1
$\begingroup$

Determinants and matrix inversion are pretty numerically unstable, but if all you are going for is speed, you can compute $A^{-1}$ in $O(n^3)$ time, then we have the cofactor matrix given by $$ C = \mathrm{det}(A)(A^{-1})^T $$

$\endgroup$
1
  • 2
    $\begingroup$ And how do you get $\mathrm{det}(A)$? Even calculating the inverse of matrix is really bad idea. $\endgroup$ – Alone Programmer Feb 22 '20 at 1:28