Consider the following program
sage: G = graphs.OddGraph(4)
sage: G.spanning_trees_count()
336140000000000000
It takes approximately 8 minutes to compute the number of spanning trees using
this method. However, the number of spanning trees can be computed directly
from the charpoly of the respective Kirchhoff matrix
sage: (G.kirchhoff_matrix()).charpoly().coeffs()[1]/35
336140000000000000
which takes an instant (less than a second) to compute.
Looking at the way spanning_trees_count is implemented within generic_graph.py,
one can see:
M=self.kirchhoff_matrix()
M.subdivide(1,1)
M2 = M.subdivision(1,1)
return abs(M2.determinant()) # <-The abs() here is redundant someone
should remove it
To speed the computation one can pass the parameter algorithm='padic' to the
determinant() method and get the result of spanning_trees_count() instantly.
That said, I am wondering if this is perhaps a bug in the default
implementation of determinant()? It seems strange to me that it takes 8 minutes
to compute a determinant of a 34x34 matrix while other algorithms do it within
a second.
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
