期刊
SIAM JOURNAL ON NUMERICAL ANALYSIS
卷 51, 期 3, 页码 1805-1827出版社
SIAM PUBLICATIONS
DOI: 10.1137/120876083
关键词
multilevel preconditioning; graph Laplacian; matching in graphs; aggregation
资金
- National Science Foundation [DMS-0810982, OCI-0749202]
- Austrian Science Fund [P22989-N18]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1217142] Funding Source: National Science Foundation
- Austrian Science Fund (FWF) [P 22989] Funding Source: researchfish
- Austrian Science Fund (FWF) [P22989] Funding Source: Austrian Science Fund (FWF)
This paper presents estimates of the convergence rate and complexity of an algebraic multilevel preconditioner based on piecewise constant coarse vector spaces applied to the graph Laplacian. A bound is derived on the energy norm of the projection operator onto any piecewise constant vector space, which results in an estimate of the two-level convergence rate where the coarse level graph is obtained by matching. The two-level convergence of the method is then used to establish the convergence of an algebraic multilevel iteration that uses the two-level scheme recursively. On structured grids, the method is proved to have convergence rate approximate to (1 - 1/log n) and O(n log n) complexity for each cycle, where n denotes the number of unknowns in the given problem. Numerical results of the algorithm applied to various graph Laplacians are reported. It is also shown that all the theoretical estimates derived for matching can be generalized to the case of aggregates containing more than two vertices.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据