In this talk, I will discuss our recent developments on fast randomized
structured direct methods for large sparse discretized PDEs. The methods
use some structures in practical problems as supported by the fast
multipole method (FMM), and utilizes techniques such as advanced sparse
matrix factorization, randomized sampling, and hierarchically low-rank
approximations.

We incorporate randomization into sparse direct solvers for the purposes
of both higher efficiency and better flexibility than some existing
structured solvers. We show that our direct solvers can achieve nearly
O(n) complexity for some discretized PDEs (such as Helmholtz equations)
in 2D, and O(n)~O(n^{4/3}) complexity in 3D (instead of O(n^2)
classically). The solution costs and memory requirements are about O(n)
for both 2D and 3D, which makes the methods very attractive for
preconditioning and for problems with many right-hand sides such as
seismic imaging.

The insensitivity of the solutions to parameters such as frequencies in
some problems is discussed. The stability and accuracy analysis for the
methods is given. We prove that our methods can generally be more stable
than some standard matrix computations.

We also study various important generalizations and applications, such as
O(n) cost methods for sparse selected inversion (finding diagonal or other
entries of a sparse matrix), matrix-free direct solutions, factorization
update for multiple frequencies, etc.