Efficient solution of lattice equations by the recovery method. I: Scalar elliptic problems (Q1780889)

The authors describe their work in the following way. ``An efficient solver for high dimensional lattice equations will be introduced. We will present a new concept, the recovery method, to define a bilinear form on the continuous level which has equivalent energy as the original lattice equation. The finite element discretisation of the continuous bilinear form will lead to a stiffness matrix which serves as an quasi-optimal preconditioner for the lattice equations.'' For definiteness, the authors focus on a heat conductivity model, but the analysis is easily generalized. The recovery method consists of several steps. Start with an arbitrary lattice defined by a set of nodal points \(\Theta\) and edges \(\mathcal E\) and a symmetric, positive definite bilinear form \(B(u,v)\) defined for lattice functions \(u\) and \(v\). The nodal set \(\Theta\) is used to generate a finite element type mesh \({\mathcal G}_{FE}\) using Delaunay/Voronoi methods. This process introduces a new edge set \({\mathcal E}_{FE}\) that is likely larger than \(\mathcal E\) but not a superset of \(\mathcal E\). The form \(B(u,v)\) is extended as \(B_{FE}(u,v)\) to \({\mathcal G}_{FE}\) in such a way that \[ 1/C B(u,v) \leq B_{FE}(u,v) \leq C B(u,v) \tag{*} \] for a constant \(C\) that is explicitly determined during the construction. The discrete form \(B_{FE}\) is then extended to a continuous bilinear form by reversing the usual derivation of a discrete equation from a continuous one using piecewise linear shape functions. The energy equivalence condition \((*)\) remains true. The bilinear form \(B_{FE}\) and mesh \({\mathcal G}_{FE}\) give rise to a finite element system of linear equations that is the same size but with different density pattern than the original. Efficient solution methods for the finite element system are well-known, however. The authors prove that the finite element solution can be used as a quasi-optimal preconditioner for the original lattice system.