Implement the tropical semiring

tscrim commented 11 years ago

Apply:

attachment: trac_14507-tropical_semiring-ts.patch

CC: @darijgr

Component: algebra

Keywords: tropical geometry semiring days49

Author: Travis Scrimshaw

Reviewer: Vincent Delecroix, Darij Grinberg

Merged: sage-5.12.beta0

Issue created by migration from https://trac.sagemath.org/ticket/14507

videlec commented 11 years ago

comment:2

1) Design

the min-plus convention is standard ? I thought it was max-plus. I think that it might be an option of the ring to chose between min and max.
Why did you choose to base it on real fields ? It seems more like a wrapper that call + and max (or min) appropriately. What if I want tropical integers ? Tropical real intervals ? (note: I do want those).
It would be better to call x.min(y) (optimized mpfr stuff) instead of min(x,y) (Python generic stuff)
For sake of optimization you should implement a cdef _new method that duplicate the object instead of calling self.__class__(my_parent, my_new_value). It is the way it is for most cythonized elements.

2) Documentation the file is not included in the documentation. Moreover it might be nice to have more examples in the headers of the file (with a link to :wikipedia:Tropical_geometry... actually it might be a good idea to rewrite the wikipedia article ;-)

3) Question Do you know how I can build a tropical matrix ?

videlec commented 11 years ago

Work Issues: documentation, design

videlec commented 11 years ago

Reviewer: Vincent Delecroix

tscrim commented 11 years ago

comment:3

Hey Vincent,

Thanks for the review. According to the wiki, its min-plus, but of course, this is/should not be the standard. However, half the tropical talks I go to are min, half are max. I'll change things around to allow the users to have a choice. I based it on the reals since I've only every seen it as such and to avoid having to check if the base ring has a total order (which is the only thing we really need and I don't know how to check that). I will just let it use any base ring and put warnings in the doc. I'll also include your other changes.

For tropical matrices, this should be the same as tropical polynomials, they aren't there (yet). We will see if making the base ring input arbitrary will make it work. I'll let you know when an updated patch is posted. [Edit: I should actually say I haven't tried, but I'm assuming tropical matrix multiplication becomes matrix addition, so it should break. In an ideal world, I could use this to wrap anything or have this act like a functor; we'll see what kind of world is created by allowing the base ring to be arbitrary.]

Thanks,

Travis

videlec commented 11 years ago

comment:4

If you have a semi-ring R, you can always consider R^n and linear applications on it (here ax+by means max(a+x,b+y) or min(a+x,b+y)). But, be careful, matrix multiplication does not become matrix addition: it is composition of the corresponding linear applications. Right now, Sage is not happy with matrices with entries in a semi-ring

sage: matrix(ZZ,[[0,1],[2,3]])   # no problem
[0 1]
[2 3]
sage: matrix(NN,[[0,1],[2,3]])   # BOOM!
Traceback (most recent call last):
...
ValueError: Invalid matrix constructor.  Type matrix? for help

If you know how to fix it easily it would be wonderful. Otherwise, I will have to work to play with my max-plus matrices.

Vincent

tscrim commented 11 years ago

comment:5

So just to make sure, you want tropical operations being performed with regular matrix multiplication, i.e.

[a b] * [c] = min(a+c, b+d)
        [d]

Which makes more sense, I was thinking of the set of all n x m matrices over a [totally ordered] ring R where the min would be the minimum of all the entries.

In general, creating a matrix space requires something in the category of Rings:

sage: MatrixSpace(NN, 3)
Traceback (most recent call last):
...
TypeError: base_ring (=Non negative integer semiring) must be a ring

(which is the same reason why the matrix() constructor fails). We could probably loosen the restriction to the Semirings category since we still have a + and *.

Best,

Travis

tscrim commented 11 years ago

comment:6

Okay, it seems like it would not quite that simple since Modules and Algebras also require the base to be rings. Granted this is something else that would be an easy change. Anyways that could be something for the upcoming Sage days. Almost done with the revised patch.

videlec commented 11 years ago

comment:7

Replying to @tscrim:

So just to make sure, you want tropical operations being performed with regular matrix multiplication, i.e.
[a b] * [c] = min(a+c, b+d)
        [d]
Which makes more sense, I was thinking of the set of all n x m matrices over a [totally ordered] ring R where the min would be the minimum of all the entries.

This is it. I found another wikpedia page that describes it :wikipedia:Max-plus_algebra (as the name suggests it is max and not min).

tscrim commented 11 years ago

comment:9

Hey Vincent,

Here's the updated patch with your requested changes, except for the matrices. For that, I'd propose another ticket which weakens the restriction to semirings. I kept the default as min because that's what Wikipedia says, but it's an easy change if you prefer it as max. Back to needing a review.

Best,

Travis

darijgr commented 11 years ago

comment:10

Hi Travis,

I'm going to review this (at least mathematically) in the next time, but one question first: does TropicalSemiring(R) really work only for rings R as the doc says, or also for ordered additive groups R (as it should imho)? I'm just not seeing where in the code it uses multiplication (and I hope it does not).

(Also I see a typo "parituclar".)

Thanks a lot for the code; it's coming very handy for what I'm doing these days!

Best regards, Darij

tscrim commented 11 years ago

comment:11

I made a small tweak which should allow it to work for any ordered additive group; I've tested it on the AdditiveAbelianGroup. However the __pow__() uses multiplication, but you'd have to be careful what that means with non-real(complex) numbers anyways. I also fixed the typo.

Best,

Travis

darijgr commented 11 years ago

comment:12

Thanks for the changes!

I'm not going to call this a review but here are some modifications you might want to look over. I'm not claiming they're all for the better. Unfortunately I don't think I'm competent to review much of the code.

On a related note, do we have any structures made for semifields?

darijgr commented 11 years ago

version 2

darijgr commented 11 years ago

comment:13

Attachment: trac_14507-tropical_semiring_suggestions-dg.patch.gz

Oops, I forgot the most important part: If _use_min is set to False, then infinity() should be the smallest, not the largest element of the semiring. Indeed, in that case we have a + b = b if and only if a <= b for any elements a and b of R, so it makes sense to have this also hold if a or b is infinity().

New version uploaded.

tscrim commented 11 years ago

Attachment: trac_14507-tropical_semiring-ts.patch.gz

tscrim commented 11 years ago

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
+---

+Apply:
+
+[attachment: trac_14507-tropical_semiring-ts.patch](https://github.com/sagemath/sage-prod/files/10657701/trac_14507-tropical_semiring-ts.patch.gz)

tscrim commented 11 years ago

comment:14

New version with the changes Darij and I discussed.

Apply: trac_14507-tropical_semiring-ts.patch

tscrim commented 11 years ago

Changed reviewer from Vincent Delecroix to Vincent Delecroix, Darij Grinberg

tscrim commented 11 years ago

Changed keywords from tropical geometry semiring to tropical geometry semiring days49

jdemeyer commented 11 years ago

Changed work issues from documentation, design to none

jdemeyer commented 11 years ago

Merged: sage-5.12.beta0

sagemath / sage

Implement the tropical semiring #14507