Do you have an idea of the expecting degree of the number field in which your eigenvalue belongs to ? If yes you can use pari/GP otherwise I do not see what you mean by exact value.
2014-03-27 11:17 UTC+01:00, Paul Mercat <merc...@yahoo.fr>: > 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. > -- 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.
