You compute powers but *not* of the matrix itself ! You just compute iteration of a single vector. Here is a rough implementation of what you should do
sage: A = matrix([[1,2,3],[1,1,1],[1,0,1]]) sage: s = 0. sage: v = random_vector(RDF,3) sage: v /= v.norm() sage: for i in xrange(100): ....: v = A*v ....: n = v.norm() ....: s += log(n) ....: v /= n sage: exp(s/100) 3.41421356237309 sage: A.eigenvalues() [-1, 0.5857864376269049?, 3.414213562373095?] 2014-03-26 23:28 UTC+01:00, Paul Mercat <merc...@yahoo.fr>: > Le mercredi 26 mars 2014 22:56:46 UTC+1, Dima Pasechnik a écrit : >> >> On 2014-03-26, Paul Mercat <mer...@yahoo.fr <javascript:>> 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.
