A Note on QR-Based Model Reduction: Algorithm, Software, and Gravitational Wave Applications

Harbir Antil, Dangxing Chen, Scott E. Field

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.

Algorithm 1: Proper Orthogonal Decomposition (POD) via SVD.

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

Abstract

While the proper orthogonal decomposition (POD) is optimal under certain norms, its also expensive to compute. For large matrix sizes, the QR decomposition provides a tractable alternative. Under the assumption that it is a rank-revealing QR (RRQR), the approximation error incurred is similar to the POD error; furthermore, the authors show the existence of an RRQR with exactly the same error estimate as POD. To numerically realize an RRQR decomposition, they discuss the (iterative) modified Gram Schmidt with pivoting and reduced basis methods. They show that these two seemingly different approaches are equivalent. They then describe an MPI/OpenMP parallel code that implements one of the QR-based model reduction algorithms analyzed, and document the codes scalability for large problems, such as gravitational waves, and demonstrate excellent scalability up to 32,768 cores and, for complex dense matrices, as large as 10,000x3,276,800.
BibTeX
@inproceedings{antil2018note,
  author = {Harbir Antil and Dangxing Chen and Scott E. Field},
  title = {{A Note on QR-Based Model Reduction: Algorithm, Software, and Gravitational Wave Applications}},
  booktitle = {Comput. Sci. Eng},
  year = {2018},
  url = {https://openreview.net/forum?id=tFV5BXHU8W},
}
Figure