Improving Multifrontal Methods by Means of Block Low-Rank Representations
Improving Multifrontal Methods by Means of Block Low-Rank Representations
复制标题
DOI：
10.1137/120903476
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
P. Amestoy;C. Ashcraft;O. Boiteau;A. Buttari;J. L’Excellent;Clément Weisbecker
中科院分区：
文献类型：
--
作者：
P. Amestoy;C. Ashcraft;O. Boiteau;A. Buttari;J. L’Excellent;Clément Weisbecker
来自椭圆型偏微分方程（PDE）的矩阵已被证明具有低秩性质：其Schur补的良好定义的非对角块可以由低秩乘积近似。给定给予块几何意义的矩阵的适当排序，可以使用SVD或秩揭示QR因子分解来计算这样的近似。由此产生的表示提供了大量减少的内存需求，并提供了有效的方法来执行许多基本的密集代数运算。已经提出了几种策略来利用这一特性。我们提出了一种低秩格式，称为块低秩（BLR），并解释了它如何可以用来减少内存占用和复杂性的直接求解器的稀疏矩阵的多波前方法的基础上。我们目前的实验结果表明，如何BLR格式提供的增益是与分层格式，如分层矩阵（H矩阵）和分层半可分离（HSS矩阵），但提供了更大的灵活性和易用性，这是必不可少的通用的背景下，代数求解器。
Matrices coming from elliptic Partial Differential Equations (PDEs) have been shown to have a low-rank property: well defined off-diagonal blocks of their Schur complements can be approximated by low-rank products. Given a suitable ordering of the matrix which gives to the blocks a geometrical meaning, such approximations can be computed using an SVD or a rank-revealing QR factorization. The resulting representation offers a substantial reduction of the memory requirement and gives efficient ways to perform many of the basic dense algebra operations. Several strategies have been proposed to exploit this property. We propose a low-rank format called Block Low-Rank (BLR), and explain how it can be used to reduce the memory footprint and the complexity of direct solvers for sparse matrices based on the multifrontal method. We present experimental results that show how the BLR format delivers gains that are comparable to those obtained with hierarchical formats such as Hierarchical matrices (H matrices) and Hierarchically Semi-Separable (HSS matrices) but provides much greater flexibility and ease of use which are essential in the context of a general purpose, algebraic solver.