  We define the notion of effective stiffness and show that it can used to
build sparsifiers, algorithms that sparsify 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 a high quality preconditioner that can be used to solve the
linear system in a small number of iterations. 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 solve, there has
been limited success in designing fast solvers for finite element systems, and
previous algorithms usually target discretization of limited class of PDEs like
scalar elliptic or 2D trusses. Our sparsifier is general; it applies to a wide
range of finite-element discretizations. A sparsifier does not constitute a
complete linear solver. To construct a solver, one needs additional components
(e.g., an efficient elimination or multilevel scheme for the sparsified
system). Still, sparsifiers have been a critical tools in efficient SDD
solvers, and we believe that our sparsifier will become a key ingredient in
future fast finite-element solvers.
