I would like to built a code to find thedeterminant of a 24×24 matrix.I dont want to use the det(X) function,but a fuction that would be quick.
The one i created,whick is too slow for that.
Best Answer
NO NO NO!!!!!
First, you should not be using the determinant here. I don't know why you think you need to use it. But if you don't understand how to efficiently compute a determinant, the probability is 1 that you should not be using the determinant in the first place. There are far better tools to determine is amatrix issingular, which is why you are surely wanting to compute the determinant of a 24x24 matrix.
Ok, why is the code you wrote a an obscenely bad one? Do you understand that the code you wrote will require O(factorial(24)) computations to execute?
factorial(24)
ans =
6.20448401733239e+23
Even the largest supercomputer the NSA owns would grind to a miserable halt.
So, CAN you compute the determinant more efficiently? Well, yes. USE DET! (In fact there are ways to compute the determinant efficiently. But since you should not be using it in the first place, I won't go into details.)
So better yet, don't compute the determianant at all. So instead, you need to learn how to use tools like rank, cond or svd to do what you are trying to do. Of course, we don't really yet know what you are doing.
You can define anything you want to be sparse if you so desire. So sparse(ones(1000)) will produce a sparse matrix. ;-)
But seriously, this matrix really is reasonably sparse. Just read what is shown on the page you direct to!
We see that it is shown to be an 1899x1899 square matrix. There are 20296 non-zeros in the matrix.
20296/1899
ans =
10.688
So on average, roughly 10.7 non-zeros per row of a matrix, where each row has 1899 elements.
20296/1899/1899
ans =
0.0056281
Total density of around 0.6% non-zeros. Is that matrix sparse? Well, yes, it is. Not massively so, but it is sparse. Since I don't have that matrix, I'll do a little memory comparison on a random one with the same density.
As = sprand(1899,1899,0.0056);
Af = full(As);
whos As Af
Name SizeBytesClassAttributes
Af 1899x189928849608double
As 1899x1899337568doublesparse
So we see that storing the matrix as sparse gives me a decrese in memory of almost a factor of 100-1. (Sparse matrix storage also requires we store the location of those elements, so it is not quite as efficient as we might like.)
b = rand(1899,1);
timeit(@() Af*b)
ans =
0.0023482
timeit(@() As*b)
ans =
6.1858e-05
And working with the matrix with a matrix multiply does give a significant savings.
Much of the time, when you work with a sparse matrix, you will perform a decomposition of some sort. Odds are that will not produce a speed increase here, because the matrix itself is not a nicely tightly banded matrix. I think much of the time, people think of a sparse matrix in the form of something like a tridiagonal matrix. A matrix factorization of a tridiagonal matrix will produce no fill-in at all. On the matrix you show, if we tried to do a Cholesky or LU factoriation, for example, the result will be a virtually completely full triangular matrix.
tic,[L,U] = lu(Af);toc
Elapsed time is 0.205769 seconds.
tic,[L,U] = lu(As);toc
Elapsed time is 3.032499 seconds.
As you see, not all computations on such a matrix will see a gain in speed. Here, we see the result ends up as a nearly full triangular matrix for the factors. So treating that matrix as sparse, IF you intend to do a decomposition of the matrix will be a time loss, because the overhead from the sparse algorithms is too costly.
nnz(L)
ans =
1177842
nnz(U)
ans =
1208969
numel(L)
ans =
3606201
That is to be expected on this matrix. It does not mean the original was not sparse. It is indeed sparse. Just perhaps not as massively sparse as you may want a matrix to be. Sometimes sparse must be measured by the eye of the beholder, in proper context.
1. NEVER use the matrix determinant for any computation to determine the rank of a matrix. (Use rank or cond for that.)
1a. Never use the matrix determinant for any computation, unless you understand enough about mathematics and numerical linear algebra to know why you should virtually never use the determinant, and when it might be ok.
2. Learn about floating point arithmetic, and understand why you should never trust those bits down at the LSB level. A number on the order of 1e-16 is exactly that. It is zero in double precision arithmetic.
3. You cannot "fix" the problem you perceive, except by learning {1,1a,2} from above. Yes,you can use symbolic tools to compute an "exact" value for the determinant. But they will be EXTREMELY slow for such a result, especially as the matrix size goes only slightly higher.
Yes, it is true that you were taught in some basic math class about the determinant of a matrix. Sadly, the person who taught you was wrong, in that either they did not understand the above, or they forgot to teach you those facts at the same time as they taught you about the determinant. Sadly, many teachers only know what they see in a book, and what they themselves were taught. So these memes propagate. In this case, the meme is that you can use the determinant.
Best Answer