1
$\begingroup$

I've been trying to design an algorithm for computing determinant of Big square Matrices (N <= 1000). I am allowed to use multithreading, but still, I can't design the algorithm. The assignment states, that I should use Gaussian elimination method. Yet, there are no input data, so the testing data is on me. For big matrices (N ~1000) it's a binary matrix, otherwise - matrix of integers. I wonder, if there exists a relatively time efficient ( less than 10 seconds ) multithread algorithm for this task. Would be glad to hear opinions.

EDIT:: I came up with idea of using partial pivoting to find a row with maximum at current iterating position, swapping it with current row (such heuristic keeps precision the best). And then, the parallel part, is to do row adding in multithread ( I used 8 threads, since it gave the best results on quad-core) if the matrix is big enough. Such method gave more precise results, and efficiency raised with matrix size relatively to one thread method. It actually turned out to be quite easy to implement.

$\endgroup$
  • $\begingroup$ Do you have to implement it yourself (assignment) or you're looking for something already implemented? You can use Gaussian elimination to compute it (if you have to use it): have a look on Wikipedia. $\endgroup$ – wrong_path Jan 10 '18 at 15:10
  • 1
    $\begingroup$ That's correct. I doubt that computing the determinant in less than $O(n^3)$ for a dense $n\times n$ matrix is feasible in practice (in the same sense as matrix-matrix multiplication is $O(n^3)$, the Strassen and Winogradov algorithms notwithstanding). There is also likely not a lot of parallelism available. $\endgroup$ – Wolfgang Bangerth Jan 10 '18 at 16:55
  • 1
    $\begingroup$ That said, you can do multifrontal methods for the Gaussian elimination steps, which can run in parallel. Of course, this is an absolutely non-trivial enterprise on which you're likely going to spend months and thousands of lines of code. $\endgroup$ – Wolfgang Bangerth Jan 10 '18 at 16:56
  • 1
    $\begingroup$ No, not at all. Computing determinants is difficult for large matrices! $\endgroup$ – Wolfgang Bangerth Jan 10 '18 at 17:31
  • 4
    $\begingroup$ @LevKolomazov Then you should probably discuss this with the person that assigned the task -- maybe they had something specific in mind that you (and we) aren't realizing? Maybe they just wanted you to implement the standard Gaussian elimination and don't care about peak performance or multithreading (allowed does not mean required!) or very large matrices? (As an instructor, I much prefer students asking for clarification right away to them spending months grinding down a rabbit hole due to a misunderstanding...) $\endgroup$ – Christian Clason Jan 10 '18 at 17:31

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.