|Strange performance (bug?) computing a specific determinant||Jernej Azarija||9/6/12 5:12 AM|
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
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:
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||9/6/12 8:03 AM|
> 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)
Time: CPU 0.00 s, Wall: 0.00 s
sage: time m2._det_pari(0)
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
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
|Re: [sage-devel] Strange performance (bug?) computing a specific determinant||Jernej Azarija||9/6/12 2:03 PM|
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||1/2/13 9:11 AM|
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!
|Re: [sage-devel] Re: Strange performance (bug?) computing a specific determinant||Jeroen Demeyer||1/3/13 3:23 AM|
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||1/3/13 5:38 AM|
I backported an upstream patch for this and made a new PARI spkg, needs
review at http://trac.sagemath.org/sage_trac/ticket/13902