Julia's (max,+) and (min,+) Algebra Toolbox
The (max,+) algebra (or simply max-plus) redefines operators plus and times from the classical algebra to respective operators maximum (symbolized by ⨁) and times (symbolized by ⨂) in the domain of real numbers ℝ augmented by the number minus infinity -∞. The (min,+) algebra (min-plus) redefines operators plus and times from the classical algebra to respective operators minimum (symbolized by ⨁) and times (symbolized by ⨂) in the domain of real numbers ℝ augmented by the number minus infinity +∞.
The interest in matrix computation in this algebra is taught since 1960 by J. Kuntzman in his theory of networks. It is used in numerous domains such as operational research (network theory), physics (quantization), probabilities (Cramer's transform), law control (discrete events systems), computer science (automata theory, Petri nets), and mathematics (algebraic geometry). This algebra is also known as "tropical algebra".
This current Julia MaxPlus.jl package is a portage in Julia language of the ScicosLab's (max,+) toolbox which gave you functions for doing numerical computations in (max, +) algebra. Due to the young age of this toolbox, in case of doubt about obtained results, please compare them with ScicosLab results, and if they are not matching, report an issue.
This Julia toolbox extends the original toolbox by adding the (min, +) algebra. You may also be interested in this Timed Petri Net and Timed Event Graphs graphical editor which is also bound with (max, +) algebra. This editor can help you generate (max, +) matrices from timed event graphs.
This MaxPlus.jl toolbox depends on the following Julia packages:
Printf, PrettyTables, LinearAlgebra, SparseArrays. They are installed automatically by
Julia's packager. The toolbox is supposed to work with any version of Julia >=
0.6.4 but a version >= 1.0 is the most recommended since older Julia versions
are no longer maintained. Depending on the version of your Julia some importants
issue in the core of Julia impacts this toolbox I had to add some fallbacks but
they may interfere with other packages you are using with MaxPlus.jl.
Installation of the Julia (max,+) package MaxPlus.jl
There are different ways to install the package of this toolbox:
Get the stable
MaxPlus.jlversion of the package from the official Julia packages. Type
Get the latest code source locally. From your Linux terminal type:
git clone https://github.com/Lecrapouille/MaxPlus.jl.git --depth=1 cd MaxPlus.jl julia
Be sure to be inside the root of the git repository. Then, from the Julia REPL
] then type
add . The API may be in gestation and not be stable and
changed from the available one in official Julia packages.
Your first (max,+) lines of code in the REPL
Once the package has been installed, you have to activate the (max,+) package. From the Julia REPL, type:
julia> using MaxPlus
Now, you can type your first lines of (max, +) code inside the Julia REPL:
julia> MP([1 2; 3 8]) .+ 5
Julia will reply to you:
2×2 (max,+) dense matrix: 5 5 5 8
Let's understand how Julia has made its computation:
- First, Julia creates a dense matrix of (max,+) numbers (typed
[MP(1) MP(2); MP(3) MP(8)]).
- For each element of the matrix (the
⨁ 5will be applied.
- Before the
⨁is applied, the number
5is converted to a (max,+) number
Float64numbers are implicitly promoted to a (max,+) number (internally encoded as
⨂ are not used to avoid complex formulas hard to type and hard
to read, so keep using
The equivalent of
MP([1 2; 3 8]) .+ 5 in classical algebra is:
[max(1, 5) max(2, 5) max(3, 5) max(8, 5)]
and shall not be confused with this formula
[1 2; 3 8] .+ 5 in classical algebra
[(1 + 5) (2 + 5) (3 + 5) (8 + 5)]
Your first (min,+) lines of code in the REPL
This toolbox initially focused on the (max,+) algebra but one thing leading to another, functions for algebra (min,+) have been introduced but the name of the package MaxPlus.jl hasn't changed.
For (min,+) numbers:
julia> MI([1 2; 3 8]) 2×2 (min,+) dense matrix: 1 2 3 8
Do you want to dive more about programming in (max,+) with this toolbox ? The following documents are compiled into a single online documentation: https://lecrapouille.github.io/MaxPlus.jl else within GitHub you can see them as Markdown:
- Introduction and tutorials of this toolbox and tropical algebra in French and in English.
- The index of (max,+) functions.
- The index of (min,+) functions.
- The index of (max,+) linear system.
- The Rosetta Stone to translate SicosLab to MaxPlus.jl functions.
- For developpers, you can run non regression tests.
- A Timed Petri net and graph event editor, a separate project of mine in relation to (max,+) algebra.
- The bibliography links to other documentation and ressources.
Feel free to contribute and particularly, since I'm more of a C++ guy, to help reworking the code using more Julia formalism.