Sparse factorizations and scalable algorithms for differential and integral operators

Placeholder Show Content


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.


Type of resource text
Form electronic; electronic resource; remote
Extent 1 online resource.
Publication date 2017
Issuance monographic
Language English


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


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

© 2017 by Yingzhou Li
This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).

Also listed in

Loading usage metrics...