Maxplus Function

howard - maxplus eigenvalues eigenvectors (Howard algorithm)

Calling Sequence

[l,v,p,c,n]=howard(A)

Parameters

Description

Maxplus right eigenvalues and eigenvectors of a full or sparse maxplus matrix by Howard algorithm. The eigenvalues are considered as the average cost per unit of time for the corresponding dynamic programming problem.

The values taken by the entries of l are the eigenvalues. If A is irreducible, l is constant, it is the eigenvalue and v is a corresponding eigenvector (in this case, there exits only one eigenvalue but more than one eigenvectors may exist).

Otherwise, A can be decomposed into irreducible components (in a certain numbering of rows and columns, it becomes block-triangular with diagonal irreducible blocks), l is constant over each component and this constant is the eigenvalue, the corresponding entries of v, completed by -inf for the other blocks, provide a corresponding eigenvector.

p gives an optimal policy which satisfies a_ip(i) v_p(i)= l+v_i.

Remark:

- For the block triangular case, take a look at the examples to see what happen precisely on the transient block. All the eigen values are not found and the support of the eigenvectors depends of the eigenvalues of the blocks.

- For the block diagonal case all the eigen values are found and the support of the eigenvectors are clear.

EXAMPLES

See Also