#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 | f511623cce7bde7f022fa212a505526b3b62f0db
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Hello,
I will push several commits in a minute on my branch `u/vdelecroix/16603`.
Again you are free to use/discuss/reject them. I discuss the most
important changes below.
Change in your original code and documentation:
- I changed your initial function into `permanental_minor_polynomial`. It
looks more natural as it is what you compute... I moved the part of the
code that makes it a list in `matrix.rook_vector`
- I added a keyword `var` (as it is the case for `matrix.charpoly` for
example) and change the argument name from `m` to `A` (since A is used in
the docstring)
- I optimized a bit the method `prm_mul` (it was possible to remove the
loop computing `exp`) and introduced the list `vars_to_do` inplace of the
set `done_vars`.
- Sometimes it might happen that some coefficient of the partial product
become zero. I added a test in `prm_mul`. If you think this is not worth
it, I can revert that change.
- Again, I edited a lot the documentation of
`permanental_minor_polynomial`. Please reread carefully, I tried to make
it more understandable but I might have made many mistakes.
- Do you know an adaptation of your method to compute only a specific
permanental minor? (I guess that to compute the `k`-th permanental minor
it is just enough to ignore the terms `t^l^` with `l > k`)
Methods of matrices:
- does your algorithm have a name? I used Butera-Pernici (see the item
just below, it has some importance).
- To allow the computation using your algorith, I made changes in
`matrix.permanental_minor` and `matrix.permanent`. After my commits you
can do
{{{
sage: m = matrix(ZZ,4,4,range(16))
sage: m.permanent(algorithm="Ryser")
22432
sage: m.permanent(algorithm="ButeraPernici")
22432
}}}
it will be easier to make benchmarks (but I repeat that right now it is
not fair for both, see also #17457).
- Right now, in all methods except `matrix.rook_vector`, the default
choice for algorithm is Ryser (what was before). Where do you think we
should put yours in first?
- why `matrix.rook_vector` is only defined for {0,1} matrices... it is
well defined for any matrix, isn't it?
- possibly we can add a method `matrix.permanental_minor_polynomial` but
it will overlap a lot with rook vector. I am not sure what to do as these
methods are very specific to matrix combinatorics. Perhaps you have a
better overview than me on that.
Despite this big list of remarks, I am sure this is not far for being
ready for integration! This is a really nice piece of work.
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/16603#comment:21>
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.
