#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_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
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
Butera-Pernici 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:27>
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.
