Exact parallelized dynamic mode decomposition with Hankel matrix for large-scale flow data

Abstract An exact parallel algorithm of dynamic mode decomposition (DMD) with Hankel matrices for large-scale flow data is proposed. The proposed algorithm enables the DMD and the Hankel DMD for large-scale data obtained by high-fidelity flow simulations, such as large-eddy simulations or direct numerical simulations using more than a billion grid points, on parallel computations without any approximations. The proposed algorithm completes the computations of the DMD by utilizing block matrices of $$X^TX\in \mathbb {R}^{k\times k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>X</mml:mi> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>X</mml:mi> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>×</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> (where $$X\in \mathbb {R}^{n\times k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> is a large data matrix obtained by high-fidelity simulations, the number of snapshot data is $$n &gt; rsim 10^9$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≳</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mn>9</mml:mn> </mml:msup> </mml:mrow> </mml:math> , and the number of snapshots is $$k\lesssim O(10^3)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≲</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> ) without any approximations: for example, the singular value decomposition of X is replaced by the eigenvalue decomposition of $$X^TX$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>X</mml:mi> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> . Then, the computation of $$X^TX$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>X</mml:mi> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> is parallelized by utilizing the domain decomposition often used in flow simulations, which reduces the memory consumption for each parallel process and wall-clock time in the DMD by a factor approximately equal to the number of parallel processes. The parallel computation with communication is performed only for $$X^TX$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>X</mml:mi> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> , allowing for high parallel efficiency under massively parallel computations. Furthermore, the proposed exact parallel algorithm is extended to the Hankel DMD without any additional parallel computations, realizing the Hankel DMD of large-scale data collected by over a billion grid points with comparable cost and memory to the DMD without Hankel matrices. Moreover, this study shows that the Hankel DMD, which has been employed to enrich information and augment rank, is advantageous for large-scale high-dimensional data collected by high-fidelity simulations in data reconstruction and predictions of future states (while prior studies have reported such advantages for low-dimensional data). Several numerical experiments using large-scale data, including laminar and turbulent flows around a cylinder and transonic buffeting flow around a full aircraft configuration, demonstrate that (i) the proposed exact parallel algorithm reproduces the existing non-parallelized Hankel DMD, (ii) the Hankel DMD for large-scale data consisting of over a billion grid points is feasible by using the proposed exact parallel algorithm with high parallel efficiency on more than 6 thousand CPU cores, and (iii) the Hankel DMD has advantages for high-dimensional data such as $$n &gt; rsim 10^9$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≳</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mn>9</mml:mn> </mml:msup> </mml:mrow> </mml:math> . Graphical abstract