[sage-devel] Re: Implementing the tropical semiring
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 -~--~~~~--~~--~--~---
[sage-devel] Re: Implementing the tropical semiring
On Nov 6, 2009, at 9:52 PM, luisfe wrote: Hi, 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 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 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[sage-devel] Re: Implementing the Tropical Semiring
On 7/2/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: 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? Not to my knowledge. 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). Can you describe in more detail what you need to implement? 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. Section 3 of the Programming Guide http://www.sagemath.org/documentation.html is a good place to start. There are also links to two good (and free) Python tutorials on the above webpage. I personally like Beasley's Python reference manual, but each person has their favorites. 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? I am very pro-GAP but I think SAGE has a better development environment, partially due to that fact that Python is more flexible than the GAP language, and the fact that William Stein has thought carefully about implementing good programming development tools. Thanks for your comments, Ivan Andrus -- MacMail - the Webmail service especially for Mac users worldwide http://www.macmail.com --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Implementing the Tropical Semiring
On Jul 3, 2007, at 2:06 AM, [EMAIL PROTECTED] wrote: 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. This would be really really cool. There was some discussion a while ago about arithmetic with polynomials over p-adic rings, and it turns out that computing the precision information in the product (long story) is exactly equivalent to doing efficient multiplication of polynomials over the tropical semiring. Having an efficient implementation of such arithmetic in SAGE would make me very happy. 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). The first problem in my mind is that currently SAGE doesn't have an appropriate base class for the semiring itself (let alone the polynomials). We are pretty heavily biased towards commutative algebra and linear algebra currently. If you look at the main sage directory, you'll see the main arithmetic parents implemented are currently algebras, groups, matrix, modules, monoids, rings. I would propose adding a new directory semirings, and a new class Semiring that derives possibly from ParentWithGens. Then the specific semirings you have in mind (the tropical one, polynomials over that, etc) would be subclasses. (Caveat: I know very little about semirings, so perhaps what I'm saying above doesn't make a whole lot of sense, in which case it should be ignored.) david --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Implementing the Tropical Semiring
I have some interest in such an implementation, although more as a user of it than an architect/developer. I would encourage you to do it in sage and not GAP. I can at least commit to help testing any code you work on. There might be some helpful overlap with Anders Jensen's gfan program, which already has a partial interface to sage written. Gfan is capable of some tropical computations, although I am not sure exactly what is externally callable. If you are unfamiliar with gfan, perhaps a good place to start is: http://arxiv.org/abs/math/0507563 Cheers, Marshall Hampton On Jul 2, 10:06 am, [EMAIL PROTECTED] wrote: 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? Thanks for your comments, Ivan Andrus -- MacMail - the Webmail service especially for Mac users worldwidehttp://www.macmail.com --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
