[sage-devel] Re: sparse linear algebra in sage
A long time ago I did numerical eigenvalue computations using
SLEPC ( see http://www.grycap.upv.es/slepc/ )
There is also Trilinos/Anazazi (I did't use it)
But I was only interested in a part of the spectrum (smallest /largest),
Do you need to compute all eigenvalues?
Maybe (as William said) you should look for available software.
I know about the following existing survey:
http://www.grycap.upv.es/slepc/documentation/reports/str6.pdf
Jakob
Am Samstag, 13. September 2014 20:53:50 UTC+2 schrieb wstein:
On Sat, Sep 13, 2014 at 11:28 AM, Erik Slivken
wrote:
William-
I am trying to find the eigenvalues of a roughly 1x1 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 1x1
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.)
William
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
wst...@uw.edu javascript:
--
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 sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: sparse linear algebra in sage
On Sat, Sep 13, 2014 at 11:52 AM, William A Stein wst...@uw.edu wrote:
On Sat, Sep 13, 2014 at 11:28 AM, Erik Slivken
wrote:
William-
I am trying to find the eigenvalues of a roughly 1x1 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 1x1
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.
William
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
wst...@uw.edu
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
wst...@uw.edu
--
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 sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: sparse linear algebra in sage
On 2014-09-13, William A Stein wst...@uw.edu wrote:
On Sat, Sep 13, 2014 at 11:52 AM, William A Stein wst...@uw.edu wrote:
On Sat, Sep 13, 2014 at 11:28 AM, Erik Slivken
wrote:
William-
I am trying to find the eigenvalues of a roughly 1x1 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 1x1
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
wst...@uw.edu
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
wst...@uw.edu
--
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 sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: sparse linear algebra in sage
On Saturday, September 13, 2014 9:26:33 PM UTC+1, Dima Pasechnik wrote: (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) Depends of course on how many ones there are ;-) -- 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 sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
