The algebra (min,+) (pronounced min-plus) redefines the addition and multiplication operators of classical algebra by respectively the minimum operators noted $\oplus$ and addition noted $\otimes$ in the domain of real numbers $\mathbb{R}$ increased by the number plus infinity ($\varepsilon = +\infty$) which we call $\mathbb{R}_{\varepsilon} = \mathbb{R} \cup \{ +\infty \}$. Its algebraic structure is that of a selective-invertible dioid according to the Gondran-Minoux classification (this structure is more frequently called idemiotent semi-field) $(\mathbb{R}_{\varepsilon}, \oplus, \otimes)$.
$$\forall a,b \in \mathbb{R}_{\varepsilon}: a \oplus b \triangleq \min(a,b)$$$$\forall a,b \in \mathbb{R}_{\varepsilon}: a \otimes b \triangleq a + b$$The interest of matrix calculation in this algebra is taught as early as the 1960s by J. Kuntzman in his network theory. It is used in many fields Operational research (network theory), Physics (Quantification), Probability (Cramer transform), Automation (discrete event systems), Computer science (automata theory, Petri nets), Mathematics (algebraic geometry ).
In a first tutorial, we showed you how to install our Max-Plus toolbox for the Julia language, the main purpose of which is to facilitate matrix calculations in this algebra. It can be downloaded from GitHub at https://github.com/Lecrapouille/MaxPlus.jl or from Julia's package system via the command ] add MaxPlus
. It is a port in Julia of Max-Plus arithmetic from ScicosLab, a fork of Scilab being replaced by NSP.
In a previous tutorial, we have introduced the algebra (max,+). This document will introduce the basic functions of the toolbox concerning the (min,+) algebra. The reader can consult the bibliography to obtain the demonstration of certain results and the description of the algorithms used. For those who wished to compare this toolbox with Sicoslab, unfortunately the latter does not implement anything concerning the (min,+) algebra.
From Julia's REPL, launch Jupyter notebook:
# using IJulia
# notebook()
In a newly created Jupyter document, load the Max-Plus toolbox from the MaxPlus.jl folder:
push!(LOAD_PATH, pwd())
using MaxPlus
For the moment, for educational purposes, we activate a special display mode for Max-Plus numbers that explicitly displays the $+\infty$ and the $0.0$. More pleasant display modes will be explained later.
set_tropical_display(0)
I will show -Inf, +Inf and 0.0
This toolbox allows to generate code $\LaTeX$ via the Base.show
. In Jupyter, this mode seems to be the one used by default, but here, we prefer to keep the display in plain text. To do this, you must first type:
Base.show(io::IO, ::MIME"text/latex", x::MI) = show(io, MIME"text/plain", x)
Base.show(io::IO, ::MIME"text/latex", A::MIAbstractVecOrMat) = show(io, MIME"text/plain", A)
Before presenting the algebra (max,+), let's type a few purely Julia lines to learn how to create Min-Plus scalars thanks to the constructor MI()
:
a = MI(1.0); b = MI(3.5); c = MI(5)
typeof(a), typeof(b), typeof(c)
(MI, MI, MI)
Dans Julia, les nombres Min-Plus sont codés en interne par des Float64
car ils sont seulement définis dans l'espace $\mathbb{R}_{\varepsilon}$. Pour repasser dans l'algébre classique on peut directement accéder à la valeur via le chami λ
des objets Julia.
a, a.λ, typeof(a), typeof(a.λ)
(1.0, 1.0, MI, Float64)
c, c.λ, typeof(c), typeof(c.λ)
(5.0, 5.0, MI, Float64)
If you don't want to use the chami explicitly, λ
the function plustimes
does that too. It also works for sparse and dense matrices:
a, plustimes(a), typeof(a), typeof(plustimes(a))
(1.0, 1.0, MI, Float64)
a + a, plustimes(a) + plustimes(a)
(1.0, 2.0)
Min-Plus numbers contaminate other numbers (integers, reals): they convert a non-Min-Plus number into a Min-Plus number via the arithmetic operators where the promotion operators imply:
d = 1.0
typeof(d), typeof(c), typeof(c + d), typeof((c + d).λ), c + d
(Float64, MI, MI, Float64, 1.0)
We see that the Min-Plus addition has converted d
from type Float64
to type MI
. Same behavior for integers where f
from type Int64
is converted to to type MI
:
f = 1
typeof(f), typeof(c), typeof(c + f), typeof((c + f).λ), c + f
(Int64, MI, MI, Float64, 1.0)
MP(MI(4))
(max,+) 4.0
MI(MP(4))
(min,+) 4.0
MI(MP([4 5]))
1×2 (min,+) dense matrix: 4.0 5.0
On the other hand, it is forbidden to mix Max-Plus and Min-Plus. The following code will produce the error Va produire Cannot promote (min,+) to (max,+)
:
# MI(4) + MP(4); as well as MI(4) * MP(4);
Neutral elements for operators $\oplus$ and $\otimes$ are given as Julia constantes:
Neutral element $\varepsilon$ (sometimes denoted $\mathbb{0}$ in some documents) for the operator $\oplus$ : the Julia constants are mi0
equal to $+\infty$. This element is absorbing for the multiplication $\varepsilon\otimes a=a\otimes \varepsilon=\varepsilon$.
Neutral element $e$ (sometimes denoted $\mathbb{1}$ in some documents and on Scilab %1
) for the operator $\otimes$ : the Julia constants are either mi1
or mie
equal to 0.
Although this toolbox is dedicated to Max-Plus algebra it uses the constant mitop
equals to $-\infty$ when doing calculations in dual Min-Plus algebra. This constant corresponds to the ScicosLab %top
constant.
These numbers are of type MI
(and we can eventually convert them into numbers of classical algebra either via the field λ
or the function plustimes
).
mi0, mi1, mitop, zero(MI), one(MI)
(Inf, 0.0, -Inf, Inf, 0.0)
We see that so far Julia is showing in her results +Inf
and 0.0
for ε
and 0
what is not very compact. In Max-Plus we often handle large matrices and a good display is important: the more compact better it is. Rememeber at the beginning of this document we wrote set_tropical_display(0)
to force the display (named style 0
) for a pedagogical concern so that the reader does not confuse the Max-Plus zeros with the zeros of classical algebra.
There are four possible styles of display of Max-Plus numbers that can be switched with the function set_tropical_display
that accepts a number between 0
and 4
. The style 1
being the one defined by default and follows the display in ScicosLab because it allows to display the matrices in a compact way. Indeed, it is common in Max-Plus to have to manipulate and display large matrices filled with elements $\varepsilon$.
Style 0
: is the classic Julia display: numbers $+\infty$ are displayed +Inf
and numbers as reals like 0.0
.Style 1 or 2
: numbers $+\infty$ are displayed as a dot .
.Style 3 or 4
: numbers $+\infty$ are displayed as ε
.Style 1 or 3
: real numbers which can be written as integers (therefore without decimal places) will be displayed as integers. For example 0.0
will be displayed as 0
.Style 2 or 4
: Zeros are displayed as e
.The activated style impacts the functions Base.show
and also impacts the functionLaTeX
for the generation of $\LaTeX$ code for the matrices (which we will see a little later in this document).
# Classic Julia-style display
set_tropical_display(0)
J = MI([+Inf 0; 0 +Inf])
I will show -Inf, +Inf and 0.0
2×2 (min,+) dense matrix: Inf 0.0 0.0 Inf
# Display 0 as e
set_tropical_display(2)
J
I will show (max,+) -Inf and (min,+) +Inf as . and 0.0 as e
2×2 (min,+) dense matrix: . e e .
# Display +Inf as ε
set_tropical_display(3)
J
I will show (max,+) -Inf and (min,+) +Inf as ε
2×2 (min,+) dense matrix: ε 0 0 ε
# Display +Inf as ε and 0 as e
set_tropical_display(4)
J
I will show (max,+) -Inf and (min,+) +Inf as ε and 0.0 as e
2×2 (min,+) dense matrix: ε e e ε
And finaly, the default mode:
# Display +Inf as a .
set_tropical_display(1)
J
I will show (max,+) -Inf and (min,+) +Inf as .
2×2 (min,+) dense matrix: . 0 0 .
The addition operator is redefined by the min
classical algebra operator. Its symbol, to differentiate it from addition in classical algebra, is $\oplus$. But in Julia we will keep the symbol +
. This operator is associative, commutative, has a neutral element (denoted $\varepsilon$) and is idempotent. $\forall a,b,c \in \mathbb{R}_{\varepsilon}:$
a = MI(1); b = MI(3); c = MI(5);
(a, b, c)
(1, 3, 5)
a + b
(min,+) 1
The following equality $a \oplus b = a \oplus c$ does not result $b = c$. On the other hand, we will have $a \oplus b = a$ if $a \leq b$ or more generally $a \oplus b = a$ or $b$. According to the terminology of Gondran-Minoux $\oplus$ is selective.
a + b == b + a
true
a + b + c == (a + b) + c == a + (b + c)
true
a + b + c # ≜ min(a, b, c) == min(1, 3, 5)
(min,+) 1
a + mi0 == mi0 + a == a
true
Is equivalent to:
a + mi0 == mi0 + a == a
true
(a, mi0), (a + mi0), (mi0 + a)
((1, .), 1, 1)
Note that 0
is neutral for positive numbers:
a + 0 == 0 + a == a
false
a, 0, a + 0
(1, 0, 0)
a + a # ≜ min(a, a) == min(1, 1) == 1
(min,+) 1
The multiplication operator is redefined by the addition operator which is associative, commutative, has the neutral element $e$, the absorbing element $\varepsilon$ and is distributive over $\oplus$
a * b # ≜ a + b == 1 + 3 == 4
(min,+) 4
a * b == b * a
true
a * b * c == (a * b) * c == a * (b * c)
true
a * b * c
(min,+) 9
a * mie == mie * a == a
true
Is equivalent to:
a * mi1 == mi1 * a == a
true
a * mi0 == mi0 * a == mi0
true
Is equivalent to:
a * mi0 == mi0 * a == mi0
true
By convention:
$$+\infty \otimes \varepsilon = \varepsilon \otimes +\infty = \varepsilon$$mitop * mi0
(min,+) .
a * a # ≜ a + a == 1 + 1 == 2
(min,+) 2
(a + b) * c == (a * c) + (b * c) # => min(a, b) + c == min(a + c, b + c)
true
(a * c) + (b * c)
(min,+) 6
In Min-Plus algebra the power operator behaves like a multiplication in classical algebra:
MI(2)^5 # ==> 2 * 5
(min,+) 10
MI(2)^0 # ==> 2 * 0
(min,+) 0
MI(2)^-1 # ==> 2 * -1
(min,+) -2
Instead of ^-1
we can also call the function inv()
:
inv(MI(2))
(min,+) -2
MI(1:5)
5-element (min,+) vector: 1 2 3 4 5
MI(1:0.5:3)
5-element (min,+) vector: 1 1.5 2 2.5 3
As with sczlairs, contamination of Max-Plus numbers on Int64
and Float64
numbers also works on elements of dense and sparse matrices:
[MI(1) 2; 3.5 4.0]
2×2 (min,+) dense matrix: 1 2 3.5 4
MI(1)
of type MI
has contamined the classical integers 2
, 3.0
and 4
to MI
numbers.
Here's another more elegant way to write it:
MI([1 2; 3 4])
2×2 (min,+) dense matrix: 1 2 3 4
Another example of contamination of Max-Plus numbers:
f = 3; a = MI(1)
[f a
f + f a + a]
2×2 (min,+) dense matrix: 3 1 6 1
f + f
being og Int64
the classic addition was made before the promotion in numbers MI
. On the other hand, a + a
being MI
it is the addition (min, +) which was used. Finally all the elements of the matrix are of type MI
.
In the following example, $\varepsilon$ rendered the following matrix implicitly MI
:
[mi0 2; 3.5 4]
2×2 (min,+) dense matrix: . 2 3.5 4
La contamination fonctionne également sur les matrices creuses.
Une matrice creuse est une matrice contenant beaucoup de zéros. Sa structure interne est conçue pour ne pas garder en mémoire ces zéros (sauf en Julia s'ils sont explicitement donnés). En algèbre classique les zéros sont 0 (pour les entiers) ou 0.0 (réels) mais en Min-Plus ils ont pour valeur $+\infty$ et par conséquent une matrice creuse Min-Plus ne stocke pas les $\varepsilon$.
Les matrices creuses sont essentielles pour les applications qui necessitent souvent des matrices de grandes tailles. Par exemile dans le calcul du chemin le plus long dans un reseau routier, la taille de la matrice sera le nombre de noeuds, le nombre d'éléments non nuls (le nombre de routes joignant 2 noeuds) va croitre linéairement avec cette taille, alors que le nombre de coefficients de la matrice croit comme le carré de la taille.
Pour créer une matrice creuse Min-Plus, plusieurs choix:
mizeros
que l'on verra plus tard.SparseArrays.sparse
couplée avec le constructeur MI
.MI
: un vecteur des données à stocker et deux vecteurs indiquant les index de ces données dans la matrice.using SparseArrays;
set_tropical_display(0);
I will show -Inf, +Inf and 0.0
S = MI(sparse([1 2; 0 4]))
2×2 (min,+) sparse matrix with 3 stored entries: [1, 1] = 1.0 [1, 2] = 2.0 [2, 2] = 4.0
Here the zero of classical algebra (equal to 0) has been deleted by SparseArrays.sparse
but in the following example it is the zero of Max-Plus algebra ($\varepsilon$ vallant $+\infty$) that a will be deleted.
S = sparse(MI([1 2; +Inf 4]))
2×2 (min,+) sparse matrix with 3 stored entries: [1, 1] = 1.0 [1, 2] = 2.0 [2, 2] = 4.0
The attentive reader will have understood that the display is that of Julia 1.5 even if Julia >= 1.6 is used. Indeed, with Julia 1.6 the display of a sparse matrix is done in the same way as a dense matrix what does not make sens. This toolbox forces the old display for Max-Plus sparse matrices.
As a reminder, the function SparseArrays.findnz
returns the stored elements D
as well as their indices I
and J
in the form of a triplet of row vectors which quickly becomes unreadable as soon as the matrix grows a little:
i,j,d = findnz(S)
([1, 1, 2], [1, 2, 2], MI[1.0, 2.0, 4.0])
Just like SparseArrays.findnz
returning a triple of column vectors I
, J
and D
, the SparseArrays.sparse
accepts its same parameters. But explicit zeros will be stored:
S = MI(sparse([1; 2; 3], [1; 2; 3], [42; 0; 5]))
3×3 (min,+) sparse matrix with 3 stored entries: [1, 1] = 42.0 [2, 2] = 0.0 [3, 3] = 5.0
Here the zero of classical algebra (being 0) has not been deleted by SparseArrays.sparse
. In the following example it is the zero of the Min-Plus algebra ($\varepsilon$ equal $+\infty$) which has not been deleted.
S = sparse([1; 2; 3], [1; 2; 3], MI([42; +Inf; 5]))
3×3 (min,+) sparse matrix with 3 stored entries: [1, 1] = 42.0 [2, 2] = Inf [3, 3] = 5.0
This is a behavior Julia intended for more flexibility as you can call dropzeros
to remove them:
S = MI([1; 2; 3], [1; 2; 3], MI([0; +Inf; 5]))
3×3 (min,+) sparse matrix with 2 stored entries: [1, 1] = 0.0 [3, 3] = 5.0
As seen previously for scalars, we may want to convert a Min-Plus matrix into a classical matrix (+,*) :
A = MI([4 0; 7 +Inf])
plustimes(A)
2×2 Matrix{Float64}: 4.0 0.0 7.0 Inf
Also works for sparse matrices:
Z = spzeros(MI,2,2)
2×2 (min,+) sparse matrix with 0 stored entries
plustimes(Z)
2×2 SparseMatrixCSC{Float64, Int64} with 4 stored entries: Inf Inf Inf Inf
We may want to go from a Min-Plus sparse matrix to a full matrix in classical algebra:
Matrix(plustimes(Z))
2×2 Matrix{Float64}: Inf Inf Inf Inf
All three functions produce the same result:
full(Z), dense(Z), Matrix(Z)
(MI[Inf Inf; Inf Inf], MI[Inf Inf; Inf Inf], MI[Inf Inf; Inf Inf])
Just like sparse matrices several ways to do it. Preserving the zero()
s:
sparsevec([1, 3], MI([0, -Inf]))
3-element SparseVector{MI, Int64} with 2 stored entries: [1] = 0.0 [3] = -Inf
MI(sparsevec([1, 3], [0, -Inf]))
3-element SparseVector{MI, Int64} with 2 stored entries: [1] = 0.0 [3] = -Inf
Where by removing the zeros:
MI([1, 3], [0, -Inf])
3-element SparseVector{MI, Int64} with 2 stored entries: [1] = 0.0 [3] = -Inf
Since Julia v1.0, the function eye
no longer exists and has been replaced by LinearAlgebra.I
but this toolkit adds their equivalent eye(MI,...)
and miI
:
using LinearAlgebra
I
UniformScaling{Bool} true*I
Matrix{MI}(I, 2, 2)
2×2 (min,+) dense matrix: 0.0 Inf Inf 0.0
miI
UniformScaling{MI} 0.0*I
Matrix(miI, 2, 2)
2×2 (min,+) dense matrix: 0.0 Inf Inf 0.0
Matrix(miI, 2, 2) == eye(MI,2,2), Matrix{MI}(I, 2, 2) == eye(MI,2,2)
(true, true)
The function eye
is easier to type:
J = eye(MI,2,2)
2×2 (min,+) dense matrix: 0.0 Inf Inf 0.0
J = eye(MI,2) # Equivalent to eye(MI, 2,2)
2×2 (min,+) dense matrix: 0.0 Inf Inf 0.0
Size 3 $\times$ 2:
J = eye(MI,3,2)
3×2 (min,+) dense matrix: 0.0 Inf Inf 0.0 Inf Inf
Build an identity matrix (max,+) from the dimensions of an existing (max,+) matrix:
A = MI([1.0 -Inf; 0.0 4])
J = eye(A)
2×2 (min,+) dense matrix: 0.0 Inf Inf 0.0
For example matrix of size 2 $\times$ 2 :
$$\left[ \begin{array}{*{20}c} e & e \\ e & e \\ \end{array} \right]$$O = ones(MI,2,2)
2×2 (min,+) dense matrix: 0.0 0.0 0.0 0.0
Column vector of 2 elements:
O = ones(MI,2) # /!\ N'est pas équivalent à ones(MI,2,2) /!\
2-element (min,+) vector: 0.0 0.0
Build a matrix of e
(max,+) from the dimensions of an existing (max,+) matrix:
A = MI([1.0 -Inf; 0.0 4])
J = ones(A)
2×2 (min,+) dense matrix: 0.0 0.0 0.0 0.0
Caution: Under Scilab zeros
will create a sparse matrix while natively Julia will create a full matrix, you will have to remember to call spzeros
instead to have the same behavior.
Z = zeros(MI,2,2)
2×2 (min,+) dense matrix: Inf Inf Inf Inf
Z = zeros(MI,2,3)
2×3 (min,+) dense matrix: Inf Inf Inf Inf Inf Inf
Z = zeros(MI,2)
2-element (min,+) vector: Inf Inf
Z = spzeros(MI,2,2)
2×2 (min,+) sparse matrix with 0 stored entries
Z = spzeros(MI,2,3)
2×3 (min,+) sparse matrix with 0 stored entries
Z = spzeros(MI,2)
2-element SparseVector{MI, Int64} with 0 stored entries
Note that these matrices are empty. Indeed, they correspond to the 0 eliminated from sparse matrices in classical algebra. A Max-Plus sparse matrix does not store Max-Plus numbers $+\infty$ (note: finally until Julia > 1.9 because the previous versions had a bug they confused 0 and zero(T)
with T
template of type MI
).
You must use the function full
or the synonymous function dense
.
Z = full(zeros(MI,2,2))
2×2 (min,+) dense matrix: Inf Inf Inf Inf
Dense:
diagm(MP([1,2,3]))
Sparse:
spdiagm(MP([1,2,3]))
Julia allows you to iterate over the elements of an array, matrix, vector and apply an operation to each of them. For instance:
$$4 \oplus \left[ \begin{array}{*{20}c} 2 \\ 8\\ \end{array} \right] = \left[ \begin{array}{*{20}c} 4 \oplus 2 \\ 4 \oplus 8\\ \end{array} \right] = \left[ \begin{array}{*{20}c} 2 \\ 4 \\ \end{array} \right]$$A = MI([2; 8])
2-element (min,+) vector: 2.0 8.0
We apply the max(4, ) function to each of the elements that will be contaminated in Min-Plus number:
4 .+ A
2-element (min,+) vector: 2.0 4.0
A .+ 4.0
2-element (min,+) vector: 2.0 4.0
We apply the function +(4, ) on each of the elements:
4 .* A
2-element (min,+) vector: 6.0 12.0
A .* 4.0
2-element (min,+) vector: 6.0 12.0
The dies can be of the Max-Plus type. Addition and matrix product Max-Plus matches addition and matrix product with operators $+$ et $\times$ overloaded.
MI([1 6; 8 3]) + MI([2 5; 3 3])
2×2 (min,+) dense matrix: 1.0 5.0 3.0 3.0
A = MI([4 3; 7 +Inf])
A * A
2×2 (min,+) dense matrix: 8.0 7.0 11.0 10.0
A * A == A^2
true
Also works on sparse matrices:
A = MI([4 3; 7 +Inf])
sparse(A)
2×2 (min,+) sparse matrix with 3 stored entries: [1, 1] = 4.0 [2, 1] = 7.0 [1, 2] = 3.0
A * sparse(A) == sparse(A) * A == sparse(A) * sparse(A)
true
Power of a Max-Pus matrix:
A^5
2×2 (min,+) dense matrix: 20.0 19.0 23.0 22.0
A^0
2×2 (min,+) dense matrix: 0.0 Inf Inf 0.0
Also applies to compatible rectangular matrices:
MI([2 0; mi0 5]) * MI([2; 8])
2-element (min,+) vector: 4.0 13.0
MI([2 8]) * MI([2 0; mi0 5])
1×2 (min,+) dense matrix: 4.0 2.0
Check that the identity matrix $I$ is quite neutral:
$$ A \otimes I = I \otimes A = A$$A = MI([4 3; 7 +Inf])
A * eye(MI, 2,2) == eye(MI, 2,2) * A == A
true
Let’s check the zero matrix is indeed absorbing:
A * zeros(MI, 2,2) == zeros(MI, 2,2) * A == zeros(MI, 2,2)
true
A + zeros(MI, 2,2) == zeros(MI, 2,2) + A == A
true
From a Min-Plus matrix, we can generate the code $\LaTeX$
through the function LaTeX
or through the function show
with the argument MIME"text/latex"
. The function set_tropical_display
modifies the neutral and absorbing elements of the generated LaTeX code accordingly.
set_tropical_display(0)
LaTeX(stdout, eye(MI, 2,2))
I will show -Inf, +Inf and 0.0\left[ \begin{array}{*{20}c} 0 & +\infty \\ +\infty & 0 \\ \end{array} \right]
Once this code $\LaTeX$ compiled, it will display:
$$\left[ \begin{array}{*{20}c} 0 & +\infty \\ +\infty & 0 \\ \end{array} \right]$$While :
set_tropical_display(2)
LaTeX(stdout, eye(MI, 2,2))
I will show (max,+) -Inf and (min,+) +Inf as . and 0.0 as e\left[ \begin{array}{*{20}c} e & . \\ . & e \\ \end{array} \right]
Once this code $\LaTeX$ compiled, it will display:
$$\left[ \begin{array}{*{20}c} e & . \\ . & e \\ \end{array} \right]$$Fonctionne avec les matrices creuses :
set_tropical_display(1)
LaTeX(stdout, zeros(MI, 2,2))
I will show (max,+) -Inf and (min,+) +Inf as .\left[ \begin{array}{*{20}c} . & . \\ . & . \\ \end{array} \right]
Once this code $\LaTeX$ compiled, it will display:
$$\left[ \begin{array}{*{20}c} . & . \\ . & . \\ \end{array} \right]$$