No, I have no idea of what will be the degree of the number field in which my spectral radius belongs to. But if I could compute the characteristic polynomial of the matrix, I could have the minimal polynomial of the spectral radius (and that's what I mean by exact value).
Le jeudi 27 mars 2014 12:33:17 UTC+1, vdelecroix a écrit : > > 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 <mer...@yahoo.fr <javascript:>>: > > 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+...@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.
