# Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I am having trouble finding algorithms which perform well on a massively parallel architecture where there is no shared memory between CPU and GPU.

However, on the wikipedia page for the $\mathsf{NC}$ complexity class states that the determinant (and inverse) of matrices lies within this class, which makes me believe that there do exist algorithms which perform well on massively parallel architecture.

Can anyone provide me with a reference to such an algorithm, or is it just proved that the determinant and inverse of a matrix lies within $\mathsf{NC}$ without a current algorithm having been developed.

• Explicitly computing the inverse of a matrix is a horribly ill-conditioned problem. It may be more worth your while to examine solving linear systems rather than computing matrix inverses, as this is generally what people need anyway. The choice of algorithm depends on a few factors. Are you looking at sparse or dense matrices? Iterative or direct solution methods? Symmetric? Positive-definite? Aug 24, 2014 at 19:11
• @korrok I am looking at dense matrices at the moment (although information regarding sparse matrix optimizations will be useful later when I get around to implementing them). I am not against either iterative or direct solution methods; providing they do not affect performance on massively parallel architectures. I don't intend to place restrictions on the user as to the nature of their matrix, so I can't guarantee symmetry or positive-definiteness. Aug 24, 2014 at 19:14

The class NC is the class of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. Is your problem to decide - or actually compute the Determinant of a Matrix? Chistov's algorithm solves for the determinant in the class NC with $(log$ $n)^2$ processors, and is the best(?) so far for the class NC(Reference: Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. A. L. Chistov ). As an aside, the question whether the class P is equivalent to NC is still open.
Therefore we opted to parallelising the algorithm for an MPI cluster. Here we observed linear gain in performance as evidenced by Table 3. This is consistent with the fact that the dominating term in the overall complexity of the algorithm $O(N^3)$ is due to computations, and the complexity of data transfers $O(N^2 \log T)$ is comparatively small.