OK, thank you, I see. It's an efficient method to compute a approximation of the spectral radius. It's good but I still want to have the exact value. Maybe I can find the exact value from the approximation ?
Le mercredi 26 mars 2014 23:56:49 UTC+1, vdelecroix a écrit : > > 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 <mer...@yahoo.fr <javascript:>>: > > 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+...@googlegroups.com <javascript:>. > > To post to this group, send email to > > sage-...@googlegroups.com<javascript:>. > > > 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.
