Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a C++ matrix class which can do the following operations on a square matrix related to determinant calculation:

  1. LU Decomposition
  2. Calculation of eigenvalues
  3. Calculation of determinant by adjoint method

I want to calculate determinant. Which these there methods is faster? I can say that the answer is not "3", but at least can you compare the first two methods for me?

Is there any other numeric method which is better (faster and/or more reliable) than the ones in the list? My matrix class can also do QR decomposition and can solve linear matrix equations in Ax=b format; can these features be used in determinant calculation?

share|improve this question
1  
Gaussian elimination would be the best approach to use; QR is a bit more expensive, eigendecomposition is even more expensive, and expanding into minors/cofactors is ridiculously expensive. –  J. M. Dec 22 '11 at 16:35
add comment

1 Answer

up vote 1 down vote accepted

The cost (number of multiplication) for $LU$ decomposition is $$\frac{n^3}{3} + \frac{n^2}{2} - \frac{5n}{6}$$ Add an additional cost of $n-1$ to multiply out the diagonal elements of $U$ to get the determinant.

The cost (number of multiplication) for $QR$ decomposition is $$\frac{2n^3}{3} + n^2 + \frac{n}{3} - 2$$ Add an additional cost of $n-1$ to multiply out the diagonal elements of $R$ to get the determinant.

EDIT

MATLAB, for instance, computes determinant by performing an LU and then multiplying out the diagonal entries (and as J.M. points out keeps track of the sign by looking at the number of row swaps done during LU decomposition).

share|improve this answer
    
"MATLAB, for instance, computes determinant by performing an LU and then multiplying out the diagonal entries." - and takes care of the proper sign by counting how many row swaps were done while doing Gaussian elimination. –  J. M. Dec 22 '11 at 16:59
    
@J.M: Thanks. True. I shall update it. –  user17762 Dec 22 '11 at 17:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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