#13503: Enhancement of `is_triangle_free' addition of `triangles_count' and a
minor
change in `spanning_trees_count'
----------------------------------------------------------+-----------------
Reporter: azi | Owner:
jason, ncohen, rlm
Type: enhancement | Status:
needs_work
Priority: minor | Milestone:
sage-5.4
Component: graph theory | Resolution:
Keywords: triangles, graphs, number of triangles | Work issues:
Report Upstream: N/A | Reviewers:
David Coudert
Authors: Jernej Azarija | Merged in:
Dependencies: | Stopgaps:
----------------------------------------------------------+-----------------
Comment (by dcoudert):
I'm certainly not used to matrix multiplications and rings in sage, and
I'm surprised that computing with doubles is faster than with integer. For
instance, if G has {{{10^6}}} vertices, then since M is a matrix of 0 and
1's, the largest value in {{{M^3}}} is in {{{10^18 < 2^63}}} and so all
computations are doable using 64bits integers.
Following your example, and after some search, I found a much faster
solution: use GF(2)
{{{
sage: G = graphs.CompleteBipartiteGraph(100,100); M = G.am(); M
200 x 200 dense matrix over Integer Ring (type 'print M.str()' to see all
of the entries)
sage: %timeit not (M*M*M).trace()
5 loops, best of 3: 39.5 ms per loop
sage: MR = M.change_ring(RDF); MR
200 x 200 dense matrix over Real Double Field (type 'print MR.str()' to
see all of the entries)
sage: %timeit (MR*MR*MR).trace() == 0.0
125 loops, best of 3: 1.47 ms per loop
sage: M2 = M.change_ring(GF(2)); M2
200 x 200 dense matrix over Finite Field of size 2 (type 'print M2.str()'
to see all of the entries)
sage: %timeit not (M2*M2*M2).trace()
625 loops, best of 3: 201 µs per loop
}}}
However, this is not always the best solution and it is extremely slow for
sparse matrix O_o
{{{
sage: G = graphs.RandomGNP(1000,.1); M = G.am(); M2 =
M.change_ring(GF(2)); M2
1000 x 1000 dense matrix over Finite Field of size 2 (type 'print
M2.str()' to see all of the entries)
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 424 µs per loop
sage: %timeit not (M2*M2*M2).trace()
125 loops, best of 3: 4.09 ms per loop
sage: MR = M.change_ring(RDF)
sage: %timeit (MR*MR*MR).trace() == 0.0
5 loops, best of 3: 96.9 ms per loop
sage:
sage: G = graphs.RandomGNP(1000,.01); M = G.am(); M2 =
M.change_ring(GF(2)); M2
1000 x 1000 sparse matrix over Finite Field of size 2 (type 'print
M2.str()' to see all of the entries)
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 594 µs per loop
sage: %timeit not (M2*M2*M2).trace()
5 loops, best of 3: 3.41 s per loop
sage: MR = M.change_ring(RDF)
5 loops, best of 3: 8.08 s per loop
sage:
sage: G = graphs.RandomGNP(100,.01); M = G.am(); M2 =
M.change_ring(GF(2)); M2
100 x 100 dense matrix over Finite Field of size 2 (type 'print M2.str()'
to see all of the entries)
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 1.22 ms per loop
sage: %timeit not (M2*M2*M2).trace()
625 loops, best of 3: 95.7 µs per loop
sage:
sage: G = graphs.RandomGNP(100,.1); M = G.am(); M2 = M.change_ring(GF(2));
M2
100 x 100 dense matrix over Finite Field of size 2 (type 'print M2.str()'
to see all of the entries)
sage: %timeit my_is_triangle_free(G)
625 loops, best of 3: 71.4 µs per loop
sage: %timeit not (M2*M2*M2).trace()
625 loops, best of 3: 95.5 µs per loop
}}}
I don't know how to force a matrix to be dense. for "small" graphs, it is
apparently always dense.
Clearly, the algorithm should use tradeoffs between size and density.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13503#comment:16>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
