On 2014-09-13, William A Stein <[email protected]> wrote: > On Sat, Sep 13, 2014 at 11:52 AM, William A Stein <[email protected]> wrote: >> On Sat, Sep 13, 2014 at 11:28 AM, Erik Slivken >> <> wrote: >>> William- >>> >>> I am trying to find the eigenvalues of a roughly 10000x10000 sparse matrix >>> with entries from {0,1} (and would like to do this for even larger >>> matrices). I don't know what could be done to increase the speed (right now >>> it has been running for roughly half a day). But it said to email you to >>> raise a quota. Also, if there is special faculty access, this is a project >>> with Chris Hoffman from UW and I am sure he would sign on for more computing >>> power. >>> >>> Thanks for your time. >>> >>> Cheers, >>> Erik Slivken >>> >>> P.S. How long should it take to find the eigenvalues of a 10000x10000 >>> sparse matrix with entries from {0,1}? What about a 10^6x10^6 sparse matrix >>> with entries in from {0,1}? >> >> Never. Sage doesn't have any easily available sophisticated sparse >> linear algebra algorithms, as far as I know. Linbox (which is in Sage >> -- a C++ library), might have something; and Cremona's eclib has some >> gems hidden in it. I wrote some really stupid sparse linear algebra, >> which was sufficient for something I did once. There's several >> stages to sparse algorithms, and what is in Sage only implements the >> first part -- the "endgame", which is to solve a resulting dense >> system at a certain point, isn't in sage. Sebastian Pancratz and I >> did implement it once >> somewhere... (not sure), but it isn't in sage (and it was not easy), >> and now Sebastian works at a bank. >> >> Try typing >> >> set_verbose(2) >> >> to see what is happening, if you're using sage. >> >> You should seriously consider searching the web for current available >> software for sparse linear algebra. Last I checked, unfortunately, >> Sage is definitely not an off-the-shelf solution for anything >> nontrivial involving sparse matrices, except for maybe efficiently >> storing them. >> >> (I've changed the subject and cc'd some people on this email, in case >> anybody knows anything about sparse linear algebra and wants to chime >> in.) > > He adds "Also, I only need the largest eigenvalue, if that makes it easier." the largest eigenvalue of a nonnegative matrix is a completely different story. It is a convex optimisation problem, and can be solved efficiently for huge matrices. Assuming the underlying (di)graph is connected (such matrices are called irreducible), one has http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Perron.E2.80.93Frobenius_theorem_for_irreducible_matrices
to compute this eigenvalue, one can use "power method", or "trust region method", etc, there is a lot of literature on this stuff. (of course it's out of the question to compute the eigenvalues of an arbitrary 0-1 sparse matrix of that kind of size, so one really has to go for the largest one) HTH, Dima > >> >> William >> >> -- >> William Stein >> Professor of Mathematics >> University of Washington >> http://wstein.org >> [email protected] > > > > -- > William Stein > Professor of Mathematics > University of Washington > http://wstein.org > [email protected] > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
