Rank‐structured approximation of some Cauchy matrices with sublinear complexity
Rank‐structured approximation of some Cauchy matrices with sublinear complexity
复制标题
一些具有次线性复杂度的柯西矩阵的Rank-结构化近似
DOI：
10.1002/nla.2526
复制
发表时间：
2023
影响因子：
4.3
通讯作者：
Xia, Jianlin
中科院分区：
文献类型：
--
作者：
Lepilov, Mikhail;Xia, Jianlin
在本文中，我们考虑一种重要类型的柯西矩阵的秩结构近似。这种近似在一些结构化矩阵方法中起着关键作用，例如稳定高效的直接求解器以及托普利茨矩阵和某些核矩阵的其他算法。对于这样一个大小为 n$$ n $$ 的矩阵，以前的等级结构近似（特别是分层半可分离，或 HSS 近似）的成本至少为 O(n)$$ O(n) $$ 复杂度。在这里，我们展示如何构建具有次线性（具体来说，O(log3n)$$ O\left({\log}^3n\right) $$）复杂度的 HSS 近似。主要思想包括广泛的计算重用和分析远场压缩策略。每个层次级别的低秩压缩仅限于单个非对角块行，然后将所得的基础矩阵重新用于其他非对角块行以及非对角块列。非对角线块之间的关系经过严格分析。远场压缩使用分析代理点方法，我们优化一些参数的选择，以获得准确的低秩近似。基础重用思想和由此产生的分析分层压缩方案都可以推广到其他一些内核矩阵，并且对于加速相关的秩结构近似很有用（尽管不是矩阵向量乘法等后续操作）。
In this article, we consider the rank‐structured approximation of one important type of Cauchy matrix. This approximation plays a key role in some structured matrix methods such as stable and efficient direct solvers and other algorithms for Toeplitz matrices and certain kernel matrices. Previous rank‐structured approximations (specifically hierarchically semiseparable, or HSS, approximations) for such a matrix of size n$$ n $$ cost at least O(n)$$ O(n) $$ complexity. Here, we show how to construct an HSS approximation with sublinear (specifically, O(log3n)$$ O\left({\log}^3n\right) $$) complexity. The main ideas include extensive computation reuse and an analytical far‐field compression strategy. Low‐rank compression at each hierarchical level is restricted to just a single off‐diagonal block row, and a resulting basis matrix is then reused for other off‐diagonal block rows as well as off‐diagonal block columns. The relationships among the off‐diagonal blocks are rigorously analyzed. The far‐field compression uses an analytical proxy point method where we optimize the choice of some parameters so as to obtain accurate low‐rank approximations. Both the basis reuse ideas and the resulting analytical hierarchical compression scheme can be generalized to some other kernel matrices and are useful for accelerating relevant rank‐structured approximations (though not subsequent operations like matrix‐vector multiplications).
登录
查看更多内容
使用格林公式和求积的积分算子的低阶近似
影响因子：
2.1
作者：
S. Börm;J. Gördes
通讯作者：
J. Gördes
DOI：
10.4208/csiam-am.2021.nla.02
发表时间：
2021
期刊：
CSIAM Transactions on Applied Mathematics
影响因子：
--
作者：
Xia, Jianlin
通讯作者：
Xia, Jianlin
DOI：
10.1553/etna_vol54s581
发表时间：
2021
期刊：
ETNA - Electronic Transactions on Numerical Analysis
影响因子：
--
作者：
Difeng Cai;J. Xia
通讯作者：
Difeng Cai;J. Xia
DOI：
10.1109/ipdps47924.2020.00082
发表时间：
2020-05
期刊：
2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
Lucas Erlandson;Difeng Cai;Yuanzhe Xi;Edmond Chow
通讯作者：
Lucas Erlandson;Difeng Cai;Yuanzhe Xi;Edmond Chow