TY - JOUR
T1 - A parallel and streaming Dynamic Mode Decomposition algorithm with finite precision error analysis for large data
AU - Anantharamu, Sreevatsa
AU - Mahesh, Krishnan
N1 - Publisher Copyright:
© 2018 Elsevier Inc.
PY - 2019/3/1
Y1 - 2019/3/1
N2 - A novel technique based on the Full Orthogonalization Arnoldi (FOA) is proposed to perform Dynamic Mode Decomposition (DMD) for a sequence of snapshots. A modification to FOA is presented for situations where the matrix A is unknown, but the set of vectors {Ai−1v1}i=1 N are known. The modified FOA is the kernel for the proposed projected DMD algorithm termed, FOA based DMD. The proposed algorithm to compute DMD modes and eigenvalues i) does not require Singular Value Decomposition (SVD) for snapshot matrices X with κ2(X)≪1/ϵm, where κ2(X) is the 2-norm condition number of the snapshot matrix and ϵm is the relative round-off error or machine epsilon, ii) has an optional rank truncation step motivated by round off error analysis for snapshot matrices X with κ2(X)≈1/ϵm, iii) requires only one snapshot at a time, thus making it a 'streaming’ method even with the optional rank truncation step, iv) consumes less memory and requires less floating point operations to obtain the projected matrix than existing projected DMD methods and v) lends itself to easy parallelism as the main computational kernel involves only vector additions, dot products and matrix vector products. The new technique is therefore well-suited for DMD of large datasets on parallel computing platforms. We show both theoretically and using numerical examples that for FOA based DMD without rank truncation, the finite precision error in the computed projection of the linear mapping is O(ϵmκ2(X)). The proposed method is also compared to existing projected DMD methods for computational cost, memory consumption and relative round off error. Error indicators are presented that are useful to decide when to stop acquiring new snapshots. The proposed method is applied to several examples of numerical simulations of fluid flow.
AB - A novel technique based on the Full Orthogonalization Arnoldi (FOA) is proposed to perform Dynamic Mode Decomposition (DMD) for a sequence of snapshots. A modification to FOA is presented for situations where the matrix A is unknown, but the set of vectors {Ai−1v1}i=1 N are known. The modified FOA is the kernel for the proposed projected DMD algorithm termed, FOA based DMD. The proposed algorithm to compute DMD modes and eigenvalues i) does not require Singular Value Decomposition (SVD) for snapshot matrices X with κ2(X)≪1/ϵm, where κ2(X) is the 2-norm condition number of the snapshot matrix and ϵm is the relative round-off error or machine epsilon, ii) has an optional rank truncation step motivated by round off error analysis for snapshot matrices X with κ2(X)≈1/ϵm, iii) requires only one snapshot at a time, thus making it a 'streaming’ method even with the optional rank truncation step, iv) consumes less memory and requires less floating point operations to obtain the projected matrix than existing projected DMD methods and v) lends itself to easy parallelism as the main computational kernel involves only vector additions, dot products and matrix vector products. The new technique is therefore well-suited for DMD of large datasets on parallel computing platforms. We show both theoretically and using numerical examples that for FOA based DMD without rank truncation, the finite precision error in the computed projection of the linear mapping is O(ϵmκ2(X)). The proposed method is also compared to existing projected DMD methods for computational cost, memory consumption and relative round off error. Error indicators are presented that are useful to decide when to stop acquiring new snapshots. The proposed method is applied to several examples of numerical simulations of fluid flow.
KW - DMD
KW - Error analysis
KW - Full-Orthogonalization-Arnoldi
KW - Large data
KW - Parallel
UR - http://www.scopus.com/inward/record.url?scp=85060289208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85060289208&partnerID=8YFLogxK
U2 - 10.1016/j.jcp.2018.12.012
DO - 10.1016/j.jcp.2018.12.012
M3 - Article
AN - SCOPUS:85060289208
SN - 0021-9991
VL - 380
SP - 355
EP - 377
JO - Journal of Computational Physics
JF - Journal of Computational Physics
ER -