Babuška, I.; Sauter, S. A. Efficient solution of lattice equations by the recovery method. I: Scalar elliptic problems. (English) Zbl 1076.65097 Comput. Vis. Sci. 7, No. 3-4, 113-119 (2004). 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. Reviewer: Myron Sussman (Bethel Park) Cited in 1 Review MSC: 65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs 65N06 Finite difference methods for boundary value problems involving PDEs 35J25 Boundary value problems for second-order elliptic equations 65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs Keywords:preconditioning; lattice differential model; lattice equations; recovery method; finite element; heat conductivity model; Delaunay method; Voronoi method; piecewise linear shape functions Software:Triangle × Cite Format Result Cite Review PDF Full Text: DOI Link References: [1] Babuška, I., Guo, B.: Problems of unbounded lattices, mathematical framework. in preparation. · Zbl 1138.82004 [2] Babuška, I, Sauter, S.: Algebraic Algorithms for the Analysis of Mechanical Trusses. Technical Report 16-2002, Universität Zürich, http://www.math.unizh.ch/fileadmin/math/preprints/16-02.pdf, 2002. to appear in MathComp. · Zbl 1079.74045 [3] Bank, R.E., Xu, J.: A Hierarchical Basis Multi-Grid Method for Unstructured Grids. In: Hackbusch, W., Wittum, G. (eds.), Fast Solvers for Flow Problems, Proceedings of the Tenth GAMM-Seminar, Kiel: Verlag Vieweg 1995 · Zbl 0874.65091 [4] Chan, No article title, Contemp. Math., 218, 67 (1998) · doi:10.1090/conm/218/03002 [5] Chew, L.P.: Guaranteed-quality Delaunay meshing in 3D. In Proc. 13th Symp. Comp. Geom., pp. 391-393, ACM, 1997 [6] Constantinides, No article title, Basic Studies. Chem. Eng. Comm., 81, 55 (1980) · doi:10.1080/00986448908940530 [7] Fatt, No article title, Trans. Am. Inst. Mem. Metall Pet. Eng., 207, 144 (1956) [8] Feuchter, No article title, Comput. Visual. Sci., 6, 1 (1) · Zbl 1030.65126 · doi:10.1007/s00791-003-0102-3 [9] George, P.: Automatic Mesh Generation and Finite Element Computation, Vol. IV, chapter Finite Element Methods (Part 2), pp. 69-192. In: Ciarlet, P.G., Lions, J.L. (eds.), Handbook of Numerical Analysis, North-Holland 1996 [10] Gibson, L., Ashby, M.: Cellular Solids, Structures and Properties. Exeter: Pergamon Press 1989 · Zbl 0723.73004 [11] Glasser, No article title, J. Phys.,, 133, 5017 (2000) [12] Griebel, M., Knapek, S.: A multigrid-homogenization method. In: Hackbusch, W., Wittum, G. (eds.), Modeling and Computation in Environmental Sciences, pp. 187-202, Braunschweig: Vieweg 1997. Notes Numer. Fluid Mech. 59 · Zbl 0884.76063 [13] Hackbusch, No article title, Part I: Introduction to ℋ-Matrices. Computing, 62, 89 (1999) · Zbl 0927.65063 [14] Hackbusch, No article title, Part II: Applications to Multi-Dimensional Problems. Computing, 64, 21 (22) [15] Hackbusch, W., Khoromskij, B., Sauter, S.: On ℋ2-matrices. In: Bungartz, H.-J., Hoppe, R., Zenger, C. (eds.), Lectures on Applied Mathematics, pp. 9-30, Heidelberg: Springer-Verlag 2000 · Zbl 0963.65043 [16] Hackbusch, No article title, Part II: Implementation and Numerical Results. Comput. Visual. Sci., 1, 15 (1) [17] Hansen, No article title, Biophy. J., 70, 146 (1996) · doi:10.1016/S0006-3495(96)79556-5 [18] Joyce, No article title, Proc. Roy. Soc., London Ser. A, 445, 463 (1994) · Zbl 0808.33015 · doi:10.1098/rspa.1994.0072 [19] Kornhuber, No article title, Contemp. Math., 180, 49 (1994) · doi:10.1090/conm/180/01956 [20] Mandel, No article title, Computing, 62, 205 (1999) · Zbl 0942.65034 · doi:10.1007/s006070050022 [21] Martinson, P.G.: Fast Multiscale Methods for Lattice Equations. PhD thesis, University of Texas at Austin, 2002 [22] Ostoja-Starzewski, No article title, App. Mech. Review, 55, 35 (1) · doi:10.1115/1.1432990 [23] Ostoja-Starzewski, No article title, Comp. Math. Sci., 7, 89 (1996) [24] Pshenichnov, G.I.: Theory of Lattice Plates and Shells. Singapure: World Scientific 1993 · Zbl 0791.73002 [25] Ruge, J., Stüben, K.: Algebraic multigrid. In: McCormick, S. (ed.), Multigrid Methods, pp. 73-130, Philadelphia, Pennsylvania: SIAM 1987 [26] Shewchuk, J.: Triangle:Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In First Workshop on Appl. Geom., pp. 124-133 , Philadelphia, Pennsylvania, USA: Association for Computing Machinery 1996 [27] Shewchuk, J.: Tetrahedral Mesh Generation by Delaunay Refinement. In Proc. Of the 14th Annual Symp. On Comp. Geom., pp. 86-95, Minneapolis, USA: Association of Computing Machinery 1998 [28] Xu, No article title, Computing, 56, 215 (1996) · Zbl 0857.65129 · doi:10.1007/BF02238513 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.