  We give the first mathematically rigorous analysis of an emerging approach to
finite element analysis (see, e.g., Bauer et al. [Appl. Numer. Math., 2017]),
which we hereby refer to as the surrogate matrix methodology. This methodology
is based on the piece-wise smooth approximation of the matrices involved in a
standard finite element discretization. In particular, it relies on the
projection of smooth so-called stencil functions onto high-order polynomial
subspaces. The performance advantage of the surrogate matrix methodology is
seen in constructions where each stencil function uniquely determines the
values of a significant collection of matrix entries. Such constructions are
shown to be widely achievable through the use of locally-structured meshes.
Therefore, this methodology can be applied to a wide variety of physically
meaningful problems, including nonlinear problems and problems with curvilinear
geometries. Rigorous a priori error analysis certifies the convergence of a
novel surrogate method for the variable coefficient Poisson equation. The
flexibility of the methodology is also demonstrated through the construction of
novel methods for linear elasticity and nonlinear diffusion problems. In
numerous numerical experiments, we demonstrate the efficacy of these new
methods in a matrix-free environment with geometric multigrid solvers. In our
experiments, up to a twenty-fold decrease in computation time is witnessed over
the classical method with an otherwise identical implementation.
