| brain activity log
25.03.2006 Saturday - matrixes
Yesterday and today my fundamental problem was inverting a matrix and
computing its determinant. I have written a nice template matrix class (I'll publish it
on this site sooner or later).
Computing the inverse of a matrix is pretty straightforward.
It can be done by Gauss elimination and has computational cost
comparable to n^3 where n is the rank. Writing the Gauss elimination
algo took a couple of hours yesterday night but afterwards I was able to invert
a 1000x1000 matrix in matters of seconds (Athlon64 3500).
A huger problem is the one of computing the determinant.
The Liebnitz formula is too complex to implement since it
involves enumerating all the permutations of the matrix columns.
Enumerations of n elements are n! and such complexity is
obviously out of range.
Using the recursive determinant formula is also a heavy approach
since it requires a lot of time and a really huge amounts of memory.
You have to compute ALL the minors of the matrix... which is too much.
I've written down a hybrid method that uses a sort of Liebnitz
approach with the first row and a recursive method for the minors.
It's still too much. Computing a 20x20 determinant is not feasible
in terms of time (it requires several hours) and it also eats a lot of memory
since you need to hold 20x20 + 19x19 + 18x18 + 17x17 + ... + 1x1 matrixes in memory at once.
I've readed of the LU decomposition approach which should be
comparable to the inversion in terms of complexity and memory usage.
The idea is to decompose our matrix in a product of two matrices: L and U.
L should be lower triangular and U upper triangular. Once such a decomposition
is known the determinant of the matrix is det(L) * del(U) which are
both products of the elements on the diagonal. There is an approach
in that L has all 1 elements on the diagonal so det(L) is even 1 (no need to compute it at all).
The problem, now, is to find the LU decomposition. I still
have to study better the algorithm. This will be a task for tomorrow
tough. Tonight I'll also ask Valeria about it. She's a matematician so she
probably will be able to give me some hints.
want more ?
... really ? :D
Browse around then.
You're viewing one post per page: you can view more, if you want.
The entries marked in red are the ones you're viewing now.
| 