A Note on QR-Based Model Reduction: Algorithm, Software, and Gravitational Wave Applications
For practitioners needing efficient model reduction of large-scale systems, this work provides a theoretically grounded, scalable QR-based alternative to POD with equivalent error guarantees.
The authors show that rank-revealing QR (RRQR) can achieve the same error estimate as POD, and that iterative modified Gram Schmidt with pivoting is equivalent to the greedy reduced basis method. They present a parallel MPI/OpenMP code that scales to 32,768 cores and handles matrices up to half a terabyte, demonstrated on gravitational wave model reduction.
While the proper orthogonal decomposition (POD) is optimal under certain norms it's also expensive to compute. For large matrix sizes, it is well known that the QR decomposition provides a tractable alternative. Under the assumption that it is rank--revealing QR (RRQR), the approximation error incurred is similar to the POD error and, furthermore, we show the existence of an RRQR with exactly same error estimate as POD. To numerically realize an RRQR decomposition, we will discuss the (iterative) modified Gram Schmidt with pivoting (MGS) and reduced basis method by employing a greedy strategy. We show that these two, seemingly different approaches from linear algebra and approximation theory communities are in fact equivalent. Finally, we describe an MPI/OpenMP parallel code that implements one of the QR-based model reduction algorithms we analyze. This code was developed with model reduction in mind, and includes functionality for tasks that go beyond what is required for standard QR decompositions. We document the code's scalability and show it to be capable of tackling large problems. In particular, we apply our code to a model reduction problem motivated by gravitational waves emitted from binary black hole mergers and demonstrate excellent weak scalability on the supercomputer Blue Waters up to 32,768 cores and for complex, dense matrices as large as 10,000-by-3,276,800 (about half a terabyte in size).