Max-plus switching systems and long max-plus matrix products
Lead Research Organisation:
University of Birmingham
Department Name: School of Mathematics
Abstract
Switching max-plus linear (SMPL) systems are used to model the propagation of delays in a railway network.
Suppose that departure times of a network at a particular instant
are given by a vector x(k). The departure times at instant k are
given by a recurrence relation based upon the departure times at a
previous instant multiplied in the sense of max-plus arithmetic by
matrix A(u(k)) where u(k) is a control variable. At every instant, the network may
slightly change, which is encapsulated in this control variable.
This has a residual effect on the ultimate departure times, which
one often seeks to optimize in some way: for instance, by minimizing
the cumulative delay with respect to a given regular schedule.
The main idea of the proposed research is to study the switching
max-plus linear systems as vector orbits of a finitely generated max-plus matrix semigroup: the set of all
possible max-plus matrix products of a given finite set of matrices.
In this research we will be particularly interested in the long
max-plus matrix products and developing for them an analogue
of the CSR representation of max-plus matrix powers suggested by
Sergeev and Schneider. We then aim to apply the new theoretical
results which we obtain to switching max-plus systems and the above
mentioned optimization problems over them.
Suppose that departure times of a network at a particular instant
are given by a vector x(k). The departure times at instant k are
given by a recurrence relation based upon the departure times at a
previous instant multiplied in the sense of max-plus arithmetic by
matrix A(u(k)) where u(k) is a control variable. At every instant, the network may
slightly change, which is encapsulated in this control variable.
This has a residual effect on the ultimate departure times, which
one often seeks to optimize in some way: for instance, by minimizing
the cumulative delay with respect to a given regular schedule.
The main idea of the proposed research is to study the switching
max-plus linear systems as vector orbits of a finitely generated max-plus matrix semigroup: the set of all
possible max-plus matrix products of a given finite set of matrices.
In this research we will be particularly interested in the long
max-plus matrix products and developing for them an analogue
of the CSR representation of max-plus matrix powers suggested by
Sergeev and Schneider. We then aim to apply the new theoretical
results which we obtain to switching max-plus systems and the above
mentioned optimization problems over them.
People |
ORCID iD |
| Arthur Kennedy-Cochran-Patrick (Student) |
Publications
Kennedy-Cochran-Patrick A
(2021)
New bounds on the periodicity transient of the powers of a tropical matrix: Using cyclicity and factor rank
in Linear Algebra and its Applications
Kennedy-Cochran-Patrick A
(2023)
Extending CSR decomposition to tropical inhomogeneous matrix products
in The Electronic Journal of Linear Algebra
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509590/1 | 01/10/2016 | 30/09/2021 | |||
| 1956719 | Studentship | EP/N509590/1 | 01/10/2017 | 31/03/2021 | Arthur Kennedy-Cochran-Patrick |
| Description | For a specific case of matrices we have developed a transient for a factor rank-one property of the long matrix product. This means that, using the specific type of matrices, if the length of the product (i.e. the number of matrices multiplied together) is greater than the transient, then the matrix can be written as the product of a column vector and row vector taken from the matrix. We have developed an inhomogeneous product analogue of CSR, which for matrices that are CSR, exhibit a factor rank property equivalent to the sum of the cyclicities of each strongly connected component of the critical graph of the original matrix structure. Using this CSR definition we have developed a transient for a more general version of the first case in which a product of length satisfying such transient is CSR. We have also developed counterexamples for the cases where this CSR definition does not work. |
| Exploitation Route | With the cases of counterexamples there exists scope to either alter the definition of CSR, or to exert some control over the sequence of matrices making the product in order to develop transients for the more general cases. As these are theoretical results there is also scope for applications of them in areas that require long max-plus matrix products. |
| Sectors | Digital/Communication/Information Technologies (including Software),Transport |
| URL | https://arxiv.org/abs/2009.07804 |
| Description | Collaboration with Glenn Merlet (Marseille, France) and Thomas Nowak (Paris, France) |
| Organisation | Aix-Marseille University |
| Country | France |
| Sector | Academic/University |
| PI Contribution | The award has helped to restart our collaboration with Dr. Glenn Merlet from Aix-Marseille University in France and with Dr. Thomas Nowak (Paris, France). We have created together two academic papers during the project duration, and they finally got published in the end of 2020 and beginning of 2021. The research also involved Arthur Kennedy-Cochran-Patrick (University of Birmingham). The contribution of all participants was fair and equal and included theoretical hypothesis, proofs and examples illustrating the validity and the sense of proven statements. |
| Collaborator Contribution | The contribution of all participants was fair and equal and included theoretical hypothesis, proofs and examples illustrating the validity and the sense of proven statements. |
| Impact | 1. Article "New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank" (coauthored by A. Kennedy-Cochran-Patrick, G. Merlet, T. Nowak and S. Sergeev, published in the journal "Linear Algebra and its Applications") offers new bounds on the periodicity transient of tropical matrix powers that make use of cyclicity of the ambient digraph and the factor rank. See https://www.sciencedirect.com/science/article/pii/S0024379520305152 2. Article "On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers" (coauthored by G. Merlet, T. Nowak and S. Sergeev, published in the journal "Linear and Multilinear Algebra) offers an in-depth analysis of matrices that precisely attain some bounds on the periodicity transient that were obtained earlier. See https://www.tandfonline.com/doi/abs/10.1080/03081087.2021.1878995 |
| Start Year | 2017 |
| Description | Talk at International Linear Algebra and Matrix Theory Workshop at University College Dublin |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | International Linear Algebra Conference in UCD took place in the end of May 2019. It attracted such renowned experts in Linear Algebra and Numerical Algorithms as C. Johnson, V. Mehrmann, T. Laffey and H. Smigoc. I was invited to give a talk on tropical matrix algebra. My talk was on the ongoing work on tropical matrix powers and their periodicity transients, with extension to non-homogenous matrix products, which I am doing jointly with my colleagues in France (G. Merlet and T. Nowak) and my PhD student A. Kennedy-Cochran-Patrick. As a result of my talk, the audience became more interested in tropical matrix algebra and in tropical matrix powers in particular. |
| Year(s) Of Engagement Activity | 2019 |
| URL | https://maths.ucd.ie/lamt/Abstracts.pdf |