IIRC, the bottleneck to computing the spectra of large graphs is in the construction of the adjacency matrix. I don't know why.
On Wed, Mar 26, 2014 at 3:28 PM, Paul Mercat <merc...@yahoo.fr> wrote: > Le mercredi 26 mars 2014 22:56:46 UTC+1, Dima Pasechnik a écrit : >> >> On 2014-03-26, Paul Mercat <mer...@yahoo.fr> wrote: >> > >> > >> > Le mercredi 26 mars 2014 20:48:32 UTC+1, Dima Pasechnik a écrit : >> >> >> >> On 2014-03-26, Paul Mercat <mer...@yahoo.fr <javascript:>> wrote: >> >> > I need to compute charpoly of big sparse matrices obtained in sage, >> >> > but >> >> > there is no efficient algorithm in sage for the moment. >> >> > So I would like to implement it and add it to sage. >> >> > I think it already exists in gp or in linbox, but I was not able to >> >> > use >> >> it >> >> > in sage. >> >> > Maybe sage has no proper way to convert a sparse matrix to give it to >> >> > gp >> >> or >> >> > to linbox ? >> >> > Does somebody knows how to do that ? >> >> >> >> what kind of field are your matrices defined over? >> >> >> >> >> >> >> > I have matrices with non negative integers. >> > Is there a efficient way to get the exact Perron-Frobenius spectral >> > radius >> > of these sparse matrices in sage ? >> >> Do I understand you right that you are talking about a generalisation of >> the usual Perron-Frobenius for matrices with positive entries? >> >> Do you really need to now the whole exact characteristic polynomial? >> This looks like an overkill, and won't possibly work for big matrices >> (if by "big" you mean something like 1000x1000 or more...) >> IMHO, at least in the case of irreducible matrices, >> one computes the dominant eigenvector by the power method, and from it >> one can find (an approximation of) the maximal eigenvalue. >> >> > > Thank you for your answer. > I'm talking about usual Perron-Frobenius. In fact my matrices are adjacency > matrices of graphs. > By "big", I mean that my matrices can be of size more than 1000x1000 and > sometimes even more than 50000x50000 (I have even bigger matrices, but the > more I can compute, the happier I will be !). > It is not difficult to reduce the problem to the case of irreducible > matrices. > > I don't think that it's a good idea to compute power of the matrix, because > it will increase a lot the number of coefficients, and therefore it will > consume too much memory. > For example, I have a 65135 x 65135 matrix with 130207 coefficients equals > to 1 and the others one are nulls. > I remember that I was able to compute efficiently large determinants (and so > characteristic polynomials) of large sparse matrices using pari/gp, but it > don't work with sage, because when I try to execute a pari/gp function to my > sage matrix, it take immediately too much memory (I think that sage convert > the matrix to a dense one when it give it to pari/gp). > I would like to have the exact value (i.e. its minimal polynomial) of the > spectral radius. > > -- > 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. -- 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.
