New computational tools for Koopman spectral analysis of nonlinear dynamical systems

Dynamic Mode Decomposition (DMD) is a data driven spectral analysis technique for a time series. For a sequence of snapshot vectors $\mathbf{; ; f}; ; _1, \mathbf{; ; f}; ; _2, \dots, \mathbf{; ; f}; ; _{; ; m+1}; ; $ in $\mathbb{; ; C}; ; ^{; ; n}; ; $, assumed driven by a linear operator $\mathbb{; ; A}; ; $, $\mathbf{; ; f}; ; _{; ; i+1}; ; =\mathbb{; ; A}; ; \mathbf{; ; f}; ; _i$, the goal is to represent the snapshots in terms of the computed eigenvectors and eigenvalues of $\mathbb{; ; A}; ; $. We can think of $\mathbb{; ; A}; ; $ as a discretization of the underlying physics that drives the measured $\mathbf{; ; f}; ; _i$'s. In a pure data driven setting we have no access to $\mathbb{; ; A}; ; $. Instead, the $\mathbf{; ; f}; ; _i$'s are the results of measurements, e.g. computed from pixel values from a high speed camera recorded video. No other information on the action of $\mathbb{; ; A}; ; $ is available. (In another scenario of data acquisition, $\mathbb{; ; A}; ; $ represents PDE/ODE solver (software toolbox) that generates solution in high resolution, with given initial condition $\mathbf{; ; f}; ; _1$.) Such a representation of the data sequence provides an insight into the evolution of the underlying dynamics, in particular on dynamically relevant spatial structures (eigenvectors) and amplitudes and frequencies of their evolution (encoded in the corresponding eigenvalues) -- it can be considered a finite dimensional realization of the Koopman spectral analysis, corresponding to the Koopman operator associated with the nonlinear dynamics under study \cite{; ; zd:arbabi-mezic-siam-2017}; ; . This important theoretical connection with the Koopman operator and the ergodic theory, and the availability of numerical algorithm \cite{; ; zd:schmid2010}; ; make the DMD a tool of trade in computational study of complex phenomena in fluid dynamics, see e.g. \cite{; ; zd:Williams2015}; ; . Its exceptional performance motivated developments of several modifications that make the DMD an attractive method for analysis and model reduction of nonlinear systems in data driven settings. A peculiarity of the data driven setting is that direct access to the operator is not available, thus an approximate representation of $\mathbb{; ; A}; ; $ is achieved using solely the snapshot vectors $\mathbf{; ; f}; ; _i$ whose number $m+1$ is usually much smaller than the dimension $n$ of the domain of $\mathbb{; ; A}; ; $. In this talk, we present recent development of numerically robust computational tools for dynamic mode decomposition and data driven Koopman spectral analysis. First, we consider computations of the Ritz pairs $(z_j, \lambda_j)$ of $\mathbb{; ; A}; ; $, using both the SVD based Schmid's DMD \cite{; ; zd:schmid2010}; ; and the natural formulation via the Krylov decomposition with the Frobenius companion matrix. We show how to use the eigenvectors of the companion matrix explicitly -- these are the columns of the inverse of the notoriously ill-conditioned Vandermonde matrix. The key step to curb ill-conditioning is the discrete Fourier transform of the snapshots ; in the new representation, the Vandermonde matrix is transformed into a generalized Cauchy matrix, which then allows accurate computation by specially tailored algorithms of numerical linear algebra. Numerical experiments show robustness in extremely ill-conditioned cases. More details can be found in \cite{; ; zd:P1}; ; , \cite{; ; zd:P2}; ; . Secondly, the goal is to identify the most important coherent structures in the dynamic process under study, i.e. after computing the Ritz pairs $(z_j, \lambda_j)$ of $\mathbb{; ; A}; ; $ the task is to determine $\ell