ansaurus

Question

Answer 1

A:

Octave has splu which does lu decomposition for sparse matrices. I am not sure whether it can handle 25k x 25k but worth a shot.

Alternatively if your matrix is structured like so: A = [B zeros;zeros C] then you can diagonalize B and C separately and put them together into one matrix. I am guessing you can do something similar for eig.

Anon 2010-05-27 00:25:33

Stupid question, but once I do have lu, how do I use this? I realize that det(A) = det(L)*det(U), so there must be some relationship between their diagonalizations, but I'm not smart enough to see it.

Xodarap 2010-05-27 20:22:32

Answer 2

+2 A:

Have you tried SVD, svds for sparse matrix in matlab.

EDIT: one more thing, don't do full rank SVD since the dimension is big, use a small rank, say 500, so that your solution fits in the memory. This cuts the small eigenvalues and their vectors out. Thus it does not hurt your accuracy much.

Yin Zhu 2010-05-27 00:27:40

@ A = USV'. S is a square matrix with eigenvaules on the its diagonal.

Yin Zhu 2010-05-27 00:33:23

+1 @duffymo: See wikipedia on relationship between svd and eigenvalue decomposition. In any case the OP was asking for diagonalization of A which svd does.

Anon 2010-05-27 00:37:31

I tried doing this on mine and it said "maximum variable size exceeded." My computer isn't exactly top-of-the-line though, so it could be a problem there instead of with matlab.

Xodarap 2010-05-27 00:44:37

@ Xodarap. Matlab's svds is not the best there. You could also try http://tedlab.mit.edu/~dr/SVDLIBC/. When you start, you first make sure SVD does your job by trying small matrices.

Yin Zhu 2010-05-27 00:48:23

@Yin - this is an excellent idea, but do you know how much information is lost? I feel like since this is an adjacency matrix and the rows are really quite independent of each other, finding only 10% of the eigenvalues (or whatever) will lose 90% of the info.

Xodarap 2010-05-27 21:41:50

@Xodarap. Very little. http://en.wikipedia.org/wiki/Singular_value_decomposition#Matrix_approximationYou can also do some experiments on small matrices to see the difference between approximation and the exact value.

Yin Zhu 2010-05-27 23:42:35

Answer 3

+1 A:

Have you considered the following property: exp(A*t) = L^(-1) {(sI-A)^(-1)} where L^(-1) the inverse Laplace transform? - provided that you can invert (sI-A)

gd047 2010-05-27 07:12:12

I think inverse laplace runs in O(n^4), which is very slow. It's also prone to errors. See http://www.cs.cornell.edu/cv/ResearchPDF/19ways+.pdf

Xodarap 2010-05-28 17:33:57

Answer 4

A:

In R you could check igraph package and function arpack which is interface to ARPACK library.

Marek 2010-05-28 22:21:26

Answer 5

+1 A:

If you have access to a 64 bit machine and octave compiled with 64 bit support, you might be able to get around this problem.

Also, I don't know what platform you are running all of this on, but in UNIX based systems you can use ulimit to increase the maximum allowed stack size for user processes.

For example, you can run

ulimit -u unlimited

and this will ensure that there are no memory limits etc on your processes. This is not a good idea in general, since you have have runaway processes that will completely bog down your machine. Try instead

ulimit -s [stacksize]

to increase the stack size limit.

Marcus P S 2010-06-27 02:11:05

ansaurus

tags:

views:

answers:

Tool to diagonalize large matrices

related questions