Fast Determinant Calculation
Someone came to me recently for some help on computing determinants. Determinants of 2×2 and 3×3 and maybe even 4×4 matrices are trivial and you can easily hard code the expanded symbolic form. Determinants of bigger matrices are much harder and require careful thought.
First some rules:
- Singular matrices have determinant zero. Simple, but often overlooked.
- If you require a spectral decomposition at a later stage, the easiest is the product of the eigenvalues (the matrix cookbook is a handy reference.)
- For triangular matrices, it’s the product of the diagonal entries.
- The determinant of the product of two matrices is the product of their determinants.
Using the above rules, the first step is to factor your matrix into two triangular matrices. The LU decomposition achieves this. In general, a permutation matrix allows all ones on the diagonal of L. If you only care about the absolute value of the determinant, simply computing the product of the diagonal values of U gets you the determinant.
If your matrix is symmetric and positive definite, then you can use a specialization known as Cholesky decomposition which makes L the transpose of U (doing half the work with half the storage.) The determinant is then the product of the square of the diagonal elements. Diffusion tensors are covariance matrices (symmetric, positive definite) and so this decomposition always applies.
This reminds me of one my undergrad toys I had worked with one buddy of mine. You can take a look at it here: http://www.geocities.com/dhruvbird/eqnc/.
So its basically a distributed equation solver, solves system of linear equation. At the core of system is solving determinant in trivial way but merging results back to calculate final value. Though we didnt do any rigorous benchmarks works decent.
That’s real neat. Brings back bad memories of trying to solve linear systems by hand in high school via Cramer’s rule.
Determinants are rich. Most of us are only familiar with linear algebraic methods, but as the amount of data becomes too big to fit in memory, we need novel methods such as yours. More promising is combinatorial random approaches (Las Vegas/Monte Carlo kind.)