Strange performance (bug?) computing a specific determinant | Jernej Azarija | 06/09/12 05:12 | Consider the following program sage: G = graphs.OddGraph(4) 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 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() 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. |

Re: [sage-devel] Strange performance (bug?) computing a specific determinant | D. S. McNeil | 06/09/12 08:03 | > That said, I am wondering if this is perhaps a bug in the default implementation of determinant()?Yeah, it looks like pari's Gauss-Bareiss takes forever on this matrix, even though its classical Gaussian is quick: sage: time m2._det_pari(1) 336140000000000000 Time: CPU 0.00 s, Wall: 0.00 s sage: time m2._det_pari(0) 336140000000000000 Time: CPU 597.13 s, Wall: 597.10 s Kind of funny: _det_pari(0) is so slow on this particular matrix that it's five orders of magnitude faster to square m2 and take the root of the determinant! sage: %timeit (m2)._det_pari(1) 125 loops, best of 3: 3.39 ms per loop sage: %timeit (m2*m2)._det_pari(0)^(1/2) 125 loops, best of 3: 5.92 ms per loop Doug |

Re: [sage-devel] Strange performance (bug?) computing a specific determinant | Jernej Azarija | 06/09/12 14:03 | Interesting! I have also noticed that if I just slightly modify the matrix m2, it again works efficiently. Will someone direct the pariGP guys to this issue? |

Re: Strange performance (bug?) computing a specific determinant | Jernej Azarija | 02/01/13 09:11 | Hello! Has anyone already looked into this thing? The bug appears to slow down all matrix computations related to pariGP. For example it gets stuck computing the eigenvalues of a matrix as well. It's quite annoying. The pariGP guys confirmed it's a bug in pari so we should update the pari package that sage ships! Best, Jernej |

Re: [sage-devel] Re: Strange performance (bug?) computing a specific determinant | Jeroen Demeyer | 03/01/13 03:23 | On 2013-01-02 18:11, Jernej Azarija wrote:If you create a Sage ticket for this issue, pointing to the PARI/GP bug report and cc: me, I'll happily apply the fix. |

Re: [sage-devel] Re: Strange performance (bug?) computing a specific determinant | Jeroen Demeyer | 03/01/13 05:38 | I backported an upstream patch for this and made a new PARI spkg, needs
review at http://trac.sagemath.org/sage_trac/ticket/13902 |