search

clvcooke / MatrixMath

A from scratch implementation of basic matrix manipulation and operations in C++
0 stars 2 forks source link

Determinant #5

Closed clvcooke closed 9 years ago

clvcooke commented 9 years ago

Write a function within the Matrix class which calculates and returns its determinant.

RowanFerrabee commented 9 years ago

Complete and committed to the master

RowanFerrabee commented 9 years ago

We should consider using the Leibniz formula (http://en.wikipedia.org/wiki/Leibniz_formula_for_determinants) for calculating determinants considering the current recursive formula is insanely inefficient.

ericye16 commented 9 years ago

Quoting from the first paragraph...

Directly evaluating the Leibniz formula from the definition requires \Omega(n! \cdot n) operations in general—that is, a number of operations asymptotically proportional to n factorial—because n! is the number of order-n permutations. This is impractically difficult for large n. Instead, the determinant can be evaluated in O(n3) operations by forming the LU decomposition A = LU (typically via Gaussian elimination or similar methods), in which case \det A = (\det L) (\det U) and the determinants of the triangular matrices L and U are simply the products of their diagonal entries.

RowanFerrabee commented 9 years ago

True that makes a lot more sense (too busy trying to make sense of the equation to read the paragraphs). We definitely need an rref function before we proceed so I'll open up a thread for that