Decomposing reach set computations with low-dimensional sets and high-dimensional matrices (extended version)
Abstract: Approximating the set of reachable states of a dynamical system is an algorithmic way to rigorously reason about its safety. Despite progress on efficient algorithms for affine dynamical systems, available algorithms still lack scalability to ensure their wide adoption in practice. While modern linear algebra packages are efficient for matrices with tens of thousands of dimensions, set-based image computations are limited to a few hundred. We propose to decompose reach-set computations such that set operations are performed in low dimensions, while matrix operations are performed in the full dimension. Our method is applicable in both dense- and discrete-time settings. For a set of standard benchmarks, we show a speed-up of up to two orders of magnitude compared to the respective state-of-the-art tools, with only modest loss in accuracy. For the dense-time case, we show an experiment with more than 10,000 variables, roughly two orders of magnitude higher than possible before
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- Extent
-
Online-Ressource
- Language
-
Englisch
- Notes
-
ISSN: 1090-2651
- Event
-
Veröffentlichung
- (where)
-
Freiburg
- (who)
-
Universität
- (when)
-
2024
- Creator
- DOI
-
10.1016/j.ic.2022.104937
- URN
-
urn:nbn:de:bsz:25-freidok-2455016
- Rights
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
25.03.2025, 1:45 PM CET
Data provider
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Bogomolov, Sergiy
- Forets, Marcelo
- Frehse, Goran
- Podelski, Andreas
- Schilling, Christian
- Universität
Time of origin
- 2024
Other Objects (12)
Cavitronics in low-dimensional systems
On low-dimensional stochastic models
On low-dimensional stochastic models
Low-dimensional materials and applications
High-dimensional variable selection via low-dimensional adaptive learning
Remarks on Low-Dimensional Projections of High-Dimensional Distributions
Regularities of Pareto sets in low-dimensional practical multi-criteria optimisation problems: analysis, explanation, and exploitation
Cuprates as low-dimensional model compounds
Properties of interacting low-dimensional systems
Accurate spectral analysis of two-dimensional point sets
Strong electronic correlations in low-dimensional systems
A study of low-dimensional inhomogeneous systems
Cavitronics in low-dimensional systems
On low-dimensional stochastic models
On low-dimensional stochastic models
Low-dimensional materials and applications
High-dimensional variable selection via low-dimensional adaptive learning
Remarks on Low-Dimensional Projections of High-Dimensional Distributions
Regularities of Pareto sets in low-dimensional practical multi-criteria optimisation problems: analysis, explanation, and exploitation
Cuprates as low-dimensional model compounds
Properties of interacting low-dimensional systems
Accurate spectral analysis of two-dimensional point sets
Strong electronic correlations in low-dimensional systems
A study of low-dimensional inhomogeneous systems
Cavitronics in low-dimensional systems
On low-dimensional stochastic models
On low-dimensional stochastic models
Low-dimensional materials and applications
High-dimensional variable selection via low-dimensional adaptive learning
Remarks on Low-Dimensional Projections of High-Dimensional Distributions
Regularities of Pareto sets in low-dimensional practical multi-criteria optimisation problems: analysis, explanation, and exploitation
Cuprates as low-dimensional model compounds
Properties of interacting low-dimensional systems
Accurate spectral analysis of two-dimensional point sets
Strong electronic correlations in low-dimensional systems