0
$\begingroup$

How to determine the computational cost associated with calculating determinant of an $n \times n$ matrix using the LU factorization?

$\endgroup$

1 Answer 1

0
$\begingroup$

With $M(n)$ the times for mutliplying 2 matrices, the factorization LU requires $O(M(n))$ with $M(n)>n^2$. Classical matrix multiplication complexity is $M(n)=O(n^3)$, some efficient way gives $M(n)=O(2^{2.373})$. To get such complexity for LU decomposition it is Coppersmith–Winograd algorithm.

Then to get the determinant of the matrix you have to add $2n$ multiplication.

$\endgroup$
4
  • $\begingroup$ A = LU So, det(A) = det(L)*det(u) On a text book, it says that this is $$ O(n^3) $$ please can you show me how to prove this? $\endgroup$
    – Malith
    Mar 10, 2015 at 10:59
  • $\begingroup$ Given an decomposition, the determinant is a product of $2n$ numbers, not $n^2$. $\endgroup$
    – Arthur
    Mar 10, 2015 at 13:45
  • $\begingroup$ The proof is a bit long to rewrite. You need to count the number of basic operation used in one algorithm, for instance the Crout method. An example with proof is available in this document math.univ-paris13.fr/~halpern/teaching/MACS1_2010/systemes.pdf $\endgroup$
    – Tanj
    Mar 10, 2015 at 15:23
  • $\begingroup$ For anyone reading, I believe the Coppersmith-Winograd algorithm is considered galactic, and therefore inefficient/infeasible for implementation on most if not all real datasets. $\endgroup$
    – Serge
    Jan 25, 2022 at 4:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .