On Fri, Nov 06, 2009 at 12:52:09PM -0800, luisfe wrote: > 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?
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" <nthi...@users.sf.net> http://Nicolas.Thiery.name/ --~--~---------~--~----~------------~-------~--~----~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
