PUB - Publikationen an der Universität Bielefeld

In the max algebra system, the eigenequation for an n x n irreducible nonnegative matrix A = [a(ij)] is A circle times x = mu (A)x. Here (A circle times x)(i) = max(j) a(ij)x(j) and mu (A) is the maximum circuit geometric mean. The complexity of the power method given in [L. Elsner, P. van den Driessche, Linear Algebra Appl., to appear] to compute mu (A) and x is considered. Under some assumptions on the critical matrix, it is shown that the algorithm may have time complexity O(n(4)), A modified power method, based on Karp's formula, is presented. For this new algorithm, with no assumptions on the critical matrix, mu (A) and x can be computed in O(n(3)) time. Furthermore, this algorithm can be used to compute all linearly independent eigenvectors corresponding to mu (A). (C) 2001 Elsevier Science Inc. All rights reserved.