Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs (Q2845613)

The relation NEWLINE\[NEWLINE(Au,v)=\sum_{{k=(i,j) \in \mathcal{E}}}w_k(u_i-u_j)(v_i-v_j)=(Bu,Bv)NEWLINE\]NEWLINE defines a weighted graph Laplacian, where \(\mathcal{G}=(\mathcal{V}, \mathcal{E})\) is a weighted connected graph with the set of vertices \(\mathcal{V}\) and the set of edges \(\mathcal{E}\). Denoting the cardinality of a finite set \(\mathcal{X}\) by \(|\mathcal{X}|\) and the diagonal matrix with entries \(w_k\) by \(D: \mathbb{R}^{|\mathcal{E}|} \mapsto \mathbb{R}^{|\mathcal{E}|}\) then the matrix generated by this equality can be decomposed as NEWLINE\[NEWLINEA=B^TDB.NEWLINE\]NEWLINE Various discretisations of elliptic partial differential equations, e.g. finite element- or finite difference-discretisations, result in the algebraic problems NEWLINE\[NEWLINEAu=fNEWLINE\]NEWLINE with a given \(f\) and with such weighted graph Laplacians. The paper deals with the construction of an algebraic multilevel preconditioner based on piecewise constant coarse vector spaces obtaining by matching in graphs. The convergence rate of an two-level method is derived and the sharpness of the theoretical estimates is confirmed by numerical tests.