Calculate the determinant of large size square matrix

I was running on Maple 11 to calculate the determinant of large size square matrices. The matrix is sparse with floating-point entries and the size is roughly 6000*6000. Because the matrix is sparse, I set "storage=sparse" in defining the matrix, so that there is no storage problem. But when I used the command dtn:=Determinant(A, method=float) to calculate the determinant, there were the following problems:

Error, (in Matrix) Maple was unable to allocate enough memory to complete this computation.  Please see ?alloc

Error, (in LinearAlgebra:-LA_Main:-Determinant) Matrix does not evaluate to floating-point

Error, (in Matrix) not enough memory to allocate rtable

When running, Maple will give the above one or another error message. I used the command "kernelopts(datalimit)" and could see that the memory software limit is infinity. There is 4G physical memory on my computer. It gave the above error message when consuming roughly 500M memory. This is very strange and I don't know how the handle with this problem.

I am wondering whether there is a way in Maple to calculate the determinant of square matrix of size roughly 10000*10000 with floating-point entries. Thank you!

 

alec's picture

float[8]

method=float in Determinant may be not the best choice. Did you try to set datatype= float[8] in your matrix instead?

Alec

acer's picture

right

The method=float should be OK, as it should call externally if it can. The code shows that,

kernelopts(opaquemodules=false):
showstat(LinearAlgebra:-LA_Main:-`Determinant/float`);

Now, it sounds like Maple is creating too many copies of your data, along the way. Let's see how to cut that down.

Don't create your Matrix with storage=sparse, because there is only compiled C external fast routine for non-sparse storage (eg, full rectangular). So for a sparse storage Matrix Maple is going to copy it to full rectangular anyway.

And as Alec say, create it with datatype=float[8]. So that's one or two copies removed.

Each copy of a 6000x6000 float[8] Matrix will take about 36*8 MB of memory to store.

Now, Maple usually has to create at least one copy of your Matrix, so that it can do an LU decomposition on that in-place. It makes a copy so that it doesn't have to overwrite your own original data. So, it could take about 600MB or allocated memory to get the job done if you were simply to call Determinant() on a float[8] rectangular storage 6000x6000 Matrix. It sounds to me as if your machine has enough memory for that.

The rest is just for fun, in case you want to halve the memory requirement further.

If the original Matrix data is not important to you then you can do the steps yourself and act in-place on your original. That would save a copy. And the total memory use should then only be about 300MB or so. The tricky thing about doing it this way is to get the sign of the scalar result correct. Here's some code that does it on a random Matrix,

> N:= 6000;
                                   N := 6000

> with(LinearAlgebra):

> M := RandomMatrix(N,generator=-0.1..0.1,density=0.05,
>                   outputoptions=[datatype=float[8]]):
> for i from 1 to N do M[i,i]:=1.0: end do:

> # for testing only
> #origM := copy(M);
> #Digits:=trunc(evalhf(Digits)):Determinant(origM);

> P,M := LUDecomposition(M,inplace=true,output=['NAG']):

> d := proc(M::Matrix,n)
> local i,res;
>   res := 1.0:
>   for i from 1 to n do
>     res := res*M[i,i];
>   end do;
> end proc:

> evalhf(d(M,N));
                              9.68585766336265408
 
> quit
memory used=277.3MB, alloc=276.8MB, time=62.88

As I mentioned, getting the sign correct need a little more work. It can be done by walking through the permutation Vector P created above. I don't have time at the moment to figure out code for that, but someone may find it an amusing exercise. It's in the format of parameter IPIV of CLAPACK routine dgetrf.

Can anyone think of a way to get the determinant efficiently from sparse float[8] Matrix by doing a LinearSolve? I mention it because there is a sparse linear solver, whose use would not require copying to full rectangular storage.

acer

Robert Israel's picture

output

Why not use output=['determinant']?  That way the external NAG routine does all the work.  Thus:

determinant := LUDecomposition(M, inplace=true,output=['determinant']);

 

acer's picture

I forgot

I forgot about that. Brilliant. Thanks, Robert.

It does pretty much exactly what my code above does. (Like my code, it too overwrites the orginal Matrix with the superimposed L and U factors.) And so determinant of a 6000x6000 nonsparse float[8] takes 280MB -- pretty much the memory only to hold the Matrix itself.

So the original poster could just ensure that the Matrix is created with datatype=float[8], and not with storage=sparse, and then do your LUDecomposition call above.

acer

One more question

Dear Alec and Acer, thank you very much for you comments and detail explanations. Now there is still one more question: Since there is 4G physical memory on my machine, why Maple terminates when consuming only roughly 500M memory, which seems to be due to memory limitations.

Error, (in Matrix) not enough memory to allocate rtable

Error, (in Matrix) Maple was unable to allocate enough memory to complete this computation.  Please see ?alloc

But "kernelopts(datalimit)" shows that there is no limitation on the memory consuming. How can I use more memory, say 1.5G, so that I can handle even larger size matrices. Thank you very much!!

 

acer's picture

platform

I do not know why there may be a memory restriction on your machine. What operating system is it?

acer

platform

The operating system is Windows Server 2003 Stardard Edition. Thank you!

acer's picture

platform

You may want to contact support@maplesoft.com

Without seeing the actual code it's difficult to tell whether it is exiting due to some limit near 500MB, or whether it is sitting at 500MB and failing to further allocate memory way past 2GB for some new rtable object. I would guess the latter, but without seeing the code cannot tell how it maybe made to work.

You might also consider uploadind your code to this site using the green up-arrow to access the site's FileManager.

acer

OK

Thank you, acer. I restarted the whole computer system and now it seems that no such memory restriction problem any more. Thank you for your advice!

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}