I wrote a C-program which implements Howard's mulichain policy iteration algorithm for max-plus linear maps. It solves the general ``maximal circuit mean'' problem, in directed graphs.

The basic version of the algorithm takes as input a weighted directed graph (or sparse matrix) and returns two vectors: the cycle time, and the bias (which is an eigenvector when the matrix is irreducible). An extended version takes as input a digraph with two valuations, in order to compute the generalized maximal ``weight to length'' circuit mean (the lengths need not be 1).

Howard's algorithm runs in an almost linear time (although no proof of this fact exists). It is much faster than the classical algorithms to compute the cycle time, including Karp's. An implementation of Karp's algorithm is included for comparison.

- The algorithm is documented in the following
paper: Numerical computation of spectral elements in max-plus algebra,
Jean Cochet-Terrasson, Guy Cohen, Stephane Gaubert, Michael Mc Gettrick,
Jean-Pierre Quadrat, published in the
*Proceedings of the IFAC Conference on System Structure and Control*, Nantes, France, July 8-10, 1998. ifacssc98.pdf, ifacssc98.ps, ifacssc98.ps.gz - A variant of this algorithm, which works for the simpler single source shortest path problem (which can be seen as a subproblem of the cycle time problem), has been shown to have a strongly polynomial execution time in J. Cochet-Terrasson and S. Gaubert, Policy Iteration Algorithm for Shortest Path Problems, preprint.ps, preprint.ps.gz
- A standalone distribution is available here
HOWARD0.27.tar.gz,
alternatively, the algorithm can be used in an user
friendly way from the Maxplus toolbox of Scilab.
- Older versions of the standalone distribution:

### See also The Max-plus toolbox of Scilab

S. Gaubert Updated Jul 2008