A new framework is proposed to study rank-structured matrices arising from discretizations of 2D and 3D elliptic operators. In particular, we introduce the notion of a graph-induced rank structure (GIRS) which aims to capture the fine low rank structures which appear in sparse matrices and their inverses in terms of the adjacency graph $\mathbb{G}$. We show that the GIRS property is invariant under inversion, and hence any effective representation of the inverse of GIRS matrices would lead to effective solvers. Starting with the observation that sequentially semi-separable (SSS) matrices form a good candidate for representing GIRS matrices on the line graph, we propose two extensions of SSS matrices to arbitrary graphs: Dewilde-van der Veen (DV) representations and $\mathbb{G}$-semi-separable ($\mathbb{G}$-SS) representations. It is shown that both these representations come naturally equipped with fast solvers where the solve complexity is commensurate to fast sparse Gaussian elimination on the graph $\mathbb{G}$, and $\mathbb{G}$-SS representations have a linear time multiplication algorithm. We show the construction of these representations to be highly nontrivial by determining the minimal $\mathbb{G}$-SS representation for the cycle graph $\mathbb{G}$. To obtain a minimal representation, we solve an exotic variant of a low-rank completion problem.
翻译:提议一个新的框架来研究由 2D 和 3D 椭圆形操作器的离散产生的分级结构矩阵。 特别是, 我们引入了图形诱导的级别结构概念( GIRRS ), 旨在捕捉在稀少的矩阵中出现的精细低级结构, 及其在相邻图$\ mathbb{G}$的反面结构。 我们显示, GIRS 属性的不变化性处于倒置状态, 因此, GIRS 矩阵的任何反面代表将带来有效的解答器 。 从以下观察开始: 连续半分离的矩阵构成代表线形图上GIRS 矩阵的良好候选对象, 我们提议将 SSS 矩阵的两个扩展到任意图上: Dewilde-van der Veen (DV) 表示和 $\ mathb{G} 表示( mathb{G} $-semi- sepal- 表达式。 这两种表达式都自然地配有快速解算器的解算器, 在 $ G\ mathral_ a rualalalalal exresulation ex=a exmal_ a broup a broupal $.