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 $.

0
下载
关闭预览

相关内容

最新《自监督表示学习》报告,70页ppt
专知会员服务
85+阅读 · 2020年12月22日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
计算机视觉的不同任务
专知
5+阅读 · 2018年8月27日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Domain Representation for Knowledge Graph Embedding
Arxiv
14+阅读 · 2019年9月11日
Arxiv
17+阅读 · 2019年3月28日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
计算机视觉的不同任务
专知
5+阅读 · 2018年8月27日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Top
微信扫码咨询专知VIP会员