4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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? $\endgroup$
    – Daniel Shapero
    Aug 24, 2014 at 19:11
  • $\begingroup$ @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. $\endgroup$
    – Thomas Russell
    Aug 24, 2014 at 19:14

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

try this algorithm, it is close to what you are asking for ie optimized parallezed algorithm for the discriminant that may also deal with ill-conditioned matrices. complexity analysis sec4.2 p10 and in the appendix:

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.

A Parallel Algorithm for Calculation of Large Determinants with High Accuracy for GPUs and MPI clusters Beliakov, Matiyasevich

We present a parallel algorithm for calculating very large determinants with arbitrary precision on computer clusters. This algorithm minimises data movements between the nodes and computes not only the determinant but also all minors corresponding to a particular row or column at a little extra cost, and also the determinants and minors of all submatrices in the top left corner at no extra cost. We implemented the algorithm in arbitrary precision arithmetic, suitable for very ill conditioned matrices, and empirically estimated the loss of precision. The algorithm was applied to studies of Riemann’s zeta function.

Improve this answer
$\endgroup$
0
$\begingroup$

The NC algorithm for computing the determinant is Berkowitz's algorithm. See for example this paper by Soltys, which also links to the original paper, or various lecture notes on the subject.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I don't know if the algorithm is practical, by the way. $\endgroup$
    – Yuval Filmus
    Aug 26, 2014 at 1:36

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.