@TechReport{ it:2011-030,
author = {P. Boyanova and I. Georgiev and S. Margenov and L.
Zikatanov},
title = {Multilevel Preconditioning of Graph-{L}aplacians:
Polynomial Approximation of the Pivot Blocks Inverses},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Scientific Computing},
year = {2011},
number = {2011-030},
month = nov,
abstract = {We consider the discrete system resulting from mixed
finite element approximation of a second-order elliptic
boundary value problem with Crouzeix-Raviart non-conforming
elements for the vector valued unknown function and
piece-wise constants for the scalar valued unknown
function. Since the mass matrix corresponding to the vector
valued variables is diagonal, these unknowns can be
eliminated exactly. Thus, the problem of designing an
efficient algorithm for the solution of the resulting
algebraic system is reduced to one of constructing an
efficient algorithm for a system whose matrix is a
graph-Laplacian (or weighted graph-Laplacian).
We propose a preconditioner based on an algebraic
multilevel iterations (AMLI) algorithm. The hierarchical
two-level transformations and the corresponding $2\times 2$
block splittings of the graph-Laplacian needed in an AMLI
algorithm are introduced locally on macroelements. Each
macroelement is associated with an edge of a coarser
triangulation. To define the action of the preconditioner
we employ polynomial approximations of the inverses of the
pivot blocks in the $2\times 2$ splittings. Such
approximations are obtained via the best polynomial
approximation of $x^{-1}$ in $L_{\infty}$ norm on a finite
interval. Our construction provides sufficient accuracy and
moreover, guarantees that each pivot block is approximated
by a positive definite matrix polynomial.
One possible application of the constructed efficient
preconditioner is in the numerical solution of unsteady
Navier-Stokes equations by a projection method. It can also
be used to design efficient solvers for problems
corresponding to other mixed finite element discretizations.}
}