Sage: Ticket #14507: Implement the tropical semiring
https://trac.sagemath.org/ticket/14507
<hr />
<p>
Apply:
</p>
<p>
<a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14507/trac_14507-tropical_semiring-ts.patch" title="Attachment 'trac_14507-tropical_semiring-ts.patch' in Ticket #14507">trac_14507-tropical_semiring-ts.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14507/trac_14507-tropical_semiring-ts.patch" title="Download"></a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14507
Trac 1.1.6tscrimTue, 30 Apr 2013 16:33:18 GMTstatus changed
https://trac.sagemath.org/ticket/14507#comment:1
https://trac.sagemath.org/ticket/14507#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketvdelecroixTue, 04 Jun 2013 06:46:22 GMTstatus changed; reviewer, work_issues set
https://trac.sagemath.org/ticket/14507#comment:2
https://trac.sagemath.org/ticket/14507#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
<li><strong>work_issues</strong>
set to <em>documentation, design</em>
</li>
</ul>
<p>
1) <strong>Design</strong>
</p>
<ul><li>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.
</li></ul><ul><li>Why did you choose to base it on real fields ? It seems more like a wrapper that call <code>+</code> and <code>max</code> (or <code>min</code>) appropriately. What if I want tropical integers ? Tropical real intervals ? (note: I do want those).
</li></ul><ul><li>It would be better to call <code>x.min(y)</code> (optimized mpfr stuff) instead of <code>min(x,y)</code> (Python generic stuff)
</li></ul><ul><li>For sake of optimization you should implement a <code>cdef _new</code> method that duplicate the object instead of calling <code>self.__class__(my_parent, my_new_value)</code>. It is the way it is for most cythonized elements.
</li></ul><p>
2) <strong>Documentation</strong> 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 :<a class="ext-link" href="http://en.wikipedia.org/wiki/Tropical_geometry" title="Tropical_geometry in WikiPedia"><span class="icon"></span>wikipedia:Tropical_geometry</a>... actually it might be a good idea to rewrite the wikipedia article ;-)
</p>
<p>
3) <strong>Question</strong> Do you know how I can build a tropical matrix ?
</p>
TickettscrimTue, 04 Jun 2013 14:16:43 GMT
https://trac.sagemath.org/ticket/14507#comment:3
https://trac.sagemath.org/ticket/14507#comment:3
<p>
Hey Vincent,
</p>
<p>
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.
</p>
<p>
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.]
</p>
<p>
Thanks,<br />
Travis
</p>
TicketvdelecroixTue, 04 Jun 2013 15:16:38 GMT
https://trac.sagemath.org/ticket/14507#comment:4
https://trac.sagemath.org/ticket/14507#comment:4
<p>
If you have a semi-ring <code>R</code>, you can always consider <code>R^n</code> and linear applications on it (here <code>ax+by</code> means <code>max(a+x,b+y)</code> or <code>min(a+x,b+y)</code>). 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
</p>
<pre class="wiki">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
</pre><p>
If you know how to fix it easily it would be <strong>wonderful</strong>. Otherwise, I will have to work to play with my max-plus matrices.
</p>
<p>
Vincent
</p>
TickettscrimTue, 04 Jun 2013 19:22:08 GMT
https://trac.sagemath.org/ticket/14507#comment:5
https://trac.sagemath.org/ticket/14507#comment:5
<p>
So just to make sure, you want tropical operations being performed with regular matrix multiplication, i.e.
</p>
<pre class="wiki">[a b] * [c] = min(a+c, b+d)
[d]
</pre><p>
Which makes more sense, I was thinking of the set of all <code>n x m</code> matrices over a [totally ordered] ring R where the <code>min</code> would be the minimum of all the entries.
</p>
<p>
In general, creating a matrix space requires something in the category of <code>Rings</code>:
</p>
<pre class="wiki">sage: MatrixSpace(NN, 3)
Traceback (most recent call last):
...
TypeError: base_ring (=Non negative integer semiring) must be a ring
</pre><p>
(which is the same reason why the <code>matrix()</code> constructor fails). We could probably loosen the restriction to the <code>Semirings</code> category since we still have a <code>+</code> and <code>*</code>.
</p>
<p>
Best,<br />
Travis
</p>
TickettscrimTue, 04 Jun 2013 21:08:14 GMT
https://trac.sagemath.org/ticket/14507#comment:6
https://trac.sagemath.org/ticket/14507#comment:6
<p>
Okay, it seems like it would not quite that simple since <code>Modules</code> and <code>Algebras</code> 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.
</p>
TicketvdelecroixWed, 05 Jun 2013 06:04:01 GMT
https://trac.sagemath.org/ticket/14507#comment:7
https://trac.sagemath.org/ticket/14507#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14507#comment:5" title="Comment 5">tscrim</a>:
</p>
<blockquote class="citation">
<p>
So just to make sure, you want tropical operations being performed with regular matrix multiplication, i.e.
</p>
<pre class="wiki">[a b] * [c] = min(a+c, b+d)
[d]
</pre><p>
Which makes more sense, I was thinking of the set of all <code>n x m</code> matrices over a [totally ordered] ring R where the <code>min</code> would be the minimum of all the entries.
</p>
</blockquote>
<p>
This is it. I found another wikpedia page that describes it :<a class="ext-link" href="http://en.wikipedia.org/wiki/Max-plus_algebra" title="Max-plus_algebra in WikiPedia"><span class="icon"></span>wikipedia:Max-plus_algebra</a> (as the name suggests it is max and not min).
</p>
TicketdarijMon, 10 Jun 2013 13:56:51 GMTcc set
https://trac.sagemath.org/ticket/14507#comment:8
https://trac.sagemath.org/ticket/14507#comment:8
<ul>
<li><strong>cc</strong>
<em>darij</em> added
</li>
</ul>
TickettscrimThu, 13 Jun 2013 21:47:03 GMTstatus changed
https://trac.sagemath.org/ticket/14507#comment:9
https://trac.sagemath.org/ticket/14507#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hey Vincent,
</p>
<p>
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 <code>min</code> because that's what Wikipedia says, but it's an easy change if you prefer it as <code>max</code>. Back to needing a review.
</p>
<p>
Best,<br />
Travis
</p>
TicketdarijThu, 13 Jun 2013 21:51:25 GMT
https://trac.sagemath.org/ticket/14507#comment:10
https://trac.sagemath.org/ticket/14507#comment:10
<p>
Hi Travis,
</p>
<p>
I'm going to review this (at least mathematically) in the next time, but one question first: does <a class="missing wiki">TropicalSemiring?</a>(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).
</p>
<p>
(Also I see a typo "parituclar".)
</p>
<p>
Thanks a lot for the code; it's coming very handy for what I'm doing these days!
</p>
<p>
Best regards,
Darij
</p>
TickettscrimFri, 14 Jun 2013 08:33:09 GMT
https://trac.sagemath.org/ticket/14507#comment:11
https://trac.sagemath.org/ticket/14507#comment:11
<p>
I made a small tweak which should allow it to work for any ordered additive group; I've tested it on the <code>AdditiveAbelianGroup</code>. However the <code>__pow__()</code> uses multiplication, but you'd have to be careful what that means with non-real(complex) numbers anyways. I also fixed the typo.
</p>
<p>
Best,<br />
Travis
</p>
TicketdarijFri, 14 Jun 2013 11:34:08 GMT
https://trac.sagemath.org/ticket/14507#comment:12
https://trac.sagemath.org/ticket/14507#comment:12
<p>
Thanks for the changes!
</p>
<p>
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.
</p>
<p>
On a related note, do we have any structures made for semifields?
</p>
TicketdarijFri, 14 Jun 2013 11:43:05 GMTattachment set
https://trac.sagemath.org/ticket/14507
https://trac.sagemath.org/ticket/14507
<ul>
<li><strong>attachment</strong>
set to <em>trac_14507-tropical_semiring_suggestions-dg.patch</em>
</li>
</ul>
<p>
version 2
</p>
TicketdarijFri, 14 Jun 2013 11:44:41 GMT
https://trac.sagemath.org/ticket/14507#comment:13
https://trac.sagemath.org/ticket/14507#comment:13
<p>
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().
</p>
<p>
New version uploaded.
</p>
TickettscrimFri, 21 Jun 2013 10:47:39 GMTattachment set
https://trac.sagemath.org/ticket/14507
https://trac.sagemath.org/ticket/14507
<ul>
<li><strong>attachment</strong>
set to <em>trac_14507-tropical_semiring-ts.patch</em>
</li>
</ul>
TickettscrimFri, 21 Jun 2013 10:48:32 GMTreviewer, description changed
https://trac.sagemath.org/ticket/14507#comment:14
https://trac.sagemath.org/ticket/14507#comment:14
<ul>
<li><strong>reviewer</strong>
changed from <em>Vincent Delecroix</em> to <em>Vincent Delecroix, Darij Grinberg</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/14507?action=diff&version=14">diff</a>)
</li>
</ul>
<p>
New version with the changes Darij and I discussed.
</p>
<p>
Apply: trac_14507-tropical_semiring-ts.patch
</p>
TickettscrimFri, 21 Jun 2013 13:43:21 GMTkeywords changed
https://trac.sagemath.org/ticket/14507#comment:15
https://trac.sagemath.org/ticket/14507#comment:15
<ul>
<li><strong>keywords</strong>
<em>days49</em> added
</li>
</ul>
TicketdarijFri, 21 Jun 2013 15:23:57 GMTstatus changed
https://trac.sagemath.org/ticket/14507#comment:16
https://trac.sagemath.org/ticket/14507#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketjdemeyerSun, 21 Jul 2013 21:41:33 GMTmilestone changed
https://trac.sagemath.org/ticket/14507#comment:17
https://trac.sagemath.org/ticket/14507#comment:17
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketjdemeyerTue, 30 Jul 2013 10:26:41 GMTwork_issues deleted
https://trac.sagemath.org/ticket/14507#comment:18
https://trac.sagemath.org/ticket/14507#comment:18
<ul>
<li><strong>work_issues</strong>
<em>documentation, design</em> deleted
</li>
</ul>
TicketjdemeyerFri, 02 Aug 2013 14:14:01 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14507#comment:19
https://trac.sagemath.org/ticket/14507#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.12.beta0</em>
</li>
</ul>
Ticket