semihoward - generalized maxplus eigenvalue eigenvector ( Howard algorithm )
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.
// 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)