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.