Source-linked AI summary
Streaming GPU Singular Value and Dynamic Mode Decompositions
Seth D. Pendergrass, J. Nathan Kutz, Steven L. Brunton
TL;DR
High-dimensional streaming DMD is limited by expensive repeated SVD and inner-product computations. The paper develops streaming SVD/DMD algorithms with CPU/GPU parallelization, efficient mode-amplitude computation, and compressed-data support. Across multiple datasets, the methods provide significantly improved stream-processing performance with negligible accuracy loss, while remaining unsuitable for extreme-precision applications.
Problem
Repeated high-dimensional DMD on streaming data requires expensive SVD computations and can involve redundant inner products between successive inputs.
Source: §1 · p. 2, §2.2 · p. 5, §3 · p. 6Method
The paper combines streaming method-of-snapshots SVD, GPU-parallel DMD, efficient POD-coefficient mode amplitudes, and native compressed-format processing.
Source: §1.1 · p. 2, §3 · p. 6, §3.3 · p. 8Results
The evaluated algorithms significantly improve stream-processing performance with negligible loss in accuracy across multiple datasets.
Source: §5 · p. 13Takeaways & Limitations
Streaming SVD and DMD can process large video and other data streams in real time, with performance benefits whether or not a GPU is available.
Source: §5 · p. 13The algorithms are not suitable for extreme-precision applications because their small accuracy loss, though negligible for video background modeling, remains a limitation.
Source: §5 · p. 13
Abstract
from arXiv · showhide
This work develops a parallelized algorithm to compute the dynamic mode decomposition (DMD) on a graphics processing unit using the streaming method of snapshots singular value decomposition. This allows the algorithm to operate efficiently on streaming data by avoiding redundant inner-products as new data becomes available. In addition, it is possible to leverage the native compressed format of many data streams, such as HD video and computational physics codes that are represented sparsely in the Fourier domain, to massively reduce data transfer from CPU to GPU and to enable sparse matrix multiplications. Taken together, these algorithms facilitate real-time streaming DMD on high-dimensional data streams. We demonstrate the proposed method on numerous high-dimensional data sets ranging from video background modeling to scientific computing applications, where DMD is becoming a mainstay algorithm. The computational framework is developed as an open-source library written in C++ with CUDA, and the algorithms may be generalized to include other DMD advances, such as compressed sensing DMD, multi resolution DMD, or DMD with control. Keywords: Singular value decomposition, dynamic mode decomposition, streaming computations, graphics processing unit, video background modeling, scientific computing.
1 Introduction
The paper targets the expensive, repeatedly recomputed SVD underlying DMD for high-dimensional streaming data. It develops streaming, GPU-parallel, and compressed-data techniques to accelerate DMD while supporting applications such as video background modeling.
1 Introduction
- The algorithms address DMD’s high-dimensional cost, which is especially demanding when windowed computations must be repeated over streaming data.DMD has been used across fluid dynamics, neuroscience, robotics, epidemiology, and video processing, but its underlying SVD remains expensive for high-dimensional data.Source: §1 · p. 1
1.1 Contributions
- The proposed streaming DMD reuses shared computations between sequential inputs, avoiding redundant inner products in the method of snapshots SVD.The approach builds on prior observations that shared inner products can be copied rather than recalculated, and extends them to GPU-parallel compressed data streams.Source: §1 · p. 2, §1.1 · p. 2
1 Introduction
- DMD is applied to separate video foreground and background, providing a challenging benchmark alongside scientific-computing applications.Compared with RPCA, DMD requires only one SVD for the same task, whereas RPCA performs an SVD at each iteration.Source: §1 · pp. 1–2
1.1 Contributions
- The work combines streaming SVD/DMD, efficient POD-coefficient mode amplitudes, CPU and GPU implementations, and native compressed-data processing.Compressed representations can reduce CPU-to-GPU transfer and enable sparse matrix multiplications.Source: §1.1 · p. 2
- The framework includes an open-source C++ and CUDA package and evaluates performance improvements and error against standard DMD.The paper describes GPU acceleration, streaming methods, compressed formats, and empirical analysis as its main contributions.Source: §1.1 · p. 2
2 Background
The background introduces snapshot-based SVD, DMD, video background separation, and GPU computing as the foundations for streaming DMD. These methods reduce high-dimensional computations by working with smaller matrices, reusing computations, and exploiting parallel hardware.
2.1 Method of Snapshots Singular Value Decomposition (SVD)
- The method of snapshots computes the eigendecomposition of the smaller X∗X matrix for tall-skinny data, then reconstructs the SVD factors.Its economy SVD keeps U at the size of X while Σ and V are small square matrices.Source: §2.1 · p. 3
- 0.022s versus 0.119s: method-of-snapshots SVD was over 5× faster than standard SVD on the first Yale face sequence, with relative errors near 2.1e-7.The singular values and reconstructions closely agree across the tested numbers of singular values and vectors.Source: §2.1 · pp. 3–4, Figure 1 · p. 4
2.2 Dynamic Mode Decomposition
- DMD models transitions between successive snapshots by analyzing a reduced operator whose eigenvalues match those of the high-dimensional operator.The resulting dynamic modes have temporal signatures determined by their corresponding eigenvalues.Source: §2.2 · pp. 4–5
2 Background
- The background establishes streaming DMD as a computational setting where reduced matrices, reusable calculations, and parallel GPU execution address high-dimensional data.The state dimension can reach millions for HD video and tens of millions for 4K video, making direct analysis of the full operator impractical.Source: §2.2 · p. 5, §2.3 · p. 6
2.3 General Purpose GPU Computing
- GPU acceleration suits SVD and DMD because their many independent inner products can run in parallel across GPU threads.Minimizing CPU-to-GPU memory transfers is important, which naturally motivates streaming algorithms that transfer only updated data.Source: §2.2 · p. 5, §2.3 · p. 6
2.2.1 DMD for Video Background Subtraction
- DMD separates video background and foreground by associating nearly stationary modes, with λp ≈1, with background and faster modes with foreground dynamics.The decomposition represents the video using low-rank background and sparse foreground components.Source: §2.2.1 · p. 5
3 Proposed Streaming DMD Algorithm
The proposed streaming DMD suite reuses computations across sequential data updates, reducing repeated SVD/DMD cost and supporting GPU execution. It also exploits compressed representations to reduce transfer and enable sparse operations.
3 Proposed Streaming DMD Algorithm
- The algorithm suite targets repeated SVD and DMD computations for streaming data, where continually appended or removed columns can make recomputation prohibitively expensive.The methods are designed for applications including online video processing and windowed DMD on transient simulations.Source: §3 · p. 6
3.1 Streaming Method of Snapshots SVD
- O(nm^2) to O(nm) reduces streaming method-of-snapshots SVD complexity by recalculating only one row or column of X*X.This reused computation forms the backbone of the streaming DMD.Source: §3 · p. 6, §3.1 · p. 7
3.2 Streaming Dynamic Mode Decomposition
- Streaming DMD processes sequential inputs by reusing streaming-SVD intermediates and can return only the last sparse-background column during video subtraction.The DMD window advances by the number of frames requested per iteration.Source: §3.2 · p. 7
3.3 Computing Mode Amplitudes Efficiently
- POD-coefficient mode amplitudes replace high-dimensional least squares, requiring fewer GPU synchronizations and less data transfer.During streaming, only the row associated with the smallest absolute DMD eigenvalue needs calculation.Source: §3.3 · p. 8
3.4 GPU Implementation
- The GPU implementation omits explicit U computation and uses single precision to reduce space and memory usage, while MAGMA improved performance over OpenCL.OpenBLAS supports CPU linear algebra and MAGMA supports GPU LAPACK and BLAS.Source: §3.4 · p. 8
3.5 Implementation on Sparse Data
- GPU DMD can operate directly on compressed Fourier or wavelet data, reducing CPU-GPU transfer and enabling sparse matrix operations.The compressed-data procedure is proposed schematically but was not explicitly implemented in the code.Source: §3.5 · pp. 8–9, Figure 4 · p. 10
4 Results
Streaming CPU and GPU implementations improve scaling and substantially accelerate SVD, DMD, and background subtraction while retaining small relative errors and visually similar foreground results.
4.1 Performance Benchmarks
- The streaming GPU is fastest across SVD, DMD, and background subtraction, with better scaling as resolution and frame width increase.At 2560 × 1440 with 90 frames, SVD takes approximately 1.15 seconds on CPU versus .06 seconds on streaming GPU, nearly 20x faster.Source: §4.1 · p. 11, Figure 5 · p. 11
- Streaming substantially improves CPU performance, bringing it near GPU performance and reducing the need for a dedicated GPU.Streaming algorithms also scale more favorably with frame width than their non-streaming counterparts.Source: §4.1 · p. 11
- At 120 frames and fixed 1920 × 1080 resolution, streaming GPU SVD achieves around 25x speed-up over CPU SVD.CPU time is .77 seconds versus .03 seconds for streaming GPU.Source: §4.1 · p. 12
4.2 Error Analysis
- Streaming SVD and DMD retain quite small relative errors compared with standard Python implementations, even at the largest input sizes.DMD errors are somewhat larger than SVD errors because of accumulated GPU floating-point errors.Source: §4.2 · pp. 12–13, Table 1 · p. 12
- On BMC “Video 003,” streaming GPU DMD produces background-subtraction results consistent with other DMD versions, with little difference from CPU foreground output.The difference has little impact on thresholded results.Source: Table 2 · p. 12, Figure 6 · p. 12, §4.2 · p. 13
5 Discussion and Outlook
The paper presents streaming SVD and DMD algorithms with CPU and GPU implementations for real-time processing of large data streams. It reports improved computational performance with negligible accuracy loss and identifies broader real-time data-analysis applications and future extensions.
5 Discussion and Outlook
- Streaming SVD and DMD reuse calculations across frames to process large video and other data streams in real time.The approach exploits the structure of the method-of-snapshots SVD, and the implementation is planned as open-source C++ and CUDA software.Source: §5 · pp. 13–14
- The reported performance gains are accompanied by negligible accuracy loss across the evaluated datasets.The paper emphasizes streaming benefits for both GPU and non-GPU target platforms.Source: §5 · p. 13
- The method is not suitable for extreme-precision applications, although its small accuracy loss is negligible for video background modeling.This scope boundary reflects the trade-off between computational speed and precision.Source: §5 · p. 13
- Future work includes dynamic multi-column updates, startup buffering, multiple background DMD modes, and combinations with compressed or multi-resolution DMD.Using multiple background modes could improve results but would incur a performance penalty.Source: §5 · p. 13
- Real-time streaming decompositions could support applications involving LIDAR, 4K video, simulations, sensor networks, brain-machine interfaces, IoT, and augmented reality.The motivation is scalable feature extraction from data streams before collection and storage create a data mortgage.Source: §5 · pp. 13–14