Mathematics – Numerical Analysis
Scientific paper
2012-04-18
Mathematics
Numerical Analysis
21 pages including figures
Scientific paper
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 proven to have convergence rate $\approx (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.
Brannick James
Chen Yao
Kraus Johannes
Zikatanov Ludmil
No associations
LandOfFree
Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-411732