Implementation of the max plus algebra in SCILAB

Michael Mc Gettrick, Centre Automatique et Systèmes, École des Mines de Paris gettrick@cas.ensmp.fr

We present ongoing work on adding functionality to SCILAB to enable calculations in idempotent semirings (``dioids''). To date the dioids in question are the closely related (indeed isomorphic) (max,+) and (min,+) dioids.

While each object in SCILAB has a certain type (e.g. matrix, polynomial, list,...), we now have the concept that each type can be in a number of different ``algebras'', such as (``normal'', max+, min+,...). In our implementation, we use the same symbols (+, *, /,...) in each ``algebra'', and their meaning comes from the type of the objects they operate on: thus 2+3 = 5 or 3, depending on whether 2 and 3 have the type of normal algebra or of (max,+), respectively.

Other aspects of this additional functionality include

• New error-handling routines to cater for operations such as (in max+)

• (max,+) and (min,+) operations implemented for (sparse) matrices
• Residuation (left and right) implemented for (sparse) matrices
• Solution of linear equations such as
  • Ax=b
  • x=Ax+b
  • Ax=lambda x (eigenvalue problem)
• Graphical display of results using METANET

We will also present some preliminary work on practical use of this software in modelling a large rail network.

Mon Nov 17 12:27:58 MET 1997