#16603: permanental_minor_vector, matching polynomial
-------------------------------------+-------------------------------------
Reporter: pernici | Owner:
Type: enhancement | Status: needs_work
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 | 947ddd16da731019f25a951e43bf551ad997a700
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Old description:
> ADD 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
>
> As a benchmark, consider
> http://www.jaapspies.nl/mathfiles/dancing.sage
> on my computer `dance(10)` took 3 hours using sage-6.2, 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
>
> priority: major
> type: enhancement
> component: linear algebra
New 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
--
Comment (by vdelecroix):
I rewrote the description (formatting the code).
--
Ticket URL: <http://trac.sagemath.org/ticket/16603#comment:19>
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.
