{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Introducing the Julia MaxPlus.jl Package as (max,+) Toolbox\n", "\n", "## Algebra (max,+)\n", "\n", "\n", "The algebra (max,+) (pronounced max-plus) redefines the addition and multiplication operators of classical algebra by respectively the maximum operators noted $\\oplus$ and addition noted $\\otimes$ in the domain of real numbers $\\mathbb{R}$ increased by the number minus 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 idempotent semi-field) $(\\mathbb{R}_{\\varepsilon}, \\oplus, \\otimes)$.\n", "\n", "$$\\forall a,b \\in \\mathbb{R}_{\\varepsilon}: a \\oplus b \\triangleq \\max(a,b)$$\n", "$$\\forall a,b \\in \\mathbb{R}_{\\varepsilon}: a \\otimes b \\triangleq a + b$$\n", "\n", "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 ).\n", "\n", "In a previous 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. This document presents only the basic functions of the toolbox while introducing the basics of algebra (max,+). The algebra (min,+) will be the subject of another tutorial.\n", "\n", "For those who wish to compare this toolbox with Sicoslab, we remind you that a Max-Plus Sicoslab number is created by the maxplus function abbreviated by the function `#()`, that the neutral elements are noted `%0` and `%1`, that a Max-Plus number is absorbing and that finally a help and a demonstration are accessible from the menus of ScicosLab. One can consult the [bibliography](../docs/src/bibliography.md) to obtain the demonstration of certain results and the description of the algorithms used. For example, the [following PDF document](https://jpquadrat.github.io/TPALGLIN.pdf) describes the Max-Plus features of ScicosLab in a similar way to this tutorial.\n", "\n", "In this document term (Scilab) toolbox is equivalent to (Julia) package." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Start the Julia Toolbox MaxPlus.jl" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "From Julia's REPL, launch Jupyter notebook:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# using IJulia\n", "# notebook()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In a newly created Jupyter document, load the Max-Plus toolbox from the MaxPlus.jl folder:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "scrolled": true }, "outputs": [], "source": [ "push!(LOAD_PATH, pwd())\n", "using MaxPlus" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show -Inf, +Inf and 0.0" ] } ], "source": [ "set_tropical_display(0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "Base.show(io::IO, ::MIME\"text/latex\", x::MP) = show(io, MIME\"text/plain\", x)\n", "Base.show(io::IO, ::MIME\"text/latex\", A::MPAbstractVecOrMat) = show(io, MIME\"text/plain\", A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Max-Plus Scalars\n", "\n", "Before presenting the algebra (max,+), let's type a few purely Julia lines to learn how to create Max-Plus scalars thanks to the constructor `MP()`:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 5.0" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = MP(1.0); b = MP(3.5); c = MP(5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In Scilab we would have written `#(1.0)`. In this Julia toolbox, the Max-Plus numbers are internally encoded by des `Float64` (via the accessible field `λ`) because the numbers in this algebra are defined in the space $\\mathbb{R}_{\\varepsilon}$. For more flexibility, the constructor accepts integers (`Integer`) but they will be converted internally to `Float64`. Note that there are other Julia packages on numbers on Max-Plus which offer to change the internal type to integer but this is not the case with this toolkit (and this will not be changed).\n", "\n", "To go back to classical algebra (namely `(+,*)`) there are different ways to achieve this. The first way consists in accessing the field `λ` of objects Julia (scalar) either via the function `plustimes` does it too (its name comes from Scilab in reference to the `+`, `*` operators of classical algebra) or methods with names more in the spirit of Julia are also possible `Float64` and `float`. These functions also accept sparse and full matrices as well as sparse and full vectors." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1.0, 1.0, MP, Float64, 1.0, 1.0, 1.0)" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a, a.λ, typeof(a), typeof(a.λ), plustimes(a), Float64(a), float(a)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(MP, Float64, Float64, Float64, Float64)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "typeof(a), typeof(a.λ), typeof(plustimes(a)), typeof(Float64(a)), typeof(float(a))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Max-Plus numbers contaminate other numbers (integers, reals): they convert a non-Max-Plus number into a Max-Plus number via arithmetic operators or implicit promotion operators. We effect, on the one hand we consider that we work only in this algebra and on the other hand that simplifies the writing of the code (as well as its reading):" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(Float64, MP, MP, Float64, 5.0)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d = 1.0\n", "typeof(d), typeof(c), typeof(c + d), typeof((c + d).λ), c + d" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We see that the Max-Plus addition has converted `d` from type `Float64` to type `MP`. Same behavior for integers where `f` from type `Int64` is converted to to type `MP`:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(Int64, MP, MP, Float64, 5.0)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = 1\n", "typeof(f), typeof(c), typeof(c + f), typeof((c + f).λ), c + f" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Max-Plus constants\n", "\n", "The neutral elements for $\\oplus$ and $\\otimes$ operators are given as Julia constants:\n", "- Neutral element $\\varepsilon$ (sometimes denoted $\\mathbb{0}$ in certain documents and on Scilab `%0`) for the operator $\\oplus$: the Julia constants are `mp0` either `ε` (obtained by typing `\\varepsilon`) equal $-\\infty$ (either `MP(-Inf)`). This element is absorbing for the multiplication $\\varepsilon\\otimes a=a\\otimes \\varepsilon=\\varepsilon$.\n", "\n", "- Neutral element $e$ (sometimes denoted $\\mathbb{1}$ in certain documents and on Scilab `%1`) for operator $\\otimes$: the Julia constants are `mp1` either equal `mpe` to `0`.\n", "\n", "- Although this toolbox is dedicated to Max-Plus algebra, it uses the constant `mptop` equal $+\\infty$ when doing calculations in Min-Plus dual algebra. This constant corresponds to the ScicosLab `%top`.\n", "\n", "These numbers are of type `MP` (and we can eventually convert them into numbers of classical algebra either via the field `λ` or the function `plustimes`." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-Inf, -Inf, -Inf, 0.0, 0.0, 0.0, Inf, -Inf, 0.0, Inf, Inf)" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mp0, ε, MP(-Inf), mp1, mpe, MP(0), mptop, zero(MP), one(MP), mptop, MP(Inf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Controlling the display of Max-Plus numbers\n", "\n", "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.\n", "\n", "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$.\n", "\n", "- `Style 0`: is the classic Julia display: numbers $-\\infty$ are displayed `-Inf` and numbers as reals like `0.0`.\n", "- `Style 1 or 2`: numbers $-\\infty$ are displayed as a dot `.`.\n", "- `Style 3 or 4`: numbers $-\\infty$ are displayed as `ε`.\n", "- `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`.\n", "- `Style 2 or 4`: Zeros are displayed as `e`.\n", "\n", "The activated style impacts the functions `Base.show` and also impacts the function`LaTeX` for the generation of $\\LaTeX$ code for the matrices (which we will see a little later in this document)." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show -Inf, +Inf and 0.0" ] }, { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " -Inf 0.0\n", " 0.0 -Inf\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Classic Julia-style display\n", "set_tropical_display(0)\n", "\n", "J = MP([-Inf 0; 0 -Inf])" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show (max,+) -Inf and (min,+) +Inf as . and 0.0 as e" ] }, { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " . e\n", " e .\n" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Display 0s as e\n", "set_tropical_display(2)\n", "\n", "J" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show (max,+) -Inf and (min,+) +Inf as ε" ] }, { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " ε 0\n", " 0 ε\n" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Display -Inf as ε\n", "set_tropical_display(3)\n", "\n", "J" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show (max,+) -Inf and (min,+) +Inf as ε and 0.0 as e" ] }, { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " ε e\n", " e ε\n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Display -Inf as ε and 0 as e\n", "set_tropical_display(4)\n", "\n", "J" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And finaly, the default mode:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show (max,+) -Inf and (min,+) +Inf as ." ] }, { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " . 0\n", " 0 .\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Display -Inf as a .\n", "set_tropical_display(1)\n", "\n", "J" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Max-Plus Operator $\\oplus$\n", "\n", "The addition operator is redefined by the `max` 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}:$\n", "\n", "$$a \\oplus b \\triangleq \\max(a,b)$$" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 3, 5)" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = MP(1); b = MP(3); c = MP(5);\n", "(a, b, c)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 3" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + b # ≜ max(a, b) ==> max(1, 3) = 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### $\\oplus$ is not invertible or simplifiable\n", "\n", "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 \\geq b$ or more generally $a \\oplus b = a$ or $b$. According to the terminology of Gondran-Minoux $\\oplus$ is selective." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Commutativity of $\\oplus$\n", "\n", "$$a \\oplus b = b \\oplus a$$\n", "$$\\triangleq$$\n", "$$\\max(a,b) = \\max(b,a)$$" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + b == b + a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Associativity of $\\oplus$\n", "\n", "$$a \\oplus b \\oplus c = (a \\oplus b) \\oplus c = a \\oplus (b \\oplus c)$$" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + b + c == (a + b) + c == a + (b + c)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 5" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + b + c # ≜ max(a, b, c) ==> max(1, 3, 5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Neutral element $\\varepsilon$ for $\\oplus$\n", "\n", "$$a \\oplus \\varepsilon = \\varepsilon \\oplus a = a$$\n", "$$\\triangleq$$\n", "$$\\max(a,-\\infty) = \\max(-\\infty,a) = a$$" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + ε == ε + a == a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Equivalent to:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + mp0 == mp0 + a == a" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "((1, ., .), (1, 1), (1, 1))" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(a, mp0, ε), (a + mp0, a + ε), (mp0 + a, ε + a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that `0` is neutral for positive numbers:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + 0 == 0 + a == a" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1, 0, 1)" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a, 0, a + 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### $\\oplus$ is idempotent" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 1" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a + a # ≜ max(a, a) ==> max(1, 1) == 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Max-Plus Operator $\\otimes$\n", "\n", "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$." ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 4" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * b # ≜ a + b ==> 1 + 3 == 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Commutativity of $\\otimes$\n", "\n", "$$a \\otimes b = b \\otimes a$$\n", "$$\\triangleq$$\n", "$$a + b = b + a$$" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * b == b * a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Associativity of $\\otimes$\n", "\n", "$$a \\otimes b \\otimes c = (a \\otimes b) \\otimes c = a \\otimes (b \\otimes c)$$" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * b * c == (a * b) * c == a * (b * c)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 9" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * b * c" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Neutral element $e$ for $\\otimes$\n", "\n", "$$a \\otimes e = e \\otimes a = a$$\n", "$$\\triangleq$$\n", "$$a + 0 = 0 + a = a$$" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * mpe == mpe * a == a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Equivalent to:" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * mp1 == mp1 * a == a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Absorbing element $\\varepsilon$ for $\\otimes$\n", "\n", "$$a \\otimes \\varepsilon = \\varepsilon \\otimes a = \\varepsilon$$\n", "$$\\triangleq$$\n", "$$a -\\infty = -\\infty + a = -\\infty$$" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * ε == ε * a == ε" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Equivalent to:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * mp0 == mp0 * a == mp0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By convention:\n", "\n", "$$+\\infty \\otimes \\varepsilon = \\varepsilon \\otimes +\\infty = \\varepsilon$$" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) ." ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mptop * mp0 # FIXME shall return mp0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### $\\otimes$ is not idempotent" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 2" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a * a # ≜ a + a ==> 1 + 1 == 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Distributivity of $\\otimes$ over $\\oplus$\n", "\n", "$$a \\otimes (b \\oplus c) = (a \\otimes b) \\oplus (a \\otimes c)$$\n" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(a + b) * c == (a * c) + (b * c) # ==> max(a, b) + c ==> max(a + c, b + c) " ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 8" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(a * c) + (b * c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Power operator\n", "\n", "In Max-Plus algebra the power operator behaves like a multiplication in classical algebra:" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 10" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP(2)^5 # ==> 2 * 5" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 0" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP(2)^0 # ==> 2 * 0" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) -2" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP(2)^-1 # ==> 2 * -1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Instead of `^-1` we can also call the function `inv()` :" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) -2" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "inv(MP(2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Max-Plus column vector, Max-Plus matrices (dense and sparse) ¶\n", "\n", "What we have just seen for sclairs is also applicable to vectors, matrices whether dense (full) or sparse. Note that this toolbox uses internally using SparseArraysfor sparse matrices and vectors.\n", "\n", "### Building Max-Plus Dense Column Vectors" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5-element (max,+) vector:\n", " 1\n", " 2\n", " 3\n", " 4\n", " 5\n" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP(1:5)" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5-element (max,+) vector:\n", " 1\n", " 1.5\n", " 2\n", " 2.5\n", " 3\n" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP(1:0.5:3)" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element (max,+) vector:\n", " 1\n", " 2\n", " 3\n" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP([1, 2, 3])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Building Max-Plus dense matrices\n", "\n", "As with sczlairs, contamination of Max-Plus numbers on `Int64` and `Float64` numbers also works on elements of dense and sparse matrices:" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 1 2\n", " 3.5 4\n" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[MP(1) 2; 3.5 4.0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`MP(1)` of type `MP` has contamined the classical integers `2`, `3.0` and `4` to `MP` numbers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here's another more elegant way to write it:" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 1 2\n", " 3 4\n" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP([1 2; 3 4])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Another example of contamination of Max-Plus numbers:" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 3 1\n", " 6 1\n" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "f = 3; a = MP(1)\n", "[f a\n", " f + f a + a]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`f + f` being og `Int64` the classic addition was made before the promotion in numbers `MP`. On the other hand, `a + a` being `MP` it is the addition (max, +) which was used. Finally all the elements of the matrix are of type `MP`.\n", "\n", "In the following example, $\\varepsilon$ rendered the following matrix implicitly `MP`:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " . 2\n", " 3.5 4\n" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[ε 2; 3.5 4]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Building of Max-Plus sparse matrices\n", "\n", "Contamination also works on sparse matrices.\n", "\n", "A sparse matrix is a matrix containing many zeros. Its internal structure is designed not to keep these zeros in memory (except in Julia if they are explicitly given). In classical algebra the zeros are 0 (for integers) or 0.0 (real) but in Max-Plus they have the value $-\\infty$ and therefore a Max-Plus sparse matrix does not store $\\varepsilon$. Let remind you that Julia is based on functions `zero()` et `one()` to redefine these elements and therefore sparse matrices do not store ples `zero()` element (warning the `SparseArrays.sparse` API until Julia version 1.8 included stay have unfixed bugs where `0` are confused with `zero()`).\n", "\n", "Sparse matrices are essential for applications that often require large sizes. For example in the calculation of the longest path in a road network, the size of the matrix will be the number of nodes, the number of non-zero elements (the number of roads joining 2 nodes) will grow linearly with this size, then that the number of matrix coefficients increases as the square of the size.\n", "\n", "To create a Max-Plus hollow matrix, several choices:\n", "- either from an initially empty sparse matrix, like the function `mpzeros` that we will see later.\n", "- either from a full matrix with the function `SparseArrays.sparse` coupled with the constructor `MP`.\n", "- or from three vectors and the function `MP`: a vector of the data to be stored and two vectors indicating the indexes of these data in the matrix." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In any case, it is important to import the correct module `using SparseArrays`." ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show (max,+) -Inf and (min,+) +Inf as ." ] } ], "source": [ "using SparseArrays;\n", "set_tropical_display(1);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### From a full matrix" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) sparse matrix with 3 stored entries:\n", " [1, 1] = 1\n", " [1, 2] = 2\n", " [2, 2] = 4" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = MP(sparse([1 2; 0 4]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) sparse matrix with 3 stored entries:\n", " [1, 1] = 1\n", " [1, 2] = 2\n", " [2, 2] = 4" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = sparse(MP([1 2; -Inf 4]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "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:" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "([1, 1, 2], [1, 2, 2], MP[1, 2, 4])" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "i,j,d = findnz(S)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Explicit sparse construct\n", "\n", "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:**" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) sparse matrix with 3 stored entries:\n", " [1, 1] = 42\n", " [2, 2] = 0\n", " [3, 3] = 5" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = MP(sparse([1; 2; 3], [1; 2; 3], [42; 0; 5]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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 Max-Plus algebra ($\\varepsilon$ equal $-\\infty$) which has not been deleted." ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) sparse matrix with 3 stored entries:\n", " [1, 1] = 42\n", " [2, 2] = .\n", " [3, 3] = 5" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = sparse([1; 2; 3], [1; 2; 3], MP([42; -Inf; 5]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is a behavior Julia intended for more flexibility as you can call `dropzeros` to remove them:" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) sparse matrix with 2 stored entries:\n", " [1, 1] = 42\n", " [3, 3] = 5" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dropzeros(S)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For this, the constructor`MP(I,J,Tv)` has been added: it calls `dropzeros(sparse(I,J,Tv))` in order to remove explicit zeros:" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) sparse matrix with 2 stored entries:\n", " [1, 1] = 0\n", " [3, 3] = 5" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = MP([1; 2; 3], [1; 2; 3], MP([0; -Inf; 5]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Conversion from Max-Plus matrices to classical algebra \n", "\n", "As seen previously for scalars, we may want to convert a Max-Plus matrix into a classical matrix (+,*) :" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "scrolled": false }, "outputs": [ { "data": { "text/plain": [ "2×2 Matrix{Float64}:\n", " 4.0 0.0\n", " 7.0 -Inf" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([4 0; 7 -Inf])\n", "plustimes(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Also works for sparse matrices:" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) sparse matrix with 0 stored entries" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = spzeros(MP,2,2)" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 SparseMatrixCSC{Float64, Int64} with 4 stored entries:\n", " -Inf -Inf\n", " -Inf -Inf" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plustimes(Z)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We may want to go from a Max-Plus sparse matrix to a full matrix in classical algebra:" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Matrix{Float64}:\n", " -Inf -Inf\n", " -Inf -Inf" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Matrix(plustimes(Z))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Converting a sparse matrix to a full matrix: \n", "\n", "All three functions produce the same result:" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "(MP[. .; . .], MP[. .; . .], MP[. .; . .])" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "full(Z), dense(Z), Matrix(Z)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Construction of Max-Plus sparse column vectors\n", "\n", "Just like sparse matrices several ways to do it. Preserving the `zero()`s:" ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element SparseVector{MP, Int64} with 2 stored entries:\n", " [1] = 0\n", " [3] = ." ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sparsevec([1, 3], MP([0, -Inf]))" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element SparseVector{MP, Int64} with 2 stored entries:\n", " [1] = 0\n", " [3] = ." ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP(sparsevec([1, 3], [0, -Inf]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Where by removing the zeros:" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "scrolled": false }, "outputs": [ { "data": { "text/plain": [ "3-element SparseVector{MP, Int64} with 1 stored entry:\n", " [1] = 0" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP([1, 3], [0, -Inf])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Construction of usual Max-Plus matrices\n", "\n", "### Dense Identity Matrix\n", "\n", "For example of size 2 $\\times$ 2 :\n", "\n", "$$\\left[\n", "\\begin{array}{*{20}c}\n", "e & \\varepsilon \\\\\n", "\\varepsilon & e \\\\\n", "\\end{array}\n", "\\right]$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since Julia v1.0, the function `eye` no longer exists and has been replaced by `LinearAlgebra.I` but this toolkit adds their equivalent `eye(MP,...)` and `mpI` :" ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "UniformScaling{Bool}\n", "true*I" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using LinearAlgebra\n", "I" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 .\n", " . 0\n" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Matrix{MP}(I, 2, 2)" ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "UniformScaling{MP}\n", "0*I" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mpI" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 .\n", " . 0\n" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Matrix(mpI, 2, 2)" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "(true, true)" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Matrix(mpI, 2, 2) == eye(MP,2,2), Matrix{MP}(I, 2, 2) == eye(MP,2,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The function `eye` is easier to type:" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 .\n", " . 0\n" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "J = eye(MP,2,2)" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 .\n", " . 0\n" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "J = eye(MP,2) # Equivalent to eye(MP, 2,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Size 3 $\\times$ 2:" ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×2 (max,+) dense matrix:\n", " 0 .\n", " . 0\n", " . .\n" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "J = eye(MP,3,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Build an identity matrix (max,+) from the dimensions of an existing (max,+) matrix:" ] }, { "cell_type": "code", "execution_count": 74, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 .\n", " . 0\n" ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([1.0 -Inf; 0.0 4])\n", "J = eye(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Dense Column Matrices/Vector filled only with $e$ :\n", "\n", "For example matrix of size 2 $\\times$ 2 :\n", "\n", "$$\\left[\n", "\\begin{array}{*{20}c}\n", "e & e \\\\\n", "e & e \\\\\n", "\\end{array}\n", "\\right]$$" ] }, { "cell_type": "code", "execution_count": 75, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 0\n", " 0 0\n" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "O = ones(MP,2,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Column vector of 2 elements:" ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " 0\n", " 0\n" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "O = ones(MP,2) # /!\\ Is not equivalent to ones(MP,2,2) /!\\" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Build a matrix of `e` (max,+) from the dimensions of an existing (max,+) matrix:" ] }, { "cell_type": "code", "execution_count": 77, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 0\n", " 0 0\n" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([1.0 -Inf; 0.0 4])\n", "J = ones(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Spasre matrices filled with $\\varepsilon$ :\n", "\n", "$$\\left[\n", "\\begin{array}{*{20}c}\n", "\\varepsilon & \\varepsilon \\\\\n", "\\varepsilon & \\varepsilon \\\\\n", "\\end{array}\n", "\\right]$$\n", "\n", "**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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Dense Matrix" ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " . .\n", " . .\n" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = zeros(MP,2,2)" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "2×3 (max,+) dense matrix:\n", " . . .\n", " . . .\n" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = zeros(MP,2,3)" ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " .\n", " .\n" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = zeros(MP,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Sparse Matrix" ] }, { "cell_type": "code", "execution_count": 81, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) sparse matrix with 0 stored entries" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = spzeros(MP,2,2)" ] }, { "cell_type": "code", "execution_count": 82, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×3 (max,+) sparse matrix with 0 stored entries" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = spzeros(MP,2,3)" ] }, { "cell_type": "code", "execution_count": 83, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element SparseVector{MP, Int64} with 0 stored entries" ] }, "execution_count": 83, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = spzeros(MP,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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 `MP`)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Dense Matrices filled with $\\varepsilon$ :\n", "\n", "You must use the function `full` or the synonymous function `dense`." ] }, { "cell_type": "code", "execution_count": 84, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " . .\n", " . .\n" ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z = full(zeros(MP,2,2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Diagonal matrices\n", "\n", "Dense:" ] }, { "cell_type": "code", "execution_count": 85, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) dense matrix:\n", " 1 . .\n", " . 2 .\n", " . . 3\n" ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" } ], "source": [ "diagm(MP([1,2,3]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sparse:" ] }, { "cell_type": "code", "execution_count": 86, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) sparse matrix with 3 stored entries:\n", " [1, 1] = 1\n", " [2, 2] = 2\n", " [3, 3] = 3" ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" } ], "source": [ "spdiagm(MP([1,2,3]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Elementwise operator on matrices\n", "\n", "Julia allows you to iterate over the elements of an array, matrix, vector and apply an operation to each of them. For instance:\n", "\n", "$$4 \\oplus \\left[\n", "\\begin{array}{*{20}c}\n", "2 \\\\\n", "8\\\\\n", "\\end{array}\n", "\\right] = \\left[\n", "\\begin{array}{*{20}c}\n", "4 \\oplus 2 \\\\\n", "4 \\oplus 8\\\\\n", "\\end{array}\n", "\\right] = \\left[\n", "\\begin{array}{*{20}c}\n", "4 \\\\\n", "8\\\\\n", "\\end{array}\n", "\\right]$$" ] }, { "cell_type": "code", "execution_count": 87, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 1 2\n", " 3 4\n" ] }, "execution_count": 87, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([1.0 2; 3 4])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We apply the max(2, ) function to each of the elements that will be contaminated in Max-Plus number:" ] }, { "cell_type": "code", "execution_count": 88, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 2 2\n", " 3 4\n" ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "2 .+ A" ] }, { "cell_type": "code", "execution_count": 89, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 2 2\n", " 3 4\n" ] }, "execution_count": 89, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A .+ 2.0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We apply the function +(2, ) on each of the elements:" ] }, { "cell_type": "code", "execution_count": 90, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 3 4\n", " 5 6\n" ] }, "execution_count": 90, "metadata": {}, "output_type": "execute_result" } ], "source": [ "2 .* A" ] }, { "cell_type": "code", "execution_count": 91, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 3 4\n", " 5 6\n" ] }, "execution_count": 91, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A .* 2.0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Addition and matrix product \n", "\n", "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.\n", "\n", "### Matrix addition\n", "\n", "$$\\begin{bmatrix}\n", "1 & 6 \\\\\n", "8 & 3\n", "\\end{bmatrix} \\oplus \\begin{bmatrix}\n", "2 & 5 \\\\\n", "3 & 3\n", "\\end{bmatrix} = \\begin{bmatrix}\n", "1 \\oplus 2 & 6 \\oplus 5 \\\\\n", "8 \\oplus 3 & 3 \\oplus 3\n", "\\end{bmatrix} = \\begin{bmatrix}\n", "2 & 6 \\\\\n", "8 & 3\n", "\\end{bmatrix}$$" ] }, { "cell_type": "code", "execution_count": 92, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 2 6\n", " 8 3\n" ] }, "execution_count": 92, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP([1 6; 8 3]) + MP([2 5; 3 3])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Matrix Product\n", "\n", "$$A=\\begin{bmatrix}\n", "4 & 3 \\\\\n", "7 & -\\infty\n", "\\end{bmatrix}\\;,$$\n", "\n", "$$A \\otimes A = \\begin{bmatrix}\n", "4 \\otimes 4 \\oplus 3 \\otimes7 & 4 \\otimes 3 \\oplus 3 \\otimes -\\infty \\\\\n", "7 \\otimes 4 \\oplus -\\infty \\otimes 7 & 7 \\otimes 3 \\oplus -\\infty \\otimes -\\infty\n", "\\end{bmatrix}\\; = \\begin{bmatrix}\n", "10 & 7 \\\\\n", "11 & 10\n", "\\end{bmatrix}\\; = A^2.$$" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 10 7\n", " 11 10\n" ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([4 3; 7 -Inf])\n", "A * A" ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A * A == A^2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Also works on sparse dies:" ] }, { "cell_type": "code", "execution_count": 95, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) sparse matrix with 3 stored entries:\n", " [1, 1] = 4\n", " [2, 1] = 7\n", " [1, 2] = 3" ] }, "execution_count": 95, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([4 3; 7 -Inf])\n", "sparse(A)" ] }, { "cell_type": "code", "execution_count": 96, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 96, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A * sparse(A) == sparse(A) * A == sparse(A) * sparse(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Power of a Max-Pus matrix:" ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 24 23\n", " 27 24\n" ] }, "execution_count": 97, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A^5" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 .\n", " . 0\n" ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A^0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Also applies to compatible rectangular dies:" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " 8\n", " 13\n" ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP([2 0; mp0 5]) * MP([2; 8])" ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1×2 (max,+) dense matrix:\n", " 4 13\n" ] }, "execution_count": 100, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MP([2 8]) * MP([2 0; mp0 5])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let’s check that the identity matrix $I$ is indeed neutral:\n", "\n", "$$ A \\otimes I = I \\otimes A = A$$" ] }, { "cell_type": "code", "execution_count": 101, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 101, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([4 3; 7 -Inf])\n", "A * eye(MP, 2,2) == eye(MP, 2,2) * A == A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let’s check the zero matrix is indeed absorbing:" ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 102, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A * zeros(MP, 2,2) == zeros(MP, 2,2) * A == zeros(MP, 2,2)" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A + zeros(MP, 2,2) == zeros(MP, 2,2) + A == A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Displaying Max-Plus matrices in LaTeX" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "From a Max-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." ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show -Inf, +Inf and 0.0" ] } ], "source": [ "set_tropical_display(0)" ] }, { "cell_type": "code", "execution_count": 105, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\\left[\n", "\\begin{array}{*{20}c}\n", "0 & -\\infty \\\\\n", "-\\infty & 0 \\\\\n", "\\end{array}\n", "\\right]\n" ] } ], "source": [ "LaTeX(stdout, eye(MP, 2,2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Once this code $\\LaTeX$ compiled, it will display:\n", "\n", "$$\\left[\n", "\\begin{array}{*{20}c}\n", "0 & -\\infty \\\\\n", "-\\infty & 0 \\\\\n", "\\end{array}\n", "\\right]$$\n", "\n", "Whereas:" ] }, { "cell_type": "code", "execution_count": 106, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show (max,+) -Inf and (min,+) +Inf as . and 0.0 as e" ] } ], "source": [ "set_tropical_display(2)" ] }, { "cell_type": "code", "execution_count": 107, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\\left[\n", "\\begin{array}{*{20}c}\n", "e & . \\\\\n", ". & e \\\\\n", "\\end{array}\n", "\\right]\n" ] } ], "source": [ "LaTeX(stdout, eye(MP, 2,2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Once this code $\\LaTeX$ compiled, it will display:\n", "\n", "$$\\left[\n", "\\begin{array}{*{20}c}\n", "e & . \\\\\n", ". & e \\\\\n", "\\end{array}\n", "\\right]$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Works with sparse matrices:" ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "I will show (max,+) -Inf and (min,+) +Inf as ." ] } ], "source": [ "set_tropical_display(1)" ] }, { "cell_type": "code", "execution_count": 109, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\\left[\n", "\\begin{array}{*{20}c}\n", ". & . \\\\\n", ". & . \\\\\n", "\\end{array}\n", "\\right]\n" ] } ], "source": [ "LaTeX(stdout, zeros(MP, 2,2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Once this code $\\LaTeX$ compiled, it will display:\n", "\n", "$$\\left[\n", "\\begin{array}{*{20}c}\n", ". & . \\\\\n", ". & . \\\\\n", "\\end{array}\n", "\\right]$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Trace of a Max-Plus Matrix\n", "\n", "This toolkit uses `using LinearAlgebra` to correct some functions such as trace and standard. The trace is the Max-Plus sum of the diagonal elements." ] }, { "cell_type": "code", "execution_count": 110, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 4" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([4 3; 7 -Inf])\n", "tr(A)" ] }, { "cell_type": "code", "execution_count": 111, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tr(A) == A[1,1] + A[2,2]" ] }, { "cell_type": "code", "execution_count": 112, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) dense matrix:\n", " 5 . 5\n", " . 6 3\n", " 11 12 11\n" ] }, "execution_count": 112, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = [5 mp0 5; mp0 6 3; 11 12 11]" ] }, { "cell_type": "code", "execution_count": 113, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 11" ] }, "execution_count": 113, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tr(A)" ] }, { "cell_type": "code", "execution_count": 114, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 114, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tr(A) == A[1,1] + A[2,2] + A[3,3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Norm of a Matrix\n", "\n", "It is defined as the difference between the largest and the smallest coefficient of the matrix." ] }, { "cell_type": "code", "execution_count": 115, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) Inf" ] }, "execution_count": 115, "metadata": {}, "output_type": "execute_result" } ], "source": [ "norm(A)" ] }, { "cell_type": "code", "execution_count": 116, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) Inf" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "norm(eye(MP, 2,2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Residuation of a Max-Plus Matrix\n", "\n", "It allows to calculate the largest sub-solution of $Ax\\leq b$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Eigenvalues of Max-Plus Matrix $A v = \\lambda v$\n", "\n", "The spectral of a matrix is the set of its eigenvalues. A square matrix $A \\in \\mathbb{R}_{\\varepsilon}^{n \\times n}$ Rn × nεhas an eigenvalue if there is a real numbe $\\lambda \\in \\mathbb{R}^{n}$ otand a vector $v \\in \\mathbb{R}_{\\varepsilon}^{n}$ if :\n", "\n", "$$A v = \\lambda v$$\n", "\n", "$v$ is called an eigenvector and $\\lambda$ eigenvalues." ] }, { "cell_type": "code", "execution_count": 117, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(MP[4.5, 4.5], MP[6.5, 4])" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = MP([3.0 7; 2 4])\n", "λ,v = mpeigen(S)" ] }, { "cell_type": "code", "execution_count": 118, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S * v == λ[1] * v" ] }, { "cell_type": "code", "execution_count": 119, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S * v == λ[2] * v" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "These spectral elements give the asymptotic behavior of Max-Plus linear dynamical systems $x_n=A\\otimes x_{n-1}$ which grow linearly at a rate given by the eigenvalue which is unique as soon as the adjacency graph of the matrix is strongly connected:" ] }, { "cell_type": "code", "execution_count": 120, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " 1\n", " 0\n" ] }, "execution_count": 120, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = MP([1; 0])" ] }, { "cell_type": "code", "execution_count": 121, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×4 (max,+) dense matrix:\n", " 1 7 11 16\n", " 0 4 9 13\n" ] }, "execution_count": 121, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[x S*x S^2*x S^3*x]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In Scilab's Max-Plus toolbox, they are obtained either by the `karp` or functions `howard`. In this toolbox Julia only `howard` is implemented because its algorithm is faster (linear to the number of arcs) than the algorithm of `karp` ($O(mn)$)." ] }, { "cell_type": "code", "execution_count": 122, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.004724 seconds (45 allocations: 22.375 KiB, 99.21% compilation time)\n" ] }, { "data": { "text/plain": [ "MaxPlus.HowardResult(MP[0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001 … 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001], MP[0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001 … 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10 … 91, 92, 93, 94, 95, 96, 97, 98, 99, 100], 98, 1)" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# FIXME Matrice 10000x10000 => Max iteration reached\n", "S = MP(sprand(100,100,0.0005))+0.001*sparse(eye(MP, 100,100))\n", "@time howard(S)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The function `mpeigen()` relies on `howard` and returns only the eigenvalues and vectors. The function `howard` returns more information:" ] }, { "cell_type": "code", "execution_count": 123, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "MaxPlus.HowardResult(MP[4.5, 4.5], MP[6.5, 4], [2, 1], 1, 2)" ] }, "execution_count": 123, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = MP([3.0 7; 2 4])\n", "r = howard(sparse(S))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The graph corresponding to the matrix `S` is:" ] }, { "cell_type": "code", "execution_count": 124, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAASsAAACNCAIAAABg9MukAAAAA3NCSVQICAjb4U/gAAAAGXRFWHRTb2Z0d2FyZQBnbm9tZS1zY3JlZW5zaG907wO/PgAAH3pJREFUeJzt3Xs8VOnjB/AjGRqXTMbImEHuQ1ghUklIJUpFd923y3bRZb+727Zlv7p8v21t1rcU2u4JoZpUm3Jt04XRhKimXEpC4zIYjLmd3+vnvNarVxcxM8eZGc/7j17jOOd5HqfXZ871eR4VGIYhAAAwMgSrigEAAAkEAIyBYyAAYAkkEACwBBIIAFgCCQQALIEEAgCWQAIBAEsggQCAJZBAAMASSCAAYAkkEACwBBIIAFgCCQQALIEEAgCWQAIBAEsggQCAJZBAAMASSCCg8Nhs9pIlSyDFJO8JFIvFcXFxs2fPDg0NLSgowLo5gDz69ttvc3NzIcUk7wn86aef2traVqxYUV9f7+3tXVdXh3WLAPly8uRJKpUKKayhkByrra319fX18/ODIGjMmDEmJiYsFmvkyJFYtwuQFywWq6mpyd3d/erVq/3dViQSlZSUPHz4sLq6uqGhQVdX18TExMvLy9bWFlK4BPL5/JSUlMzMzKdPn3K53GHDhlGpVGdn58mTJ7u7u6uqqkpWrGE35LO6urqRkZGrq6tMGgwoAYFAENUtKSmpXxvm5+efPXv20qVLJBJp/PjxJiYmzs7OLS0tTCbz4MGDZDJ5z5493t7e0MCApZaYmEihUKZNm3bs2LGHDx+WlZUVFBSkpKR8//33Tk5OFApl586d7969k6aKjo6OBQsWMBgM6VsLKI19+/axWCwYhi9cuEChUPqySUZGhpeXl5mZ2f79+9+8efPpCiKRKDk5mUqlhoeHwwNC2gRu27bN2to6Pz//Sys8ffo0LCxMT09v8+bN79+/l6AKJpMZEBCgqqpKIBBKSkqkay+gJO7evXvixAnkc18S+OrVq5kzZ1pZWV24cEEgEPS+8vv3711cXPbu3QvLeQL/85//ODs7t7a2fnXN+vr6LVu2kEik48ePi0QiCerKzc0lEokhISEStRRQNpMmTZo7d25wN1dX12HDhgUHB1+6dOnTNUUiUWRkJJFI/O9//9vV1dXH8mtraykUyr1792CUqUg8an1paam3t/eTJ096LtW+qqSkZP369Tgc7ty5cxQKpb81/vzzzzdv3nzy5En/Gwsom/T0dA6Hg3y+f//+hQsXjh07Nnr0aDs7uw9Xq62tXbx4sUAgOHv2rJmZWb+qSEhIiIyMzM/Ph1AlcXYDAwOjo6P7u5VQKNy3b5+BgcH169f7u218fPy8efP6uxWg9BK770R8uvzBgwcUCiUiIkIoFEpQrFgstra2fvDgAYwmCRP4+vVrIpHY0dEh2ebIrjlw4EDvqwkEgqqqqp4fV69e3csFJzBoJX4ugfHx8QYGBjdu3JCm5AMHDnz33XewHCbw8OHDa9askabit2/furq6rly5spfvJxaLhcPh/Pz8Tpw4cfz48ezsbGlqBAaP33//3cTEpLS0VMpymEymra0tLIfXgTNnzgwNDQ0JCZHmBLijo2Pu3Ll4PP7ixYvq6uqfXYfL5VZWVpqYmOjo6EhTFzB47N69+/Lly7du3ZLgXsNHRCIRgUCorq4ePnw4JFdvpT1+/NjNzU3KuvF4PJ1OV1NTmz17dldX12fX0dLSsre3B/ED+igiIuLKlSvZ2dnSxw+CIFVVVVNT09evX0OokSSBPB6vsbFRJn8hDoeLj4/X0tKaP3++QCCQvkBgMDt06NClS5cyMzP19fVlVSaFQnn79i0kVwmsr68nkUhDhsjmrW5VVdX4+HgYhlesWAEm9AUkFh8fHx0dffv2bRKJBMkOHo/v7OyEUCNJijo7O/F4vAwboaamlpSUVFlZuWvXLhkWCwweWVlZ27dvv3HjBplMlm3JampqqJ6dSZJAPp+Pw+Fk2w4NDQ06nZ6UlHTmzBnZlgwovcrKysWLFycmJqLRraGzs3PYsGGQXPWN0NTUbG9vl3lTiETi9evXPT09R48e7eLiIvPyAaXU0dExZ86cn3/+2cvLC43yORwOgUCA5OoYOHz48NbWVhQaA1lbW8fExISEhDQ2NqJRPqB8NmzY4OjouGnTJpTKr6+vJxKJKBUOQZAkzwPFYrGmpiaHw/nSQzwp/fjjj2VlZdeuXVNRUUGjfEBpJCQkREREMBgMTU1NNMoXiUTa2tpNTU0aGhpydAwcMmQIhUJ58+YNhI69e/fW1dXFxsaiVD6gHCorK7ds2ZKQkIBS/CAIevPmjb6+Pnrxk/yJvJmZ2atXryB0qKmpXbhwYffu3SwWC6UqAEUHd78n/K9//eubb75BrxYmk+no6Ihe+ZIn0NHREdVeQtbW1rt37161apVYLEavFkBxnTx5ksvlbt26FdVaCgoK0B4YRcIEjhkzprCwEELTd999JxKJTpw4gWotgCKqra3duXPnn3/+KfEQRH304MED6d++7J2Eb2ZXVFRMnDixpqYGQtPTp0+9vb2Li4vB+GjAh9asWUMgEA4cOAChicvlksnkuro62b5/IrPrQBwO9+zZMwhNo0ePXrFixe7du1GtBVAsFRUVdDp9x44daFeUnZ3t5uaGavykGrHXx8cnMzMTQtmOHTvodDraUQcUyLFjx1asWKGrq4t2RWlpadOnT0e7FsnHibl8+XJMTMzt27chlEVGRt6/fz85ORntigD5JxKJDA0NHz16NGrUKFQrEgqFZDK5oKDAxMRETo+B06ZNy8/Pb2pqglC2du3au3fvovfwA1AgeXl5VCoV7fghp6Dm5uZox0+qMbPxeLyvry+dTl+xYoVMm/SZitauXRsZGRkdHQ0pHbFYXF9f//79ey6X297e3tLS0tbW1tHR0d7e3tzc/OGaOBwOefQ8dOhQbW1tHR0dfDcCgaCtrU0mk7W0tCBlR6fTZ82aNQAVnTlzZtGiRQNQkeRnoRAEXblyJSoqKicnB0JZfX09jUarrKxEb7AAtHG5XBaL9eLFi5cvX9bU1NR2e/fuHZvN1tPTI5FIWlpampqaurq6yAfk84fv5fH5fOSFeIFAwOVyW1paOrpxOJyWlpba2loYhkd209fXNzIyMjExMf+HtrY2pBQsLCxSU1PRfkre2NhoaWlZXl6O6jvZMkigQCCgUql5eXnm5uYQyoKDg6dPn75q1SpIEfB4vKKiIgaD8fTpU1a3pqYmq38YGRmRyeSRI0caGRkZGBgMHSqb2Tva29vrurHZ7JqamqqqqvJuFRUVeDzezMyMRqM5dPvmm29GjBgBKZqXL1/6+Pig9zpkj8OHDxcVFZ09exbtiqRNIARB27dvV1dX379/P4QyOp1++PBhuZ0mTiwWFxUV5efnM7qxWCwbGxtnZ2dHR0dra2srKysqlYrhi+b19fXl5eWlpaXF/9DS0nJwcBgzZoyHh8e4ceMG4Nai9M6fP3/jxo3ExERUaxEKhZaWlklJSWPHjoXkP4Hl5eUeHh5VVVWo9mJEjrdGRkb5+fmmpqaQ3CgrK8vKysrOzs7JyRk5cqSbm5tLN0dHR5Q6jshKVVVVcXExg8HIy8tjMBjGxsYeHh7jx4/39PSUqz38oY0bN5qbm6P9JlpSUtKxY8cG7Lte2gRCEBQUFOTv779mzRoIZStXrnR2dt6wYQOEKS6Xe+vWLTqdnpmZqaGh4d1t8uTJfR+9v+8OHTr0UVfJn376SeYXw0KhsLi4OC8v7/79+9nZ2bq6ulOnTp02bdqkSZPQfh7dL66urlFRUR4eHhBqYBh2dXUNDw8PDAyEFCWBubm5a9euLS0tRfslvUuXLp0/fz4tLQ3CApvNTktLu3Llyt27dz08PIKCgvz8/FC9Lf7s2bMpU6Z4eHggh1MOh1NUVIT2VRAMw0+ePLl9+3Z6enphYaGbm9vMmTPnzJkj8/FX+qurq0tPT4/NZqN6tkWn0//9738XFhYO3CWDTMb99fT0RMY7Q1VTU5OOjg6Px4MHEJfLPXv2rLe3t66u7rx58y5evMjhcAam6jNnzrS1tfX8GBcXt2XLFngAtbW10en05cuX6+npTZgwISoqqrq6GsZIcXEx2sNXi0QiR0dHKQe67y/ZJDAjI8PGxkay+TH6Zdy4cbm5uWjXgszacffu3ZUrVxIIhICAgJSUlM7OThhTU6ZM+fvvvzGpms/n37x5c+XKlUQicfz48SdPnvzwq2FgpKSkBAUFoVrF+fPnx48fDw8s2SQQhuGJEyeePn0aRtnGjRsjIyNRrYLD4Rw6dMjCwsLOzu7gwYPIczbMsdlsCoUi2dSLMsTn869fvz579uwRI0asXr36/v37A1b1vn37fvzxR/TK53K5VCp1IP8iGSewsLDQ0NCwL7N5SuPkyZNLly5FqfCXL19u2rRpxIgRixYtevjwISxP4uLi1q9fD8uNurq63377zdra2s7OLiYmRuJZtPouNDQU1a/4X375JTQ0FB5wMksgDMOLFy/etWsXjKbHjx+PHj1a5sXeu3cvMDCQRCL9/PPPNTU1sPyZMmVKRkYGLH9ycnJmzZpFIpF2795dV1eHXkUTJ05E7wLk1atXRCLx7du3sEIn8M2bN0Qi8cWLFzBqOjs71dXVxWKxrAp8+PDh1KlTR40aFRsbOwBf5JJpaGgwMDD46uznGGKxWOvXr0dOTcvLy9GowsLCgsVioVGyWCyePHny4cOHYSzIMoEwDB89enTcuHF8Ph9GzYgRI9hstvTlFBYWBgQEGBsbx8bGotpg6Z04cWLlypWw3GtoaPj111+JROLatWtlftdUS0sLpWucmJgYd3f3AbiPOBAJFIvFAQEBmzZtglFjZ2dXUlIiTQnV1dULFy6kUChHjx4d4GcbkvHz8xvgW+TSaGxs/Omnn/T09MLCwurr62VSZmtrq6amJoyCiooKfX196ef6lJcEIvcSbWxs/vjjDxgdPj4+d+7ckWzbzs7Offv2EYnE8PDw9vZ2WBE0NDTo6el1dXXBCqWuri4sLIxIJB48eFD6UwwWi2VhYQHLGp/Pd3d3R/vu+kAnELkgHDVqVFxcHBqFz507NyUlRYIN6XS6mZnZ3LlzKysrYcXB4/HevXsHK6aXL1/OmDGDRqNJ/KWJyM3NnTBhAixrP/zwQ0BAgAxvK8hLAmEYLi8vp1Kp58+fl3nJQUFBV65c6dcmDQ0N8+fPt7GxyczMlHl7gK+6du0a8t0n8X3mpKSkkJAQ2e7q1NRUY2NjmdxTkIZsZuH8lJmZ2e3bt3/88UeZz0YmFAr71aGOTqc7ODhQqVQmk+nt7S3bxgB9ERgYWFpaamdnN2bMmISEBAl2Wl1dnWxHrGQwGOvXr7969Sqqs7L0Car5fv78uZmZ2d69e2VY5vTp02/evNmXNTkcTmhoqKWl5b1792TYAEBiDAbD1tZ23rx5DQ0N/dpwz549v/zyi6z2fFVVFYVCodPpsBxA6xiIsLa2zsvLu3z58vr160UikUzK5HK5fZmpo6ioyMXFRVtb+8mTJ+PHj5dJ1YCUnJ2dCwsLqVSqo6Njv4a65Hb/p/P5/OjoaCkHB6uurvbx8dmxY8fMmTMheTAAKW9tbfXz8wsICGhpaZG+NCMjozdv3vS+zunTp/X19RMSEqSvDkBDVlYWmUz+7bffer8LUlFRkZuby2AwQkNDFy5caGxsjMPhpHlwV11dbWFhgd6NegkMRAKR274bN260sbF5/vy5NOV0dHQMGzaslxeUeTze6tWraTRaWVmZNBUBaKuurnZzcwsJCemlm0VVVVXP+Y6BgQEEQVZWVhLXWFJSYmpqiu2zB8wSiLhw4QKJRLp8+bLEJZSWltJotC/9trm52cvLKzg4eOD7zgAS4PF4a9assbOze/369ZfW6Zkcwt3dHRmlVrJdfefOHRKJhMbNeUVKIAzDjx49olKpO3bskOwpbU1NzdmzZz/7q+rqant7+y1btmDehQfol6ioKGNj4y+9lSIQCJycnCAImjRpEjJndX93r1gsPnjwoKGhYV5enhz+10CYdHULDAx0cXGR/kXbngvL0tJSExOT8PBwWTQQGGjx8fEGBgZfSkh+fr6qqqqDgwMycE6/Sn7//r2/v7+bm1tFRQUslzBIIPK1dOTIkU/PCvp1kX3t2rXNmzcj4xeMHDny4sWLKLQUGCA3b94kkUhZWVmf/e2GDRs0NDRwOFy/LmFSUlLIZPKuXbvkuVsJNglEFBUV2draLlmypOdQ9sMPP/TxrWuxWPzNN9/gcLj09HQymXzp0iWUGwugLjc3l0Qi5efnf/qrlpYWCoVCo9GePHnSl6KqqqoCAgLs7Ozk/1EwlglE7m2uW7fO3Nz8wYMHXV1d+vr6Y8aM6cslYlJSEnKBrqWlJYeX14Bkbt++TSaTP3tNmJqa6unp+dUHWu3t7cjL9/v27ZPzTmdykUDE5cuXDQ0NZ8yYgYQqIiKi9/WFQiGNRoMgSFVV1cDAYNKkSVI+5ADkx/nz542NjT97d3Tnzp29bCgQCOLi4oyMjObPn49SL2GlTSByj5RMJiMjjqqpqTGZzF5WPnXqFDKXkI6ODhJaPB6fmJg4gO0FUHTw4EFXV9dPu272PojBvHnzvL29CwoKFOv/Ri4SeOvWLWSSGm1tbRcXFwiCbG1tvzQ6IJ/PNzMz09HR0dDQ+P8JEIcM8fX1vXTpksSvShQXF0dERCA3dfqOyWQeOHAAHqz6u9NEItGxY8dmz569cuVKBoPx1fVDQkLWrVvXryY1NTXBCgj7BDY0NISEhPQczVRUVHx9ffF4/I4dOz67/tGjR6lUqqqqqo6Ozpo1a6R/96WpqWnKlCleXl59XJ/D4cTHxxsaGvZ9E+XT35327bffbt++PSIiwtraeujQoV8diq61tdXa2nowXOFjn0CEUChkMBjh4eHOzs4qKirm5ubW1tafDlDb2dk5ffp0e3v7PXv2cLlcWdW+bt26/sZpxYoVgzmB/dpp+fn5Pc+KWlpaRo4c2ZchJ0tKSk6dOgUrO9nMXCc9VVVV526//vprfX19erfjx487OTl92BOCxWLt3Lnzs30dOjo6amtrTU1NCwsLdXR0bGxsen7V2dlZXFysoqLi4OCAnLsieDxeQUHBpx3Pmpubnzx5QqFQLC0te2kwpPgGZqdpaGgsWLAA+ayjozN+/HgOh/PVto3uhnQeQE6OIGWEbu8kyRgYGCxdujQ+Pv7UqVNisfjDXzk4OHw2funp6VQqdefOnRs2bNi3b5+Dg8O1a9eQX/31119r1qwZOnQo0kk0OzsbWX7v3r2lS5ficLhbt271rIzMD/P777+/ffs2KCho8+bNkPIasJ1mb2//YX7YbLavr29fWlhfX79w4UICgTBixIjQ0FA2mw0pH1gRcLlcJpPZ+5QpEyZM8PX1Rd5+8Pb2njt3LjJekK6ubs84KwcOHCASiY2NjW1tbWQyuaeXk7+/P3JCVVlZOXHiRGRhamoqBEGPHz/+bHWrV69WgrPQAd5pyLNya2vrvgzN2tXVhbyJ1sPJyUkhHvH1izweAz8Ew3B4eLiurq6TkxOBQNi8eTOfz//smhoaGqampsgAFpaWlsi0ezdv3lRVVe2Z2W/BggUNDQ05OTmpqanDhg2jUqnIcmNjY+TDjRs3eDzerm4FBQXr1q3j8XiQ8hrgnSYWi8PCwpKTk/syA9n169eLi4s/XMJkMtPT0yHlIi/XgV8SExMTERGBfIZh+MiRI7q6uj1LvqTnnKempgYZ5hVZQqFQhg4dWldXV11draam9umGLBbLyspqz5490OAzADstKipq69at9vb2fWnPy5cv+7hQocn7MfDPP//8aMmJEyf6vrmlpaVAIHj+/Dnyo0AgEAqFdnZ2BALh9evX7e3tH61PIpGys7M//Ap/9OgRNMigtNNSUlJsbW2RTkbIhKRQr+zs7Pq4UKHJewLfv3//0ZLGxkahUPjpmsgVAvJZIBAgw9LMnDnT1NT09OnTyPLc3Fx3d3dPT09/f/+uri6k96dYLH79+jUy+khAQEBtbe2yZcvq6uoaGhr279//pYYJBIKP7hIpogHbaWlpacXFxUQisbCwkMFgxMbGFhQU9N626dOnfzRhtZeXVx9v4SgSWL4FBwd/1GAPD49PV8vKyho+fLiVlVV+fn5BQYGZmdnw4cORri7Pnj0bN25ceHj4uXPnvv32254bDHFxcZqami4uLgEBATNmzHB1dU1KSkKe+OPxeBUVFUNDw9TU1E/r4vF4V69epVKpeDz+6tWrzc3NsGIasJ32999/f/g8A7mG7EtH6tbW1s2bN5ubm1tYWGzbtk2GT4DlhwzmkUdVeXm5m5sbcocAgiBNTc2cnBzkzbV+aW5uVlNT09LS+nChUChks9mGhoYdHR14PP7D5XV1dWQyecgQeT9HQBWGOw3unqnO2dkZUnbynkAIgmprayMjI0tLSy0sLMLCwszMzLBuEYAufve4XnZ2dmFhYUq/rxUggcCg0tzcPGfOHBiGt2/fHhgYCCk7kEBAjlRWVs6YMeP9+/ccDuf58+cWFhaQslPI65zS0lIul4t1KwAZKygoGDdu3LNnz1pbW1VVVUeNGjUYdrFCJjA6OnrVqlXg/FmZ0Ol0Ly+v+vp6XV1dgUBga2urHO++K2cCIyMjq6qqDh06hHVDANmIi4sLDg7u6OhAumtAEISMQjIYKGQC1dXVU1NT//jjj4yMDKzbAsiAr69vTEzMrFmzcDgc8t4vSKC8o1AoiYmJS5Ys+eqrFYD8MzMzmzdv3qtXr/bv3+/o6IgMUwINDgp5DERMnDjx3LlzgYGBTCYT67YAUoFheNWqVZ6entu3b8/JyXFzcxs8CVT4pxHJyclbt27NysqysrLCui2AhMLCwphMZkZGBg6HgyCopaUFj8d/th+G8pH33klfFRIS0t7e7u3tnZaWhkzxASiW77///sGDB3fu3EHiB0HQ8OHDoUFDgc9Ceyxfvjw6Onrq1Kl//fUX1m0B+mfnzp2ZmZm3bt0aVKlTqrPQHvfu3QsODj506NCSJUuwbgvwdcg0IXfu3MnMzNTT0xu0u0x5EghBUFlZ2YwZM0JCQvbv34+MvADIp87OzmXLltXX11+5cmXEiBHQIKYMZ6E9bG1tGQzG06dPvb293717h3VzgM9rbGz08/NTUVFJT08f5PFTtgRCEKSnp3f9+vUpU6aMHTs2JycH6+YAH2MymWPHjvX19U1MTPyo2+4gBSupjIwMIyOjLVu2tLe3w4qvv/MuyCGxWBwZGUkikcBkjx9StmNgDx8fn6dPn3Z0dNjb2/cMOKu41q1bV15e7uTklJeX5+7urnDjRyFTlyckJNy/fz8kJATr5sgTWNldu3bNyMho06ZNvQ/4K88km3dBfqSmphoZGf3yyy/yPJs0VpT2GNgjMDCwpKSkq6vLxsYmLi4OGQ5MsUg274I8qKqqCgwM3L17d1JS0p49e8AN6k8pfwIhCCIQCLGxsVlZWZcvX7a3t1e4cZclnncBQ0KhMCoqauzYsc7OzoWFhZ+d7QP4f/Agk5ycbGpqGhAQoHCTrfZ33gWsiMXi5ORkGxsbf3//iooKrJsj7wZdApEpQWJjYykUiq+v76NHj2DFIRKJZs2aVVxcDMurO3fuuLi42NvbgxuefTQYE4jg8XjR0dFUKjUgICA7OxtWBIcPH87JyYHlUlZW1qRJk2g0WkpKilgsxro5CmPwJhDB4/FiYmJoNJqjo+PJkye/NHm9PEhOTr5161bPj3IyVjefz4+Pjx8zZgyNRjtz5oxQKMS6RQpGqd4LlRhy+vS///2voKBg9erVq1atkrdxgdPS0goKCmbNmoW0trCw0MzMbMqUKRg2icPhnDhx4siRI1ZWVtu2bZs+fbqyTnOLLqy/AuQLi8UKCwvT19f39PQ8efJkS0sLLAcknncBDSKRKD09fdGiRbq6uqGhoUwmE5NmKA1wDPwMgUBw8+bNs2fPZmdnz5gxY+HChT4+PuAlxhcvXpzrZmhouGzZskWLFhEIBJQPEMoPJLA3jY2NCQkJKSkpRUVFfn5+QUFB/v7+g60v6ePHj69evUqn09ls9uLFi5cvX658k/hhCCSwT9hsdlpa2pUrV+7evTtu3Dg/Pz8fHx8HBwdlvfLp7Oy8f//+tWvX6HQ6DoebPXv2rFmz3N3dB/lkUmgACewfLpd7+/btjIyMzMxMDofj7e3t4+MzefJkc3NzSMHx+fz8/PysrKzs7GwGg+Ho6Ojv7x8UFDR4hi3DBEig5KqrqzO75ebm8ni8sWPHurm5je2mKBdIVVVVyKS2yCSeNjY2k7tNmDDho2kDAZSABMrGu3fv8vPzHz169PDhw8LCQgMDg9GjR9NoNORfGo0mDzdyWlpaWN3KysoeP37MYDDU1dWdnZ1dunl4eAy2S1x5ABIoeyKR6OXLl6WlpWVlZci/r169IpPJo0aNMulm2s3ExMTAwEBdXV3mDWhpaampqXn3j4qKChaL9fz58/b2dqtuNBrNycnJxcXF0NBQ5rUD/QISOBCEQmFFRUVlZeWbN29ed6vqxmazcTicnp6evr4+kUjU09MjEAh4PH7YsGEaGhp4PF5dXV1TUxMZSLO5ufnDMrlcbmu3tra2lpYWDofT2tra3Nz89u1bVVVVCoViaGhoZGSEJB8JnpGR0YD8uUA/gARirK2traGhgc1mNzY2NjQ0NDc3d3bj8XgdHR1dXV3t7e3IZCYfXVtqaWlpa2vr6Ohoa2vr6uoOHz5cW1ubQCBQqVRNTU3s/iCgf0ACAQBL4PEOAGAJJBAAsAQSCABYAgkEACyBBAIAlkACAQBLIIEAgCWQQADAEkggAGAJJBAAsAQSCABYAgkEAAhD/wdLj+HwYUYeUwAAAABJRU5ErkJggg==" }, "metadata": {}, "output_type": "display_data" } ], "source": [ "using IJulia\n", "IJulia.display(\"image/png\", read(\"graph.png\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The dimension of the matrix `S` is $2 \\times 2$ because two nodes. Arcs $i \\rightarrow j$ are depicted by the elements of `S[j,i]`. The order is reversed in order to keep the matrix product `S . x` with `x` a column vector.\n", "\n", "Note that the Julia `GraphPlot.jl` packages do not correctly display this kind of matrix and that `SimpleWeightedGraphs.jl` does not take a (max,+) matrix." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Arc $2 \\rightarrow 1$ with the valeur MP(7):" ] }, { "cell_type": "code", "execution_count": 125, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 7" ] }, "execution_count": 125, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S[1,2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Eigenvalues:" ] }, { "cell_type": "code", "execution_count": 126, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " 4.5\n", " 4.5\n" ] }, "execution_count": 126, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r.eigenvalues" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "eigenvectors:" ] }, { "cell_type": "code", "execution_count": 127, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " 6.5\n", " 4\n" ] }, "execution_count": 127, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r.eigenvectors" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Number of connected components found (only one will be returned):" ] }, { "cell_type": "code", "execution_count": 128, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 128, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r.components" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The list of nodes from the saturation policy:" ] }, { "cell_type": "code", "execution_count": 129, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Vector{Int64}:\n", " 2\n", " 1" ] }, "execution_count": 129, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r.policy" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Résolution d'équations linéaires Max-Plus $A \\otimes x = b$\n", "\n", "Soit $A \\in \\mathbb{R}_{\\varepsilon}^{n \\times n}$ une matrice Max-plus carrée et $b \\in \\mathbb{R}_{\\varepsilon}^{n}$ un vecteur colonne. La solution de $A \\otimes x = b$ est donnée par :\n", "$$x = A^{-1} \\otimes b$$\n", "\n", "L'inverse de $A$ peut être donné par les fonctions Julia `inv` ou `^-1` et si la matrice n'est pas inversible alors une erreur Julia est levée :" ] }, { "cell_type": "code", "execution_count": 130, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) dense matrix:\n", " . 1 .\n", " 2 . .\n", " . . 3\n" ] }, "execution_count": 130, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = [mp0 1 mp0; 2 mp0 mp0; mp0 mp0 3]" ] }, { "cell_type": "code", "execution_count": 131, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) dense matrix:\n", " . -2 .\n", " -1 . .\n", " . . -3\n" ] }, "execution_count": 131, "metadata": {}, "output_type": "execute_result" } ], "source": [ "inv(A) # Ou bien A^-1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vérifions que leur produit donne bien la matrice identité :" ] }, { "cell_type": "code", "execution_count": 132, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) dense matrix:\n", " 0 . .\n", " . 0 .\n", " . . 0\n" ] }, "execution_count": 132, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A * inv(A) # Ou bien inv(A) * A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Calculons $x = A^{-1} \\otimes b$ :" ] }, { "cell_type": "code", "execution_count": 133, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) dense matrix:\n", " 3 . .\n", " . . 4\n", " . 5 .\n" ] }, "execution_count": 133, "metadata": {}, "output_type": "execute_result" } ], "source": [ "B = [3 mp0 mp0; mp0 mp0 4; mp0 5 mp0]" ] }, { "cell_type": "code", "execution_count": 134, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 (max,+) dense matrix:\n", " . . 2\n", " 2 . .\n", " . 2 .\n" ] }, "execution_count": 134, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = A \\ B" ] }, { "cell_type": "code", "execution_count": 135, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 135, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A * x == B" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solving Max-Plus Linear Equations $x = Ax \\oplus b$\n", "\n", "Let $A \\in \\mathbb{R}_{\\varepsilon}^{n \\times n}$ a square Max-plus matrix and $b \\in \\mathbb{R}_{\\varepsilon}^{n}$ a column vector. The solution of $x = Ax \\oplus b$ is given by:\n", "$$x = A^* b$$\n", "\n", "Where:\n", "\n", "$$A^+ \\triangleq A^1 \\oplus A^2 \\oplus A^3 \\oplus\\;...$$\n", "$$A^* \\triangleq A^0 \\oplus A^+$$\n", "\n", "$A^0$ is none other than the Max-Plus identity matrix. $A^+$ is calculated by the function `plus` and $A^*$ is calculated by the function `star`. The solution of the equation is given by the function `astarb`. A solution exists as soon as the largest circuit in the adjacency graph of the matrix has a negative or null weight. The weight of a circuit being given by the sum of the weights of the arcs (coefficients of the matrix) constituting it." ] }, { "cell_type": "code", "execution_count": 136, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) Inf" ] }, "execution_count": 136, "metadata": {}, "output_type": "execute_result" } ], "source": [ "star(MP(2))" ] }, { "cell_type": "code", "execution_count": 137, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(max,+) 0" ] }, "execution_count": 137, "metadata": {}, "output_type": "execute_result" } ], "source": [ "star(MP(-2))" ] }, { "cell_type": "code", "execution_count": 138, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 -2\n", " -1 0\n" ] }, "execution_count": 138, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = MP([-3 -2; -1 0])\n", "plus(A)" ] }, { "cell_type": "code", "execution_count": 139, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 (max,+) dense matrix:\n", " 0 -2\n", " -1 0\n" ] }, "execution_count": 139, "metadata": {}, "output_type": "execute_result" } ], "source": [ "star(A)" ] }, { "cell_type": "code", "execution_count": 140, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 140, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plus(A) == A * star(A)" ] }, { "cell_type": "code", "execution_count": 141, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 141, "metadata": {}, "output_type": "execute_result" } ], "source": [ "star(zeros(MP, 2,2)) == star(full(zeros(MP, 2,2)))" ] }, { "cell_type": "code", "execution_count": 142, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " .\n", " 0\n" ] }, "execution_count": 142, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b = MP([mp0; mp1])" ] }, { "cell_type": "code", "execution_count": 143, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "2-element (max,+) vector:\n", " -2\n", " 0\n" ] }, "execution_count": 143, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = astarb(A, b)" ] }, { "cell_type": "code", "execution_count": 144, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 144, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x == A * x + b" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.8.1", "language": "julia", "name": "julia-1.8" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.8.1" } }, "nbformat": 4, "nbformat_minor": 2 }