Effective Stiffness: Generalizing Effective Resistance Sampling to Finite Element Matrices

We define the notion of effective stiffness and show that it can used to design algorithms for solving linear systems arising from finite-element discretizations of PDEs. In particular, we show that sampling O(n log n) elements according to probabilities derived from effective stiffnesses yields an high quality preconditioner that can be used to solve the linear system efficiently. Effective stiffness generalizes the notion of effective resistance, a key ingredient of recent progress in developing nearly linear symmetric diagonally dominant (SDD) linear solvers. Solving finite elements problems is of considerably more interest than the solution of SDD linear systems, since the finite element method is frequently used to numerically solve PDEs arising in scientific and engineering applications. Unlike SDD systems, which are relatively easy to precondition, there has been limited success in designing fast solvers for finite element systems. Contrary to previous attempts, which usually target discretization of limited class of PDEs like scalar elliptic or 2D trusses, our method targets a very wide range of finite element discretizations, utilizing only some basic algebraic-combinatorial properties of the matrices arising from such discretizations.

By: Haim Avron, Sivan Toledo

Published in: RC25187 in 2011


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .