I have a C++ matrix class which can do the following operations on a square matrix related to determinant calculation:
- LU Decomposition
- Calculation of eigenvalues
- 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?
Best Answer
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).