Naslov
New computational tools for Koopman spectral analysis of nonlinear dynamical systems

Autori
Drmač, Zlatko ; Mohr, Ryan ; Mezić, Igor

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, neobjavljeni rad, znanstveni

Skup
XXI Householder Symposium on Numerical Linear ALgebra

Mjesto i datum
Selva di Fasano, Italija, 12.06.2022. - 17.06.2022

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
dynamic mode decomposition, Koopman operator

Sažetak
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 <m$, the indices $\varsigma_1 < \cdots <\varsigma_{; ; \ell}; ; $ and the coefficients $\alpha_j$ to achieve high fidelity of the snapshot representations \begin{; ; equation}; ; \label{; ; eq:f_i-reconstruct-ell}; ; \mathbf{; ; f}; ; _i \approx \widehat{; ; \mathbf{; ; f}; ; }; ; _i\equiv \sum_{; ; j=1}; ; ^\ell z_{; ; \varsigma_j}; ; \alpha_j \lambda_{; ; \varsigma_j}; ; ^{; ; i-1}; ; , \ ; \ ; i=1, \ldots , m . \end{; ; equation}; ; After selecting an appropriate subset $\{; ; z_{; ; \varsigma_j}; ; \}; ; $ of the modes, the key numerical step is solution of a structured linear least squares (LS) problem $\sum_{; ; i=1}; ; ^m \|\mathbf{; ; f}; ; _i-\widehat{; ; \mathbf{; ; f}; ; }; ; _i\|_2^2\longrightarrow\min$ for the coefficients $\alpha_j$ in (\ref{; ; eq:f_i-reconstruct-ell}; ; ). The coefficients of the representation are determined from a solution of a structured linear least squares problems with the matrix that involves the Khatri-Rao product of a triangular and a Vandermonde matrix. Such a structure allows for a very efficient normal equation based least squares solution, which is used in state of the art computational fluid dynamics (CFD) tools, such as the sparsity promoting DMD (DMDSP). A new numerical analysis of normal equations approach provides insights about its applicability and its limitations. Relevant condition numbers that determine numerical robustness are identified and discussed. Further, a corrected semi-normal solution and the QR factorization based algorithms are proposed. It will be shown how to use the Vandermonde-Khatri-Rao structure to efficiently compute the QR factorization of the least squares coefficient matrix, thus providing a new computational tool for the ill-conditioned cases where the normal equations may fail to compute a sufficiently accurate solution. Altogether, we present a firm numerical linear algebra framework for a class of structured least squares problems arising in a variety of applications besides the DMD, such as e.g. multistatic antenna array processing. All details can be found in \cite{; ; zd:P3}; ; . The main message of the talk is that the state of the art numerical linear algebra provides sharp and robust numerical tools for computational analysis of nonlinear dynamical systems.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA