Sparse factorizations and scalable algorithms for differential and integral operators
Abstract/Contents
- Abstract
- Sparse factorizations and scalable algorithms for elliptic differential operators and Fourier integral operators (FIOs) are presented in the defense. The former operators are solved by the distributed-memory hierarchical interpolative factorization (DHIF) whereas the later operators are addressed by the butterfly factorization. By exploiting locality and certain low-rank properties of the elliptic differential operators, the hierarchical interpolative factorization achieves quasi-linear complexity for factorizing the discrete positive definite elliptic differential operator and linear complexity for solving the associated linear system. In this dissertation, the DHIF is introduced as a scalable and distributed-memory implementation of the hierarchical interpolative factorization. The DHIF organizes the processes in a hierarchical structure and keeps the communication as local as possible. The computation complexity is O(N/P log N) and O(N/P) for constructing and applying the DHIF, respectively, where N is the size of the problem and P is the number of processes. Extensive numerical examples are performed on the NERSC Edison system with up to 8192 processes. The numerical results agree with the complexity analysis and demonstrate the efficiency and scalability of the DHIF. The butterfly factorization is a data-sparse approximation for the FIOs as well as other matrices that satisfy a complementary low-rank property. The factorization can be constructed efficiently if either fast algorithms for applying the matrix and its adjoint are available or the entries of the matrix can be sampled individually. For an N by N matrix, the resulting factorization is a product of O(log N) sparse matrices, each with O(N) non-zero entries. Hence, it can be applied rapidly in O(N log N) operations. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms. For the kernel matrices of multidimensional FIOs, for which the complementary low-rank property is usually not satisfied due to a singularity at the origin, we extend this factorization by combining it with a multiscale decomposition of the integration domain to overcome the singularity. Numerical results are provided to demonstrate the efficiency of the proposed algorithms as well.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Li, Yingzhou | |
|---|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. | |
| Primary advisor | Ying, Lexing | |
| Thesis advisor | Ying, Lexing | |
| Thesis advisor | Ryzhik, Leonid | |
| Thesis advisor | Yang, Chao | |
| Advisor | Ryzhik, Leonid | |
| Advisor | Yang, Chao |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Yingzhou Li. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Yingzhou Li
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...