Browsing by Subject "Numerical PDEs"

Now showing 1 - 1 of 1

Randomized algorithms for the efficient solution of elliptic PDEs on modern architectures
(2023-12) Yesypenko, Anna; Biros, George; Martinsson, Per-Gunnar; Ghattas, Omar; Engquist, Bjorn; Willcox, Karen E
This thesis describes techniques for efficiently and robustly computing approximate solutions to elliptic partial differential equations (PDEs). It presents novel algorithms for solving linear systems that exploit randomized methods in linear algebra to attain high computational efficiency and scalability. These algorithms are designed to leverage a variety of compute kernels, such as vectorization and specialized hardware acceleration features found on modern architectures. The ideas in this thesis demonstrate viable paths to re-envisioning classical linear solvers in a changing hardware landscape. The unifying theme of the work is the use of hierarchical matrices (𝓗-matrices) to accelerate key compute kernels. The term 𝓗-matrix refers to a matrix that can hierarchically be tessellated into submatrices in such a way that each submatrix is either of low numerical rank, or small enough that it can be stored densely. Using 𝓗-matrix representation for a matrix of size 𝑁 × 𝑁 allows the complexity of matrixvector products and matrix inversion to have linear, or close to linear, complexity when dense linear algebra would require 𝒪(𝑁²) and 𝒪(𝑁³) operations, respectively. In this thesis, 𝓗-matrix structure is used to represent discretized integral equations, as well as to represent large dense matrices that arise in sparse direct solvers for discretized PDEs. The thesis contains three key contributions. First, a novel fast multipole method (FMM) is presented. This is a fast algorithm for applying an 𝓗-matrix to a vector, with applications in the numerical solution of integral equation formulations of PDEs using iterative methods. The method is based on linear algebraic tools such as randomized low rank approximation, and “skeleton representations” of far-field interactions. Its key feature is significantly simplified data structure compared to the original FMM. Second, a sparse direct solver for discretized PDEs is presented, which is compatible with a variety of PDE discretizations. This work addresses a critical limitation of sparse direct solvers, which is that techniques such as LU and Cholesky lead to factors that are far less sparse than the original matrix; we ameliorate this “fill-in” effect by exploiting 𝓗-matrix structure in the dense blocks that arise. This solver distinguishes itself from related work by using a decomposition of the computational domain into slabs. This approach leads to simplified data structures, which facilitate parallelization and also makes the scheme more amenable to using GPU acceleration for improved performance. Third, a novel algorithm for the simultaneous compression and LU factorization of a particular class of 𝓗-matrices is presented. This process is achieved in linear time from black-box matrix-vector products of an operator with 𝓗-matrix structure. The work builds upon a previously proposed algorithm for “strong recursive skeletonization” but provides significant simplifications and accelerations. The work has applications in the direct solution of boundary integral equations and in sparse direct solvers for discretized PDEs.