.png){kind=icon}
返回
A FAST DIRECT SOLVER FOR STRUCTURED LINEAR SYSTEMS BY RECURSIVE SKELETONIZATION
.png){kind=icon}
OA
AI
DOI：10.1137/120866683.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We present a fast direct solver for structured linear systems based on multilevel matrix compression. Using the recently developed interpolative decomposition of a low-rank matrix in a recursive manner, we embed an approximation of the original matrix into a larger but highly structured sparse one that allows fast factorization and application of the inverse. The algorithm extends the Martinsson-Rokhlin method developed for 2D boundary integral equations and proceeds in two phases: a precomputation phase, consisting of matrix compression and factorization, followed by a solution phase to apply the matrix inverse. For boundary integral equations which are not too oscillatory, e. g., based on the Green functions for the Laplace or low-frequency Helmholtz equations, both phases typically have complexity O(N) in two dimensions, where N is the number of discretization points. In our current implementation, the corresponding costs in three dimensions are O(N-3/2) and O(N log N) for precomputation and solution, respectively. Extensive numerical experiments show a speedup of similar to 100 for the solution phase over modern fast multipole methods; however, the cost of precomputation remains high. Thus, the solver is particularly suited to problems where large numbers of iterations would be required. Such is the case with ill-conditioned linear systems or when the same system is to be solved with multiple right-hand sides. Our algorithm is implemented in Fortran and freely available.
Keyword:
fast algorithms
multilevel matrix compression
interpolative decomposition
sparse direct solver
integral equations
fast multipole method
期刊
IF:
2.6
论文数:
5.1K
被引数:
1.8W
机构
引用论文
Effect of Exercise Training on the Mental and Physical Well-Being of Caregivers for Persons Living With Chronic Illnesses: A Systematic Review and Meta-Analysis运动训练对慢性病患者照顾者身心健康的影响: 系统综述和荟萃分析
PREAI
分享收藏The Leading Role of Association in Framework Modification of Highly Siliceous Zeolites with Adsorbed Methylamine.png)
ChemPhysChem
ChemPhysChemIF0
PREAI
分享收藏
PDB2PQR: an automated pipeline for the setup of Poisson-Boltzmann electrostatics calculationsPDB2PQR: 用于设置poisson-boltzmann静电计算的自动管道NUCLEIC ACIDS RESEARCHOAAI
NUCLEIC ACIDS RESEARCHIF13.1
OAAI分享收藏
查看更多内容