Abstract
Building reduced-order models (ROMs) for high-fidelity physics simulations often requires extracting low-rank approximations from massive "snapshot" matrices. While Proper Orthogonal Decomposition (POD) via Singular Value Decomposition (SVD) is the optimal approach, its computational cost is prohibitive for terabyte-scale datasets. This paper explores Rank-Revealing QR (RRQR) decomposition as a highly efficient, scalable alternative. We prove the mathematical equivalence of the Reduced Basis greedy algorithm and Modified Gram-Schmidt with pivoting and introduce greedycpp, a massively parallel software package. Our results demonstrate near-perfect scaling on up to 32,768 cores for gravitational wave datasets.
Introduction
In computational science and engineering, building reduced-order models (ROMs) is essential for speeding up complex simulations. This is typically done by extracting a low-rank approximation from a massive "snapshot" matrix of model evaluations. The gold standard for this task is the Singular Value Decomposition (SVD), or Proper Orthogonal Decomposition (POD), which provides the mathematically optimal low-rank approximation.
However, as shown in Algorithm 1, POD requires computing the full or partial SVD. For extremely large datasets, this becomes a significant bottleneck due to high memory requirements, high floating-point operation (FLOP) counts, and poor scalability on modern many-core supercomputers. This work addresses these challenges by proposing QR decomposition as a computationally tractable alternative that maintains the accuracy required for high-fidelity physics applications.
Methodology
The authors bridge theoretical linear algebra and practical software engineering through several key contributions:
Theoretical Equivalence
A central finding is the mathematical proof that two seemingly distinct techniques—Modified Gram-Schmidt (MGS) with column pivoting (popular in linear algebra) and the Reduced Basis (RB) greedy algorithm (popular in approximation theory)—are actually equivalent when applied to finite-dimensional vector spaces. This unifies the theoretical error bounds developed by the numerical analysis community with the practical algorithms of the linear algebra community.
Reconstruction Algorithm
To match the optimal accuracy of POD at a lower cost, a hybrid approach is proposed: perform a partial QR decomposition followed by a small SVD on the resulting reduced matrix. This "reconstruction" achieves POD-level precision with significantly reduced computational overhead.
The greedycpp Software
To implement these methods at scale, the authors developed greedycpp, an open-source, hybrid MPI/OpenMP parallelized C++ code. To ensure numerical stability on large datasets, the code utilizes Hoffman’s Iterated Modified Gram-Schmidt (IMGS) algorithm, preventing the loss of orthogonality common in standard Gram-Schmidt implementations.
Experimental Setup: Gravitational Wave Data
The software was evaluated using simulated gravitational wave waveforms emitted by merging binary black holes, generated via the IMRPhenomPv2 model. To test extreme scalability, the snapshot matrix was generated directly in memory across distributed nodes. The largest test case involved a dense, complex-valued matrix of 10,000 rows by 3,276,800 columns, totaling approximately 0.5 Terabytes.
Key Results and Discussion
The performance of greedycpp on the Blue Waters supercomputer highlights the advantages of the QR-based approach:
- Massive Throughput: The code successfully performed a column-pivoted QR decomposition to extract 100 basis vectors from the 0.5 TB matrix in just 13.5 seconds.
- Excellent Weak Scaling: The algorithm demonstrated near-perfect weak scaling up to 32,768 cores. As the matrix size increased linearly with the number of cores, the runtime experienced only a very mild logarithmic growth.
- Hybrid Parallelization Wins: The hybrid MPI/OpenMP approach significantly reduced inter-node communication overhead. For a 1,000 x 240,000 matrix on 370 cores, the hybrid code maintained a strong scaling efficiency of ~62%, vastly outperforming the pure MPI version.
The authors also prove the existence of an "optimal" RRQR decomposition that yields the exact same 2-norm approximation error as the optimal (but expensive) POD/SVD, confirming that scalability does not necessitate a sacrifice in accuracy.
Conclusion and Future Work
While QR-based methods offer superior scalability for massive datasets, sequential orthogonalization remains a bottleneck for smaller matrices as it cannot easily leverage highly optimized BLAS-3 (matrix-matrix) routines. Future work will explore alternative orthogonalization algorithms like Hoffman's "CMGSI," offloading heavy vector-vector product computations to specialized accelerator hardware (like GPUs), and developing new global pivot selection criteria that allow the pivot search and orthogonalization to overlap asynchronously.
Summary updated