Message Boards Message Boards


Implementation of Max-Plus Algebra

Posted 10 years ago
1 Reply
7 Total Likes
I have tried to implement the so-called Max-Plus algebra
in Mathematica.

The basic operations can be implemented easily
x_\[CirclePlus]y_ := Max[x, y]
x_\[CircleTimes]y_ := x + y

It appears that the matrix product in max-plus can be easily implemented in principle using 
x_\[CircleDot]y_ := x.y /. Plus ->  Max /. Times ->  Plus

When I multiply two matrices such as
A = {{a, b}, {c, d}};
B = {{e, f}, {g, h}};

This works fine:
A\[CircleDot]B // MatrixForm
[font=Arial, 'Arial Narrow', Helvetica, Verdana, sans-serif]

The first problem occurs when I square a matrix:
A\[CircleDot]A // MatrixForm

Because of the inner workings of the Dot[] function there is an a^2 which should be an a+a. I can fix that by changing the definition of the max-plus dot product to
x_\[CircleDot]y_ :=
x.y /. Plus ->   Max /. Times ->  Plus /. Power -> Times

A\[CircleDot]A // MatrixForm


All of this becomes more complicated when we use numbers in the definition of A, e.g.
A = {{4, 3}, {7, -Infinity}}

Now A^2 gives

instead of 

I have tried all sorts of Unevaluate, Hold, HoldAll etc commands, but it appears that Dot[]  is so deep within the language that its constitutents are difficult to substitute. Does anyone have a good idea how to use this principle to get the max plus matrix multiplication right?

PS: I am aware that I can define max-plus matrix multiplication in ways that are not based on the standard Dot[] function. 
POSTED BY: Marco Thiel
I would use Inner instead of Dot. Specifically:
In[91]:= Inner[Plus, A, B, Max]

Out[91]= {{Max[a + e, b + g], Max[a + f, b + h]}, {Max[c + e, d + g],
  Max[c + f, d + h]}}
I realize you may want to use Dot, but that's simply not going to make life easy. Inner is intended to generalize Dot, and is well suited for this type of functionality.
POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract