Opened 8 years ago
Closed 8 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: |
Description (last modified by )
Attachments (2)
Change History (21)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to needs_work
- Work issues set to documentation, design
comment:3 Changed 8 years ago by
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
comment:4 Changed 8 years ago by
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: ↓ 7 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 themin
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 8 years ago by
- Cc darij added
comment:9 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
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 8 years ago by
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?
comment:13 Changed 8 years ago by
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 8 years ago by
comment:14 Changed 8 years ago by
- 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 8 years ago by
- Keywords days49 added
comment:16 Changed 8 years ago by
- Status changed from needs_review to positive_review
comment:17 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:18 Changed 8 years ago by
- Work issues documentation, design deleted
comment:19 Changed 8 years ago by
- Merged in set to sage-5.12.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
1) Design
+
andmax
(ormin
) appropriately. What if I want tropical integers ? Tropical real intervals ? (note: I do want those).x.min(y)
(optimized mpfr stuff) instead ofmin(x,y)
(Python generic stuff)cdef _new
method that duplicate the object instead of callingself.__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 ?