Multilevel preconditioning of graph-Laplacians: Polynomial approximation of the pivot blocks inverses

P. Boyanova, I. Georgiev, S. Margenov, L. Zikatanov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 × 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 × 2 splittings. Such approximations are obtained via the best polynomial approximation of x -1 in L 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.

Original languageEnglish (US)
Pages (from-to)1964-1971
Number of pages8
JournalMathematics and Computers in Simulation
Issue number10
StatePublished - Jun 1 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)
  • Numerical Analysis
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Multilevel preconditioning of graph-Laplacians: Polynomial approximation of the pivot blocks inverses'. Together they form a unique fingerprint.

Cite this