Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Koopman operator of algorithms
356
0
0.0
(
0
)
Added by
Felix Dietrich
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A systematic mathematical framework for the study of numerical algorithms would allow comparisons, facilitate conjugacy arguments, as well as enable the discovery of improved, accelerated, data-driven algorithms. Over the course of the last century, the Koopman operator has provided a mathematical framework for the study of dynamical systems, which facilitates conjugacy arguments and can provide efficient reduced descriptions. More recently, numerical approximations of the operator have enabled the analysis of a large number of deterministic and stochastic dynamical systems in a completely data-driven, essentially equation-free pipeline. Discrete or continuous time numerical algorithms (integrators, nonlinear equation solvers, optimization algorithms) are themselves dynamical systems. In this paper, we use this insight to leverage the Koopman operator framework in the data-driven study of such algorithms and discuss benefits for analysis and acceleration of numerical computation. For algorithms acting on high-dimensional spaces by quickly contracting them towards low-dimensional manifolds, we demonstrate how basis functions adapted to the data help to construct efficient reduced representations of the operator. Our illustrative examples include the gradient descent and Nesterov optimization algorithms, as well as the Newton-Raphson algorithm.
rate research
Read More
This work presents a nonintrusive physics-preserving method to learn reduced-order models (ROMs) of Hamiltonian systems. Traditional intrusive projection-based model reduction approaches utilize symplectic Galerkin projection to construct Hamiltonian reduced models by projecting Hamiltons equations of the full model onto a symplectic subspace. This symplectic projection requires complete knowledge about the full model operators and full access to manipulate the computer code. In contrast, the proposed Hamiltonian operator inference approach embeds the physics into the operator inference framework to develop a data-driven model reduction method that preserves the underlying symplectic structure. Our method exploits knowledge of the Hamiltonian functional to define and parametrize a Hamiltonian ROM form which can then be learned from data projected via symplectic projectors. The proposed method is `gray-box in that it utilizes knowledge of the Hamiltonian structure at the partial differential equation level, as well as knowledge of spatially local components in the system. However, it does not require access to computer code, only data to learn the models. Our numerical results demonstrate Hamiltonian operator inference on a linear wave equation, the cubic nonlinear Schr{o}dinger equation, and a nonpolynomial sine-Gordon equation. Accurate long-time predictions far outside the training time interval for nonlinear examples illustrate the generalizability of our learned models.
Koopman operator theory, a powerful framework for discovering the underlying dynamics of nonlinear dynamical systems, was recently shown to be intimately connected with neural network training. In this work, we take the first steps in making use of this connection. As Koopman operator theory is a linear theory, a successful implementation of it in evolving network weights and biases offers the promise of accelerated training, especially in the context of deep networks, where optimization is inherently a non-convex problem. We show that Koopman operator theoretic methods allow for accurate predictions of weights and biases of feedforward, fully connected deep networks over a non-trivial range of training time. During this window, we find that our approach is >10x faster than various gradient descent based methods (e.g. Adam, Adadelta, Adagrad), in line with our complexity analysis. We end by highlighting open questions in this exciting intersection between dynamical systems and neural network theory. We highlight additional methods by which our results could be expanded to broader classes of networks and larger training intervals, which shall be the focus of future work.
The Koopman operator allows for handling nonlinear systems through a (globally) linear representation. In general, the operator is infinite-dimensional - necessitating finite approximations - for which there is no overarching framework. Although there are principled ways of learning such finite approximations, they are in many instances overlooked in favor of, often ill-posed and unstructured methods. Also, Koopman operator theory has long-standing connections to known system-theoretic and dynamical system notions that are not universally recognized. Given the former and latter realities, this work aims to bridge the gap between various concepts regarding both theory and tractable realizations. Firstly, we review data-driven representations (both unstructured and structured) for Koopman operator dynamical models, categorizing various existing methodologies and highlighting their differences. Furthermore, we provide concise insight into the paradigms relation to system-theoretic notions and analyze the prospect of using the paradigm for modeling control systems. Additionally, we outline the current challenges and comment on future perspectives.
We study numerical approaches to computation of spectral properties of composition operators. We provide a characterization of Koopman Modes in Banach spaces using Generalized Laplace Analysis. We cast the Dynamic Mode-Decomposition type methods in the context of Finite Section theory of infinite dimensional operators, and provide an example of a mixing map for which the finite section method fails. Under assumptions on the underlying dynamics, we provide the first result on the convergence rate under sample size increase in the finite-section approximation. We study the error in the Krylov subspace version of the finite section method and prove convergence in pseudospectral sense for operators with pure point spectrum. This result indicates that Krylov sequence-based approximations can have low error without an exponential-in-dimension increase in the number of functions needed for approximation.
In this work, a novel approach for the reliable and efficient numerical integration of the Kuramoto model on graphs is studied. For this purpose, the notion of order parameters is revisited for the classical Kuramoto model describing all-to-all interactions of a set of oscillators. First numerical experiments confirm that the precomputation of certain sums significantly reduces the computational cost for the evaluation of the right-hand side and hence enables the simulation of high-dimensional systems. In order to design numerical integration methods that are favourable in the context of related dynamical systems on network graphs, the concept of localised order parameters is proposed. In addition, the detection of communities for a complex graph and the transformation of the underlying adjacency matrix to block structure is an essential component for further improvement. It is demonstrated that for a submatrix comprising relatively few coefficients equal to zero, the precomputation of sums is advantageous, whereas straightforward summation is appropriate in the complementary case. Concluding theoretical considerations and numerical comparisons show that the strategy of combining effective community detection algorithms with the localisation of order parameters potentially reduces the computation time by several orders of magnitude.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
