Strange performance (bug?) computing a specific determinant

Showing 1-6 of 6 messages
Strange performance (bug?) computing a specific determinant Jernej Azarija 06/09/12 05:12
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.

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()?
> 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.

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:
> The pariGP guys confirmed it's a bug in pari so we should update the
> pari package that sage ships!
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