#16603: permanental_minor_vector, matching polynomial
-------------------------------------+-------------------------------------
Reporter: pernici | Owner:
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-6.4
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: Mario Pernici | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/pernici/ticket/16603 | 19350a4574f4caa2e0b5ad08f66e51930b647a42
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by pernici:
Old description:
> Added function `permanental_minor_vector`, which computes the polynomial
> of the sums of the permanental minors in an efficient way, see
> [http://arxiv.org/abs/1406.5337 arXiv:1406.5337].
>
> As a benchmark, consider [http://www.jaapspies.nl/mathfiles/dancing.sage
> dancing.sage]. On my computer `dance(10)` took 3 hours using sage-6.2 and
> 0.08 seconds with this patch!
>
> In the case of banded matrices, the speedup is greater, since for fixed
> bandwidth the new algorithm is polynomial; here is a permanent which
> cannot be computed with sage-6.2
>
> {{{
> sage: from sage.matrix.matrix_misc import permanental_minor_vector
> sage: n, w = 100, 5
> sage: m = matrix([[i*j + 1 if abs(i-j) <= w else 0
> ....: for i in range(n)] for j in range(n)])
> sage: time p = permanental_minor_vector(m, 1)
> CPU times: user 1.11 s, sys: 20 ms, total: 1.13 s
> Wall time: 1.07 s
> }}}
>
> This can be used to compute the matching polynomial of bipartite graphs
> much faster than matching_polynomial for certain graphs. For example,
> using the attached file to compute the reduced adjacency matrix of a 2d
> grid (n1, n2):
> {{{
> sage: from grid import sq_mat
> sage: from sage.matrix.matrix_misc import permanental_minor_vector
> sage: m = matrix(sq_mat(6, 6))
> sage: time a = permanental_minor_vector(m)
> Wall time: 16.3 ms
>
> sage: g = BipartiteGraph(m)
> sage: time p = g.matching_polynomial()
> Wall time: 52 s
> }}}
> For n1,n2=10,10 permanental_minor_vector(m) takes 0.7s
> For n1,n2=50,6 it takes 0.8s
New description:
Added function `permanental_minor_polynomial`, which computes the
polynomial of the sums of the permanental minors in an efficient way, see
[http://arxiv.org/abs/1406.5337 arXiv:1406.5337].
As a benchmark, consider [http://www.jaapspies.nl/mathfiles/dancing.sage
dancing.sage]. On my computer `dance(10)` took 3 hours using sage-6.2; it
takes 0.08 seconds with this patch, using the
"ButeraPernici" algorithm, 13 seconds using the Godsil algorithm.
In the case of banded matrices, the speedup is greater, since for fixed
bandwidth the new algorithm is polynomial; here is a permanent which
cannot be computed with sage-6.2
{{{
sage: from sage.matrix.matrix_misc import permanental_minor_polynomial
sage: n, w = 100, 5
sage: m = matrix([[i*j + 1 if abs(i-j) <= w else 0
....: for i in range(n)] for j in range(n)])
sage: time p = permanental_minor_polynomial(m, permanent_only=True)
Wall time: 773 ms
}}}
This can be used to compute the matching polynomial of bipartite graphs
much faster than matching_polynomial for certain graphs. For example,
using the attached file to compute the reduced adjacency matrix of a 2d
grid (n1, n2):
{{{
sage: from grid import sq_mat
sage: from sage.matrix.matrix_misc import permanental_minor_polynomial
sage: m = matrix(sq_mat(6, 6))
sage: time a = permanental_minor_polynomial(m)
Wall time: 10.6 ms
sage: g = BipartiteGraph(m)
sage: time p = g.matching_polynomial()
Wall time: 46.9 s
}}}
For n1,n2=10,10 permanental_minor_vector(m) takes 0.3s
For n1,n2=50,6 it takes 0.5s
--
--
Ticket URL: <http://trac.sagemath.org/ticket/16603#comment:25>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
