Fast and scalable hierarchical linear solvers
Abstract/Contents
- Abstract
- Linear solvers are a key component of scientific computing. In Chapter 2 we develop a new algorithm for the fast solution of large, sparse linear systems, spaND (sparsified Nested Dissection). spaND uses low-rank approximations to reduce the size of the Nested Dissection separators without creating any fill-in. The result is an approximate factorization that can be used as an efficient preconditioner. Unlike many preconditioners, spaND works on a large class of matrices. We perform several numerical experiments to evaluate this algorithm. We demonstrate that a version using orthogonal factorization and block-diagonal scaling takes fewer CG iterations to converge than the previously developed Hierarchical Interpolative Factorization algorithm on nearly all SPD problems from the SuiteSparse matrix collection. Furthermore, we prove that this algorithm is guaranteed to never break down if the input matrix is SPD. We evaluate the algorithm on some large problems, both SPD and unsymmetric, and show that it exhibits near-linear scalings. In Chapter 3, we tackle the problem of task-based parallel computing. Runtime systems, where the user expresses computations as tasks with inputs and outputs, offer a solution to programming increasingly large and complex modern computers. However, their adoption has been so far very limited. In this work, we present TaskTorrent, a lightweight distributed task-based runtime in C++. TaskTorrent uses a parametrized task graph to express the task DAG, and one-sided active messages to trigger remote tasks asynchronously. TaskTorrent is very easy to learn, easy to integrate into existing codes, and has minimal overhead. We explain the API and the implementation. We perform a series of benchmarks against StarPU, Regent and ScaLAPACK. Both TaskTorrent and StarPU outperform ScaLAPACK, and TaskTorrent exhibits good strong and weak scalings. We then combine TaskTorrent with spaND in Chapter 4, explain the implementation, and run the resulting algorithm on a few large problems, efficiently using up to 9000 cores. This shows that spaND scales very well when the ranks grow slowly with the problem size and that TaskTorrent has no problems exploring very large DAGs. In Chapter 5, we study the problem of kernel matrix factorization. In this work, we develop the Skeletonized Interpolation algorithm, a new way to build a low-rank factorization of kernel matrices. This is done by first sampling the kernel function at new interpolation points, then selecting a subset of those using a CUR decomposition, and finally using this reduced set of points as pivots for a rank-revealing LU-type factorization. We explain how this implicitly builds an optimal interpolation basis for the kernel under consideration and show the asymptotic convergence of the algorithm. Finally, we demonstrate on numerical examples that it performs very well in practice, allowing us to obtain ranks nearly equal to the optimal rank at a fraction of the cost of the naive algorithm. Finally, in Chapter 6, we study a parametrized least-square problem with a weighted norm over an arbitrary subspace. We show that the solutions belong to a low-dimensional subspace, independent from the weights and the right-hand-side, of dimension IndA(S) = dim(S + AS) − dim(S), a quantity we call the index of invariance. This result implies the low-dimensionality result from Hallman & Gu (2018). We furthermore study the tightness of the bound and show that, as one varies the weights, the solutions can belong to a subspace of dimension one even if IndA(S) is greater than one. Finally, we exhibit sufficient conditions on A (such as A being SPD) such that, as one varies both the right-hand-side and the weights, the solutions belong to a space of dimension IndA(S).
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 | 2020; ©2020 |
| Publication date | 2020; 2020 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Cambier, Léopold Yves Leon S |
|---|---|
| Degree supervisor | Darve, Eric |
| Thesis advisor | Darve, Eric |
| Thesis advisor | Alonso, Juan José, 1968- |
| Thesis advisor | Boman, Erik |
| Degree committee member | Alonso, Juan José, 1968- |
| Degree committee member | Boman, Erik |
| Associated with | Stanford University, Institute for Computational & Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Léopold Cambier. |
|---|---|
| Note | Submitted to the Institute for Compututional & Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2020. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2020 by Leopold Yves Leon S Cambier
Also listed in
Loading usage metrics...