calculating determinant for matrix

[fuzzy wozzy]

instead of upper/lower triangle method, recursion was used, short and compact but not very functional,
7x7 matrix takes 35 seconds, 11x11 takes 5 minutes, 15x15 is taking well over and hour and still going,
main function calls the helper function and the helper function calls the main function, so it must be
a deep recursion going on and maybe that's not a good thing, still, can't explain such drastic time difference.

[Antti Ylikoski]

https://en.wikipedia.org/wiki/Determinant#Calculation

With the naive method, the complexity of the computation of the determinant of an n x n matrix is n! ie. n factorial!

What is the complexity of computation of your recursion method?

This only shows how valuable it is to know theoretical computer science!

yours, AJY

Helsinki, Finland

[Willi Riha]

Your efforts are very commendable.  You obviously have heard of LU-factorisation, but it appears that you are not using it,

in preference of some kind of recursive method.

A few months ago, I got interested again in "Linear Algebra" and I translated vector and matrix operations into Shen..

I also implemented Gaussian elimination, with and without pivoting, LU-factorisation, matrix inversion etc. 

I had not written a function to work out the determinant of a matrix, as this is trivial,  when you have the the LU- factorisation.

You just need to multiply the diagonal elements of U. Because I have not looked at my matrix programs for over two months,

and Shen has slightly changed, I had a problem compiling my existing files.

Mark and I managed to do it eventually.

I still cannot work out determinants, because it is late, and I cannot think straight. 

I know that solving a system of n linear equations is slightly more expensive that factorising an nxn matrix, which is equivalent to 

working out the determinant..

On my slower PC it takes much less than 1 sec to factorise a 100 x 100 matrix, 

and not much more than  1.5 secs to factorise a 250 x 250 matrix.

For a 15 x 15 matrix the time recorded is 0.0 sec

Fuzzy, why don't you abandon your efforts in this respect.

I suggest that you do some work on the Riemann conjecture, which is one of the most .interesting unsolved mathematical

problems (as is Goldbach's conjecture). There is a lot you could do, that has not been attempted before!

Good luck

Willi

[fuzzy wozzy]

this is just laplace formula with recursion, so there isn't much algorithm to speak of,
the main function is basically a one-liner, other than an answer line and error line,
to apply the "+" or "-" in a flip-flop fashion,

a reviewer on amazon for programming pearls book by jon bentley mentioned how the book
showed the upper/lower triangular form could speed up the determinant method; 15x15 matrix could be
done in under a minute whereas before 7x7 took 7 minutes with recursion, so doing it in shen
makesthe upper/lower triangle method even faster, it seems,

the review was less than a year ago so the computing power is probably the same, then and now.

250x250 in 1.5 seconds is quite an impressive time, what's the industry standard for something like this?
what matrix size and what calculation time are expected?

upper/lower triangle method sometimes gives answers in decimal point numbers, would it be preferably to
have the answer in a fraction format, as in a/b? it's weird to see the fractional numbers as answers even
when all the elements in a matrix are integers, maybe the way to speed up the calculation with recursion
is to reverse the process, because when you know what the value of 14x14 matrix is, then finding 15x15 is
much faster than applying recursion all the way to the smallest matrix

[fuzzy wozzy]

given laplace formula for a determinant,

     ( a x det1) - (b x det2) + (c x det3) - ...

recursion is applied to det1, det2, det3.

of course this would be time-consuming,
but what was surprising was how it took
less than 5 seconds for up to 9x9 matrix,
then suddenly it jumped to 5 minutes and
then an hour, for the smallest increase in size.