0
$\begingroup$

I searched the web and found some C code for calculating the determinant of a $n\times n$ matrix. This code however seems timing complexity, and run pretty slow especially when handling a larger matrix, for instance, $1000\times1000$ matrix. I need calculate the determinant of a covariance matrix of a multivariate normal distribution, I want to know is there any rapid way, or code for this purpose, thanks for your help.

$\endgroup$
  • 1
    $\begingroup$ What are you trying to do with the determinant? There is probably a different (better) way to achieve that without going through the determinant explicitly. $\endgroup$ – Tyler Olsen Mar 3 '16 at 21:07
  • $\begingroup$ For calculating the information gain for a continous signal, however, based on Wolfgang's comments, I think it's better to finger out some alternative way to do this. $\endgroup$ – J.Doe Mar 3 '16 at 21:22
  • 2
    $\begingroup$ @J.Doe do you need to calculate the determinant or just the log-determinant? the latter can be calculated from the Cholesky factor of your covariance matrix without running into problems with numerical overflow. $\endgroup$ – GoHokies Mar 3 '16 at 21:30
4
$\begingroup$

You cannot accurately compute the determinant of a large matrix in floating point arithmetic. Every algorithm I know of would be terrifyingly slow anyway, but the reason why people don't compute determinants for large matrices is not because of run time: it is because of accuracy issues.

The reasons this is so because, in essence, when you want to compute the determinant, you need to compute the eigenvalues. There are many ways, the simplest being to just compute an LU decomposition of the matrix. But some of them may be small and some of them may be large. If you multiply together the eigenvalues, this does not create a problem if there are only a few of them. But if you have a large number of rather disparate numbers, all of which are only inaccurately known, you get into trouble because of cancellation effects unless the eigenvalues you have happen to be distributed rather specially distributed.

To see why this is so, consider a $1000\times 1000$ matrix whose eigenvalues happen to all be around 10. The first problem is that the determinant would be $10^{1000}$, too large to be represented by double precision, even though each individual eigenvalue is moderately sized. Secondly, if you multiply many numbers, each with their own finite accuracy, you'll amplify these inaccuracies to the point where you don't have much accuracy left in the end result.

$\endgroup$
  • $\begingroup$ Wolfgang, thank you so much for spending your time to answer my question, i think your answer make a lot of sense to me. $\endgroup$ – J.Doe Mar 3 '16 at 21:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.