I am writing a numeric library to exploit GPU massive parallelism and one of the

Question

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 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 NC without a current algorithm having been developed.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.