search

pierre-vigier / Perl6-Math-Matrix

fully featured data type for matrix math
Artistic License 2.0
20 stars 6 forks source link

Determinant formula is wrong #30

Closed pierre-vigier closed 6 years ago

pierre-vigier commented 8 years ago

The determinant method implemented is not correct, here is an example where it does not work: my $a = Math::Matrix.new([[7, 3, 7, 1, 1, 4], [9, 7, 6, 1, 9, 1], [9, 6, 2, 5, 5, 6], [6, 0, 3, 5, 1, 3], [0, 5, 0, 0, 5, 7], [4, 2, 7, 6, 1, 9]]); Method return 154266 , should be -33618 (dixit Octave)

I was planning to use Cholesky decomposition to compute the determinant when possible, however, to check if a Matrix can be decomposed by Cholesky, you are using the determinant, so, we have an infinite loop. I Removed the call to Cholesky, and use the LUP decompostion, using that, the determinant is however correct.

For Cholesky, should we not check the determinant, but use a try catch ?

pierre-vigier commented 8 years ago

It seems that the algorithm to find the signum is working for 2,3,4 however, while testing 6 or 10, it did not work. At least temporarily, i used the permutations algorithm that is show cased on rosettacode http://rosettacode.org/wiki/Permutations_by_swapping

Also, a quick benchmark, for a 10x10 matrix: my $a = Math::Matrix.new([[96, 13, 48, 11, 35, 63, 26, 18, 44, 61], [32, 24, 30, 87, 32, 53, 31, 93, 9, 79], [31, 37, 85, 58, 9, 38, 97, 90, 29, 32], [83, 82, 0, 78, 12, 74, 35, 43, 41, 97], [48, 42, 75, 76, 45, 82, 78, 35, 96, 75], [84, 93, 89, 51, 29, 34, 71, 59, 56, 24], [27, 62, 50, 46, 44, 6, 11, 77, 40, 83], [48, 77, 28, 87, 62, 71, 44, 10, 81, 14], [75, 2, 92, 20, 8, 50, 20, 19, 69, 62], [75, 81, 32, 69, 58, 52, 74, 78, 12, 55]]); using the decomposition method, determinant is computed in 0.7046780s, result is the same as in octave: 1.57118910345124e+16 ( octave return 1.5712e+16 ) Using the naive permutation method, i stopped the program after 25 minutes without having a result

lichtkind commented 8 years ago

so choleski or the implementation of leibnitz is not right?

lichtkind commented 8 years ago

but yes if permutation is too slow we go with decomp

lichtkind commented 8 years ago

and choleski can be tested without determinant even its not a necesary criterium. as soon we have eigenvalues the cycle is broken anyway becasue we can then check if all eigenvalues are positive but them to compute i now see only iterative. they are more sophisiticated methods but i have to read into that first. also ne befor i was in library truesday.

lichtkind commented 8 years ago

allright than signum has to be more complex and i didnt testet longer permutations I have to check that

lichtkind commented 8 years ago

allright i think this is easie to fix, 1) using special knowledge, but you alread started that path 2) using the current leibnitz formula up to 5*5 which seems to work correctly 3) larger matrices we split, i found a formula to later recombine values which might also speed up the whole thing.

what do you think?

pierre-vigier commented 8 years ago

That sounds good, happy with that solution

lichtkind commented 6 years ago

allright i will work on this issue next

lichtkind commented 6 years ago

i tested and was already fixed by pierre++