Implementing the tropical semiring
luisfe
Quite a long time ago, somebody posted this
> Mon, 02 Jul 2007 10:36:10 -0700
>
> I am in need of free software that will work with polynomials over the
> Tropical semiring. I was unable to find anything suitable, so I
> thought I would take a stab at implementing them in sage. I have just
> barely found sage though, so I don't yet understand it entirely. This
> list seemed very friendly so I thought I would ask a few questions:
>
> 1. Is this already implemented under a different name (it's also
> called min-plus algebra), or someplace that I overlooked?
>
> 2. Is it reasonable to implement in sage? In particular one thing
> that I think may be difficult is that the polynomial 'x+3' is really
> '0*x+3' since 0 is the multiplicative identity (infinity is the
> additive identity).
>
> 3. Where is the best place to go to find out how to develop a sage
> package etc. Also good tutorials for python would be appreciated,
> since I have never done any python development. I do have experience
> in a variety of other languages.
>
> 4. Would this be better to implement in something like GAP (so that
> GAP users can take advantage of it as well) and then access it through
> sage?
Has anyone made some progress about this?
I have my own silly implementation of tropical polynomials over the
rationals in sage using dictionaries. And I am considering to write it
well, using Categories and Parents and a good coerce method. It should
interact and use characteristics of gfan by A. Jensen and the tropical
lib implemented in Singular by Thomas Markwig. Although the latest
uses polymake, not included in sage by default and these two programs
would be used more to pass from a polynomial ring over a valued field
to a tropical semiring.
Is there already any Category in which this structure could fit?
mhampton
I don't have time to be really actively involved but I am interested
in this functionality so feel free to include me on any tickets as
reviewer or cc: or whatever.
Marshall Hampton
Ivan Andrus
I think that was me. I know that _I_ haven't done anything on this.
As usual I was overly optimistic about how much time I had back then. :)
-Ivan
Nicolas M. Thiery
For information: in MuPAD, we had a category SemiRings, and Eric
Laugerotte had implemented a couple parents (called "domains"" in
MuPAD) in it (boolean semi ring, tropical semi ring), which were used
for calculations with weighted automatons. The implementation was
rather plain, but it was already organized using coercions,
categories, and so on. In:
http://mupad-combinat.svn.sourceforge.net/viewvc/mupad-combinat/trunk/MuPAD-Combinat/lib/DOMAINS/
Look for:
CATEGORY/SemiRing.mu
DOMAIN/BooleanSemiRing.mu
DOMAIN/MaxMinSemiRing.mu and friends MinMax, ...
DOMAINS/DOMAIN/SemiRing.mu
DOMAINS/DOMAIN/TEST/SemiRing.tst // tests and examples
The last one was the most handy: it's a generic tropical semi-ring
that was created by passing an existing parent, and what +,*,0,1 were
to be. In Sage, it could look like:
SemiRing(NonNegativeIntegers, plus = max, zero = 0, mult = operator.add, one = 0)
If you are interested, I'd happily add the SemiRing category to Sage
as soon as the category code is in (which should be very soon now;
finally!). There will be some technicalities, like how to make it easy
to add +infinity to an existing set, to disable all the preexisting
ring operations the set may already have (i.e. apply a forgetful
functor), ...
Eric: do you have references to suggest around this code, or some
design notes? Are you interested in joining on this project?
Best,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/