Maxplus Function
Last update : 18/05/2014

semihoward - generalized maxplus eigenvalue eigenvector ( Howard algorithm )

Calling Sequence

[l,v,p,c,n]=semihoward(T,N)

Parameters

Description

Generalized right maxplus eigenvalues and eigenvectors of a timed event graph represented by a pair (T,N) of full or sparse maxplus matrices computed by a generalized Howard algorithm for delayed dynamic programming. That is the solutions (l,v) of max_j[(T_ij -N_ij x l_j)+v_j] = v_i . The matrices N and T must have the same nonzero entries. When T is irreducible l is constant.

The optimal policy p satisfies A_ip(i) v_p(i)= v_i where A denotes the matrix T-Nxdiag(l) in the standard algebra sense.

For performance evaluation of an event graph, N contains the numbers of tokens (initial marking) and T the minimal time that a token has to spend in a place. The eigenvalues l are interpreted as the average cost per time unit for the corresponding delayed dynamic programming problem and are computed by the Howard algorithm.

The values taken by the entries of l are the eigenvalues. If N is irreducible, l is constant: it is the eigenvalue and v is a corresponding eigenvector (in this case, there exits only one eigenvalue but there may exist more than one eigenvectors). If A can be decomposed into irreducible components (block diagonal with irreducible blocks), then, in each component, l is constant and this constant is the eigenvalue, the corresponding entries of v, completed by -inf, yields a corresponding eigenvector. For the block triangular case see howard command.

Examples

// irreducible case, matrices without zero terms :
//------------------------------------------------
T=[1,2;3,4];N=[2,2;2,2];[l,v]=semihoward(#(T),#(N))
// simple verification
#(T-N*plustimes(l(1)))*v==v





// irreducible case, matrices with zero terms :
//---------------------------------------------
T=[%0,1;3,%0];N=[%0,1;1,%0];[l,v]=semihoward(#(T),#(N))
// verification needs the maxplus minus operator
(T-#(plustimes(N)*plustimes(l(1))))*v==v

// sparse matrices, irreducible case :
//------------------------------------
T=sparse([%0,1;3,%0]);N=sparse([%0,1;1,%0]);[l,v]=semihoward(T,N)
#(plustimes(T)-plustimes(N)*plustimes(l(1)))*v==v

// general case :
//---------------
T=#([1,%0;%0,2])
N=%eye(2,2)*1
[l,v]=semihoward(T,N)

// 1) vectorial verification : 
(#(full(T))-full(#(plustimes(N)*diag(plustimes(sparse(l))))))*v==v

// 2) verification irreducible block by irreducible block : 
//   --- block 1:
(T(1,1)-#(plustimes(N(1,1))*plustimes(l(1))))*v(1)==v(1)
//   --- block 2:
(T(2,2)-#(plustimes(N(2,2))*plustimes(l(2))))*v(2)==v(2)
 

See Also

karp,  howard,  minus,