Modifying the power method in max algebra

Elsner L, van den Driessche P (2001)
In: Linear Algebra and its Applications. Linear Algebra and its Applications, 332-334. ELSEVIER SCIENCE INC: 3-13.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Elsner, LudwigUniBi; van den Driessche, Pauline
Abstract / Bemerkung
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.
Erscheinungsjahr
2001
Titel des Konferenzbandes
Linear Algebra and its Applications
Band
332-334
Seite(n)
3-13
ISSN
0024-3795
Page URI
https://pub.uni-bielefeld.de/record/1616857

Zitieren

Elsner L, van den Driessche P. Modifying the power method in max algebra. In: Linear Algebra and its Applications. Linear Algebra and its Applications. Vol 332-334. ELSEVIER SCIENCE INC; 2001: 3-13.
Elsner, L., & van den Driessche, P. (2001). Modifying the power method in max algebra. Linear Algebra and its Applications, Linear Algebra and its Applications, 332-334, 3-13. ELSEVIER SCIENCE INC. doi:10.1016/S0024-3795(00)00062-8
Elsner, L., and van den Driessche, P. (2001). “Modifying the power method in max algebra” in Linear Algebra and its Applications Linear Algebra and its Applications, vol. 332-334, (ELSEVIER SCIENCE INC), 3-13.
Elsner, L., & van den Driessche, P., 2001. Modifying the power method in max algebra. In Linear Algebra and its Applications. Linear Algebra and its Applications. no.332-334 ELSEVIER SCIENCE INC, pp. 3-13.
L. Elsner and P. van den Driessche, “Modifying the power method in max algebra”, Linear Algebra and its Applications, Linear Algebra and its Applications, vol. 332-334, ELSEVIER SCIENCE INC, 2001, pp.3-13.
Elsner, L., van den Driessche, P.: Modifying the power method in max algebra. Linear Algebra and its Applications. Linear Algebra and its Applications. 332-334, p. 3-13. ELSEVIER SCIENCE INC (2001).
Elsner, Ludwig, and van den Driessche, Pauline. “Modifying the power method in max algebra”. Linear Algebra and its Applications. ELSEVIER SCIENCE INC, 2001.Vol. 332-334. Linear Algebra and its Applications. 3-13.