On the Koopman operator of algorithms

Felix Dietrich, Thomas N. Thiem, Ioannis G. Kevrekidis

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

A systematic mathematical framework for the study of numerical algorithms would allow comparisons, facilitate conjugacy arguments, and enable the discovery of improved, accelerated, data-driven algorithms. Over the course of the past 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 toward 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.

Original languageEnglish
Pages (from-to)860-885
Number of pages26
JournalSIAM Journal on Applied Dynamical Systems
Volume19
Issue number2
DOIs
StatePublished - 2020

Keywords

  • Algorithm
  • Gradient descent
  • Koopman operator
  • Nesterov
  • Newton-Raphson

Fingerprint

Dive into the research topics of 'On the Koopman operator of algorithms'. Together they form a unique fingerprint.

Cite this