#16603: permanental_minor_vector, matching polynomial
-------------------------------------+-------------------------------------
Reporter: pernici | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: Mario Pernici | Reviewers: Vincent Delecroix
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/pernici/ticket/16603 | e4359bb3d2444375eed077c72274e4f6a4ed87bc
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by pernici):
* commit: 3e7297b35f94986b8e0f37f30a3b3d6ee3d3b699 =>
e4359bb3d2444375eed077c72274e4f6a4ed87bc
Comment:
Hello,
I added the ``matching_polynomial`` method to the ``BipartiteGraph``
class, so one can optionally
use the "rook" algorithm.
Now ``rook_vector`` is much faster when the matrix is made mostly of ones.
I fixed a couple of bugs and added documentation.
A simple optimization I did not include here is the one in case of
matrices which can be put in block form
permuting rows and columns. I did not include it because it does not seem
to be a commonly occurring
case. The same optimization can be used in the computation of determinants
of large matrices of this kind.
Do you think that it is worth opening a ticket on it, or is it too obvious
and useless?
Sooner or later I will open a ticket for a faster algorithm for the
matching polynomial of graphs (non bipartite).
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=dd4636a9706689dee80d16e7e11a62763ef3fe56
dd4636a]||{{{fixed bug in ``permanental_minor_poly``;}}}||
||[http://git.sagemath.org/sage.git/commit/?id=a60cc747d5b9270e5fb3d636ebb5fdd07d2d97d9
a60cc74]||{{{added argument `complement`, eliminated argument `check` in
``rook_vector``;}}}||
||[http://git.sagemath.org/sage.git/commit/?id=e4359bb3d2444375eed077c72274e4f6a4ed87bc
e4359bb]||{{{added ``matching_polynomial`` method to ``BipartiteGraph``
class}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/16603#comment:31>
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.
