Fast orthogonal factorization for sparse matrices : theory, implementation, and application
Abstract/Contents
- Abstract
- Sparse linear systems and least-squares problems appear in various scientific applications ranging from classic domains like computational physics to growing fields like data science. In this thesis, we discuss the development, application, and parallel implementation of a novel, fast, approximate QR factorization that can be used to solve such problems. In Chapters 2 and 3, we discuss the development of our novel fast QR factorization, sparsified QR (spaQR). spaQR is a fast hierarchical solver that is built on the ideas of nested dissection, Householder QR, and low-rank compressions. By using a two-step compression scheme, spaQR reduces the size of the nested dissection separators while approximately preserving the original structure of the elimination tree. A small approximation error is introduced which can be controlled by the user. We show that spaQR computes the factorization in near-linear time and takes linear time to solve with a vector. We perform numerical benchmarks to show that spaQR exhibits near-linear scalings and is an efficient preconditioner for sparse linear systems arising in CFD applications, least-squares problems arising in PDE constrained optimization problems, and three different problems from computer graphics --- laplacian mesh reconstruction, conformal mapping, and as-rigid-as-possible deformation. We demonstrate that spaQR is faster than the standard techniques for these problems and hence can be an asset to these applications. In Chapter 5, we develop a new task-based distributed memory implementation of spaQR using the TaskTorrent runtime system. We study the strong scaling behavior of our solver on a few large linear systems and least-squares problems on up to 1024 cores. We show that spaQR scales well for moderately sized 3D problems. The rank-revealing QR factorization (RRQR), which is used to provide the low-rank approximations acts as a bottleneck on larger problems. In Chapter 6, we present a new parallel task-based algorithm for randomized low-rank factorizations of a matrix. We present a set of benchmarks comparing our implementation with similar implementations in state-of-art platforms like StarPU, PaRSEC, and ScaLAPACK. Finally, we incorporate the randomized low-rank factorization in place of the RRQR and demonstrate that it improves the scalability of spaQR for large 3D problems.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Gnanasekaran, Abeynaya |
|---|---|
| Degree supervisor | Darve, Eric |
| Thesis advisor | Darve, Eric |
| Thesis advisor | Alonso, Juan José, 1968- |
| Thesis advisor | Gerritsen, Margot (Margot G.) |
| Degree committee member | Alonso, Juan José, 1968- |
| Degree committee member | Gerritsen, Margot (Margot G.) |
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Abeynaya Gnanasekaran. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/yh423ny0931 |
Access conditions
- Copyright
- © 2022 by Abeynaya Gnanasekaran
Also listed in
Loading usage metrics...