Opened 7 years ago

Closed 7 years ago

#14507 closed enhancement (fixed)

Implement the tropical semiring

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-5.12
Component: algebra Keywords: tropical geometry semiring days49
Cc: darij Merged in: sage-5.12.beta0
Authors: Travis Scrimshaw Reviewers: Vincent Delecroix, Darij Grinberg
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Attachments (2)

trac_14507-tropical_semiring_suggestions-dg.patch (9.0 KB) - added by darij 7 years ago.
version 2
trac_14507-tropical_semiring-ts.patch (19.1 KB) - added by tscrim 7 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 7 years ago by tscrim

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work
  • Work issues set to documentation, design

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 ?

comment:3 Changed 7 years ago by tscrim

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

Last edited 7 years ago by tscrim (previous) (diff)

comment:4 Changed 7 years ago by vdelecroix

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

comment:5 follow-up: Changed 7 years ago by 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.

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

comment:6 Changed 7 years ago by tscrim

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.

comment:7 in reply to: ↑ 5 Changed 7 years ago by vdelecroix

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).

comment:8 Changed 7 years ago by darij

  • Cc darij added

comment:9 Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

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

comment:10 Changed 7 years ago by darij

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

comment:11 Changed 7 years ago by tscrim

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

comment:12 Changed 7 years ago by darij

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?

Changed 7 years ago by darij

version 2

comment:13 Changed 7 years ago by darij

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.

Changed 7 years ago by tscrim

comment:14 Changed 7 years ago by tscrim

  • Description modified (diff)
  • Reviewers changed from Vincent Delecroix to Vincent Delecroix, Darij Grinberg

New version with the changes Darij and I discussed.

Apply: trac_14507-tropical_semiring-ts.patch

comment:15 Changed 7 years ago by tscrim

  • Keywords days49 added

comment:16 Changed 7 years ago by darij

  • Status changed from needs_review to positive_review

comment:17 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:18 Changed 7 years ago by jdemeyer

  • Work issues documentation, design deleted

comment:19 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.12.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.