On the maxmin-$ω$ eigenspaces and their over-approximation by zones
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911965152018432 |
|---|---|
| author | Mufid, Muhammad Syifa'ul Patel, Ebrahim Sergeev, Sergei |
| author_facet | Mufid, Muhammad Syifa'ul Patel, Ebrahim Sergeev, Sergei |
| contents | Maxmin-$ω$ dynamical systems were previously introduced as a generalization of dynamical systems expressed by tropical linear algebra. To describe steady states of such systems one has to study an eigenproblem of the form $A\otimes_ω x=λ+x$ where $\otimes_ω$ is the maxmin-$ω$ matrix-vector multiplication. This eigenproblem can be viewed in more general framework of nonlinear Perron-Frobenius theory. However, instead of studying such eigenspaces directly we develop a different approach: over-approximation by zones. These are traditionally convex sets of special kind which proved to be highly useful in computer science and also relevant in tropical convexity. We first construct a sequence of zones over-approximating a maxmin-$ω$ eigenspace. Next, the limit of this sequence is refined in a heuristic procedure, which yields a refined zone and also the eigenvalue $λ$ with a high success rate. Based on the numerical experiments, in successful cases there is a column of the difference bound matrix (DBM) representation of the refined zone which yields an eigenvector. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16778 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the maxmin-$ω$ eigenspaces and their over-approximation by zones Mufid, Muhammad Syifa'ul Patel, Ebrahim Sergeev, Sergei Rings and Algebras Metric Geometry 15A80, 15A18, 47J10 Maxmin-$ω$ dynamical systems were previously introduced as a generalization of dynamical systems expressed by tropical linear algebra. To describe steady states of such systems one has to study an eigenproblem of the form $A\otimes_ω x=λ+x$ where $\otimes_ω$ is the maxmin-$ω$ matrix-vector multiplication. This eigenproblem can be viewed in more general framework of nonlinear Perron-Frobenius theory. However, instead of studying such eigenspaces directly we develop a different approach: over-approximation by zones. These are traditionally convex sets of special kind which proved to be highly useful in computer science and also relevant in tropical convexity. We first construct a sequence of zones over-approximating a maxmin-$ω$ eigenspace. Next, the limit of this sequence is refined in a heuristic procedure, which yields a refined zone and also the eigenvalue $λ$ with a high success rate. Based on the numerical experiments, in successful cases there is a column of the difference bound matrix (DBM) representation of the refined zone which yields an eigenvector. |
| title | On the maxmin-$ω$ eigenspaces and their over-approximation by zones |
| topic | Rings and Algebras Metric Geometry 15A80, 15A18, 47J10 |
| url | https://arxiv.org/abs/2407.16778 |