Speaker: 

Jianlin Xia

Institution: 

Purdue University

Time: 

Monday, May 16, 2016 - 4:00pm to 5:00pm

Host: 

Location: 

RH306

The study of matrix structures makes it feasible to quickly solve some large discretized PDEs and integral equations. In particular, direct factorizations of some 2D and 3D elliptic problems can reach nearly linear complexity. Here, we show a framework that can be used to unify dense and sparse structured direct solvers, which are traditionally thought to be very distinct subjects. Such a unification makes it feasible to design new multi-dimensional structures that can conveniently handle sophisticated structures in dense 2D and 3D discretized problems. More specifically, we propose multi-layer hierarchically semiseparable (MHS) structures that integrate multiple layers of rank and tree structures in a recursive sparsification-localization strategy. We lay out theoretical foundations for MHS structures and justify the feasibility of MHS approximations for these dense matrices. Rigorous rank bounds for the rank structures are given. Representative subsets of mesh points are used to illustrate the multi-layer structures as well as the fast structured factorization. The framework makes it natural and convenient to 
(1) share ideas between dense and sparse direct solvers;
(2) perform stability and error analysis and reuse algorithm design based on simple hierarchical structures;
(3) establish intrinsic connections to other methods such as eigenvalue solvers and even multigrid methods.