Local Fourier analysis is a commonly used tool to assess the quality and aid in the construction of geometric multigrid methods for translationally invariant operators. In this paper we automate the process of local Fourier analysis and present a framework that can be applied to arbitrary, including non-orthogonal, repetitive structures. To this end we introduce the notion of crystal structures and a suitable definition of corresponding wave functions, which allow for a natural representation of almost all translationally invariant operators that are encountered in applications, e.g., discretizations of systems of PDEs, tight-binding Hamiltonians of crystalline structures, colored domain decomposition approaches and last but not least two- or multigrid hierarchies. Based on this definition we are able to automate the process of local Fourier analysis both with respect to spatial manipulations of operators as well as the Fourier analysis back-end. This automation most notably simplifies the user input by removing the necessity for compatible representations of the involved operators. Each individual operator and its corresponding structure can be provided in any representation chosen by the user.
Hinweise
Communicated by Daniel Kressner.
This work was partially funded by Deutsche Forschungsgemeinschaft (DFG) Transregional Collaborative Research Centre 55 (SFB/TRR55).
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Local Fourier analysis (LFA) is a powerful tool used in the construction and analysis of multigrid methods introduced in [4]. The fundamental idea of LFA is to leverage the connection between position space and frequency space via the Fourier transform. That is, in case the involved operators can be described by stencils in position space, meaning that they are translationally invariant, their Fourier transform yields so-called symbols, which can be handled much more easily.
In the context of multigrid methods LFA can be used to obtain precise approximations of the asymptotic convergence rate by assessing the spectral radius of the corresponding error propagation operator [23]. This approximation of the convergence rate is (asymptotically) still valid if the translational invariance is slightly violated, as for example when lexicographic Gauss–Seidel type smoothers are used, or in the case of certain non-periodic boundary conditions [5, 20, 27]. In other cases a similar convergence rate can usually be obtained by additional processing [12, 29]. Due to these facts, LFA is one of the main tools in the quantitative analysis of two- and multigrid methods.
Anzeige
An introduction to LFA including several examples can be found in [29, 30]. Multigrid methods have first been considered for the solution of the linear systems of equations originating in the discretization of (elliptic) partial differential equations (PDEs) [29]. Due to the fact that the simplest tiling of space is rectangular and discretizations are particularly simple to carry out on such tilings, the usual multigrid components and the LFA have originally been designed and tailored for such discretizations (cf. [29, 30]). Several other geometries, including systems of PDEs, have been considered in the past as well. LFA has been carried out for operators defined on triangular tilings in [7] and on hexagonal tilings in [32]. Further, it has been applied to edge-based quadrilateral discretizations [3], regular Voronoi meshes associated with acute triangular grids [21], edge-based discretizations on triangular grids [22] and jumping coefficients on rectangular grids [2, 18]. These papers do a complete two-grid analysis, and in some cases even a three-grid analysis, which was first introduced in [31].
While the concept of LFA is well understood, its application quickly becomes complex and involved the more frequencies get intermixed, e.g., by block smoothers, in a three-grid analysis, or in higher dimensional problems (\(n > 2\)). Thus, there exists software that automates the application of the LFA [19, 30]. In contrast to the software described in [30], which basically consists of a collection of templates corresponding to certain smoother and restriction/prolongation strategies for specific problems, the software [19], freely available on GitHub,1 can be used to analyze arbitrary translationally invariant operators on rectangular grids. This software has for example been used to analyze colored block Jacobi methods in combination with aggressive coarsening applied to PDEs with jumping coefficients in [2, 18]. As the number of frequencies which get intermixed increases with the block-size of the smoother and the growing coarsening rate, a manual analysis of this problem would be laborious.
In contrast to the approach developed in this paper, the bulk of the analysis in the previously mentioned references is mainly carried out in frequency space.
LFA with an emphasize on position space is rare in the literature.
Anzeige
In [11] under the name compact Fourier analysis, a position space oriented LFA is introduced where block Toeplitz matrices are used in order to capture the different classes of unknowns.
This work has some aspects in common with the approach to LFA we develop in this paper, but lacks generality as it is limited to simple systems on rectangular grids.
The LFA presented in this paper unifies the position space oriented approaches and allows the treatment of operators on arbitrary repetitive structures. To do so we introduce a mathematical framework for the analysis of translationally invariant operators which alter value distributions on lattices and crystals [1, 24]. These structures can be based on arbitrary sets of primitive vectors, including non-orthogonal ones, i.e., non-rectangular structures. These crystal structures, which naturally occur in the tight-binding descriptions of solid-state physics [1] or discretizations of systems of PDEs, enable the convenient and concise description of the resulting operators and allow for the automatic generation of their representations when enlarging their translational invariance, e.g., coarsening in the context of multigrid methods. Furthermore, they are very helpful in the representation of overlapping and non-overlapping block smoothers. Our framework is developed to such an extent that the only task required of the user is to provide a description of the occurring operators with respect to (potentially non-matching) descriptions of the underlying repetitive structures, i.e., each operator can be supplied in the simplest or most convenient representation. The remainder of the analysis can then be carried out automatically. In contrast to previously developed LFA, this is achieved by explicitly including a connection of the operator to its underlying structure. This allows us on one hand to automate the transformation of operators in position space, e.g., by finding a least common lattice of translational invariance of two operators and to rewrite their representations accordingly. On the other hand, this focus on structure yields a natural representation and discretization of the dual space that enables the automation of the frequency space part of the analysis as well. All these tasks can be carried out using basic principles and normal forms of integer linear algebra [24]. In combination these developments alleviate the use of LFA by removing any manual calculations. That is, neither a mixing analysis nor transformations of operators to common (and rectangular) translational invariances have to be carried out by hand. While our automated LFA does not necessarily enlarge the set of methods that are analyzable by conventional LFA, it enables the reliable and easy-to-use analysis of complex methods on complicated structures (e.g., overlapping block smoothers and discretizations of systems of PDEs). An open-source Python implementation of the automated LFA framework [13] is freely available on GitLab.2
The automation presented in this paper does have some limitation in terms of the smoothers that can be analyzed. Any sequential, i.e., lexicographic, smoother with overlapping update regions changes values in the overlap multiple times in one application. This cannot be easily translated to the structures introduced in this paper. While such smoothers have been analyzed in frequency space before (cf. [16, 17, 25]), this particular treatment of sequential overlap is momentarily not covered in our framework. Note, that the mere presence of overlap is not the problem here. By introducing a coloring, such that the complete sweep can be split into a sequence of updates where each one of them only changes values at most once, automated LFA can be applied as we are going to demonstrate in this paper. Due to the fact that a coloring in overlapping approaches also favors parallelism over their sequential counterparts, we feel that this limitation is relatively minor when targeting actual applications.
The paper is organized as follows. In Sect. 2 we introduce basic notation to describe the underlying structures of the operators we want to analyze: lattices and crystals. In the context of LFA we are interested in translationally invariant operators which alter value distributions on crystals. These kind of operators and their properties are specified in Sect. 3. After that, Sect. 4 illustrates the introduced notation by means of the discretized Laplacian and the red–black Gauss–Seidel method, which is the simplest method where a difference to the conventional LFA becomes apparent. In here, we manually rewrite the discretized Laplacian with respect to the translational invariance of the red–black splitting, such that the method can be analyzed via the results of Sect. 3. Sect. 5 contains the general theoretical results which are used to automate the complete procedure, removing the need to manually modify operators. In here, several results of integer linear algebra are used, which we review in Sect. 2.1. Using these results we obtain the algorithms given in “Appendix B” which, in combination with the arithmetic of multiplication operators given in “Appendix A”, realize the automated LFA. Finally, Sect. 6 contains selected examples to demonstrate the merits of the developed approach. First, we analyze a 4-color overlapping block Gauss–Seidel smoother for the tight-binding Hamiltonian of the carbon allotrope graphene and give some two-grid convergence results. Second, we reproduce the two-level analysis for the curl-curl problem found in [3] as a further illustration of how our approach is applied to complex error propagators and to double-check its results.
2 Lattices and crystals
In order to be able to automate the process of LFA within a unified framework we first have to review some basic definitions of integer linear algebra and crystallography [1, 24]. An (ideal) crystal is an infinite repetition, defined by a lattice, of a structure element.
Definition 2.1
Let be linearly independent. An n-dimensional lattice \(\mathbb {L}\) is the set of points
The vectors are known as the primitive vectors or lattice basis. Using matrix notation, i.e., , we can abbreviate the notation by
Without loss of generality we restrict the definition of the second component of a crystal, the structure element, to primitive cells of the lattice.
Definition 2.2
A primitive cell of a lattice is a (connected) volume of space that, if translated by all vectors of \(\mathbb {L}\), fills up \(\mathbb {R}^n\) completely without any overlap, i.e.,
i.e., parallelotopes spanned by the primitive vectors of .
The structure element of a crystal is now defined to consist of points \(\mathfrak {s}_{1},\ldots ,\mathfrak {s}_{m}\) that are contained in a particular primitive cell \(\varXi \).
Definition 2.3
Let be a lattice and , \(m \in \mathbb {N}\) be the structure element. A crystal is defined as the set of tuples
The elements of are collectively written as \(x+\mathfrak {s}=(x+\mathfrak {s}_1,x+\mathfrak {s}_2,\ldots ,x+\mathfrak {s}_m)\).
Remark 2.1
We define a crystal and the associated structure element to be a tuple instead of a set as we want to study value distributions on crystals and particular operators which manipulate them. For this purpose, the order of a structure element is of importance.
To give an idea of the various occurrences of crystal structures in numerical applications we illustrate typical examples in Fig. 1 together with their crystal representation. There are three main sources of repetitive structures that are well suited for crystal representations. First, the discretization of systems of PDEs on lattices lead to crystal structures, where the different species of unknowns typically constitute the structure element. Second, tight-binding Hamiltonian formulations in solid state physics for crystalline materials naturally imply a crystal representation based on the atomic structure. Last, colored domain decomposition approaches (e.g., red–black Gauss–Seidel) can be easily represented using crystals, where the smallest structure element typically consists of the union of one domain of each color.
Fig. 1
Illustration of the crystal representation of three repetitive structures of different origin each consisting of primitive vectors , a shaded primitive cell and a structure element \((\mathfrak {s}_1,\mathfrak {s}_2)\). a Staggered discretization of the curl-curl system of PDEs with unknowns on the edges of a rectangular lattice. b Hexagonal lattice of the carbon allotrope graphene. c Checkerboard coloring of a rectangular lattice as it is encountered in the red–black Gauss–Seidel smoother
×
2.1 Sublattices and quotient spaces
There are infinitely many representations of a crystal . On one hand, the representation of any lattice in \(n>1\) dimensions is non-unique, i.e., there exist different sets of primitive vectors that yield the same lattice structure. On the other hand, different representations of the crystal can be obtained by shifting the structure element or manipulating the underlying lattice structure, e.g., by using integer linear combinations of the primitive vectors and adjusting the structure element accordingly.
Fig. 2
The structure of graphene: Illustration of three choices of primitive vectors , and with associated structure elements \(\mathfrak {s}, \widehat{\mathfrak {s}}\) and \(\widetilde{\mathfrak {s}}\) such that . Furthermore, three different primitive cells are illustrated: The corresponding parallelotopes , as well as a hexagon corresponding to the Voronoi cell of
×
In order to cope with this lack of uniqueness of the representation of crystals, illustrated in Fig. 2, we introduce basic results from integer linear algebra [24], which resolve the relationship of lattice structures.3 An important tool in this is the notion of a sublattice.
Definition 2.4
Let and be two lattices, if then is called sublattice of .
Lemma 2.1
A lattice is a sublattice of if and only if .
A key-role in the computational comparison of lattices play the Hermite and Smith normal forms. The Hermite normal form defines a canonical choice of primitive vectors, whereas the Smith normal form allows us to find least common sublattices. Using these canonical forms is a crucial ingredient in both the theoretical analysis and the automation of the LFA.
Definition 2.5
A matrix \(U \in \mathbb {Z}^{n\times n}\) is called unimodular if \(\det (U)\in \{\pm 1\}\).
Definition 2.6
A matrix \(H\in \mathbb {R}^{n\times n}\) is in Hermite normal form (HNF) if it is upper triangular, elementwise non-negative and its row-wise maximum is located on the diagonal.
Definition 2.7
A matrix \(S\in \mathbb {R}^{n\times n}\) is in Smith normal form (SNF) if it is a diagonal matrix and the diagonal entries satisfy \( {s_{i+1}}/{s_{i}}\in \mathbb {Z}\) for all \(i=1,\ldots ,n-1\). These entries are called the elementary divisors.
Theorem 2.1
Let , then
(i)
there exists a unimodular \(U \in \mathbb {Z}^{n \times n}\) such that is in HNF,
(ii)
there exist unimodular \(U,V \in \mathbb {Z}^{n \times n}\) such that is in SNF.
In addition both normal forms H and S are unique with respect to .
Remark 2.2
Polynomial algorithms to compute the HNF and SNF can for example be found in [8]. Implementations for the computation of these normalforms are for example part of the PARI software package [28].
Using these definitions and results one obtains a precise statement about the equality of two lattices.
Theorem 2.2
Let and be two lattices then the following statements are equivalent.
(i)
.
(ii)
and .
(iii)
There exists a unimodular matrix \(U \in \mathbb {Z}^{n\times n}\), such that .
(iv)
and have the same HNF.
Instead of analyzing infinite lattice/crystal structures, we limit ourselves to analyze finite dimensional periodic structures due to the fact that we are ultimately aiming to analyze finite dimensional problems. To this end, another helpful tool is the definition of crystal tori which are defined as quotient groups.
Definition 2.8
Let be a crystal and be a sublattice. We define the crystal torus by
For every , their equivalence class \([x+\mathfrak {s}]\) is in . Furthermore, the elements of are defined by the equivalence
For theoretical and practical reasons, e.g., in Theorem 3.2 and Algorithm B.3, it is necessary to be able to list all elements of a torus , \(M \in \mathbb {\mathbb {Z}}^{n \times n}\), uniquely.
To illustrate this point, consider for example an arbitrary lattice with , and the lattice torus with
as depicted in Fig. 3. Even though we know that the quotient space consists of different elements, there is no apparent canonical list of these elements. Fortunately, a canonical ordering of the lattice points on a torus can be formulated using the Hermite or Smith normal form of M.
Theorem 2.3
Let be arbitrary, i.e., for some \(M \in \mathbb {\mathbb {Z}}^{n \times n}\).
Let \(H \in \mathbb {\mathbb {Z}}^{n \times n}\) be the HNF of M with entries \(H_{ij}\) (cf. Definition 2.6). Defining the index set \(I=I_1 \times I_2 \times \ldots \times I_n\) by \(I_\ell :=\{0,1,\ldots ,H_{\ell \ell }-1\}\), we then obtain
Let \(S=U^{-1}MV \in \mathbb {Z}^{n\times n}\) denote the Smith decomposition of M with diagonal entries \(s_{i}\) (cf.Definition 2.7) and unimodular matrices U, V. Defining the index set \(\tilde{I}=\tilde{I}_1 \times \tilde{I}_2 \times \ldots \times \tilde{I}_n\) by \(\tilde{I}_\ell :=\{0,1,\ldots ,s_{\ell }-1\}\), we then obtain
Both statements are a direct consequence of the triangular or diagonal shape of the normal forms and Theorem 2.2, i.e., lattices are not changed by unimodular column transformations. On the one hand we have . The second statement follows from and hence . \(\square \)
Thus, a unique list of all representatives of is given by
The Smith decomposition of M is given by
Thus, another unique list of all representatives of is given by
where .
All tori representations , and are depicted in Fig. 3. In the remainder we drop the bracket notation for reasons of readability.
Fig. 3
The Hermite normal form H and the Smith normal form S of M yield lattice bases which allow us to define a canonical lexicographic ordering of the lattice points of a crystal torus
×
3 Operators on crystals
Now that the basic notation of the underlying structure is in place we introduce notation for value distributions and operators on these structures. For aforementioned reasons, we restrict ourselves to the finite dimensional setting by only considering quotient groups of lattices
with being an arbitrary sublattice of . While it is significantly easier to be mathematically precise in this general finite setting than in an infinite setting it is also much closer to the targeted applications, namely finite dimensional approximations of PDEs and Hamiltonians. Eventually we only work with operators as part of numerical simulations, i.e., we face only a finite number of unknowns/lattice points anyway. The quotient group , , precisely describes such an arbitrarily large but finite torus. To shorten notation we use instead of whenever we do not specify explicitly.
Definition 3.1
A crystal-operator is a linear function
where corresponds to the crystal of the domain and corresponds to the crystal of the codomain. The function spaces are defined by
A value \(f_j(x)\), , corresponds to a value at the position \(x + \mathfrak {s}_j\). The function space is equipped with the scalar product
where \(\langle f(x),g(x)\rangle _{2} := \sum _{\ell =1}^{|\mathfrak {s}|} f_\ell (x) \overline{g_\ell (x)}\) denotes the Euclidean scalar product on \(\mathbb {C}^{|\mathfrak {s}|}\).
In the context of LFA we are interested in operators which can be represented in (block) stencil notation. That is, translationally invariant operators that can be written as multiplication operators. As these two properties are in fact equivalent (cf. [26, Theorem 3.16]), we can connect those operators to the notation of crystal structures.
Theorem 3.1
Let be a crystal operator. The following statements are equivalent.
1.
L is a multiplication operator, i.e., there exist matrices \(m_L^{(y)} \in \mathbb {C}^{|{\mathfrak {c}}|\times |{\mathfrak {d}}|}\) such that for each and we have
2.
L is -translationally invariant, i.e.,
where the translation operator is defined by .
For the analysis of such operators the concept of the dual lattice comes in handy as already considered in similar form in [7, 32].
Definition 3.2
Let be a lattice. Its dual lattice is the set
A lattice basis of the dual lattice is given by . The elements of may also be referred to as wave vectors.
In addition to the dual space we introduce an orthonormal basis of wave functions that are compatible with the crystal structure introduced in Sect. 2. This basis is an extension of the basis used in [15] to analyze the red–black Gauss–Seidel relaxation. Furthermore, similar basis functions have been used in the context of LFA, e.g. in [2, 3, 6, 9, 14].
Theorem 3.2
An orthonormal basis for the function space with a structure element \(\mathfrak {s}=(\mathfrak {s}_1,\ldots ,\mathfrak {s}_m)\) is given by the wave functions \(e_{1,k},e_{2,k},\ldots ,e_{m,k}\) defined by
The statement follows by a straightforward, but lengthy calculation, by assuming without loss of generality that is given in Smith normal form, making use of Theorem 2.3 and the geometric sum formula. \(\square \)
An illustration of a lattice torus along with its dual is given in Fig. 4.
Fig. 4
A lattice torus (left) and its dual torus (right). In here, the lattices bases are denoted by and
×
The orthonormal basis of Theorem 3.2 can be split into subsets with respect to the wave vector k, i.e., with
Let be a multiplication operator. Then the subspaces \(H_k\) of Eq. (3.1) are L-invariant, i.e., \(L(H_k) \subseteq H_k\).
Proof
Let \(e_{k}(x)\) denote an arbitrary value distribution in \(H_{k}\). That is, there exist \(\alpha _{1},\ldots ,\alpha _{m} \in \mathbb {C}\) such that
Due to their L-invariance the subspaces \(H_k\) are oftentimes referred to as spaces of harmonics. Thus we can easily represent any -translationally operator via its symbols, which are formally defined as follows.
Definition 3.3
Let be a multiplication operator with
We define the symbol of L according to Eq. (3.2) by
In case \(\mathfrak {s}= \mathfrak {t}\) the spectrum of L can then be extracted from its symbols \(L_{k}\).
Theorem 3.4
Let be a multiplication operator with
Then .
Proof
Follows immediately due to the orthonormality of the basis \(e_{\ell ,k}\) (cf. Theorem 3.2) and the L-invariance of the subspaces \(H_{k}\) (cf. Theorem 3.3). \(\square \)
Remark 3.1
The main purpose of , i.e., the set of primitive vectors that define an arbitrary sublattice of , is to simplify the theory developed in Sect. 3 by turning an infinite dimensional setting to an (arbitrarily large) finite one. Though there is another interpretation to it as well. In Theorem 3.4 explicitly specifies the resolution of the frequency space as seen in Fig. 4, i.e.,
where the spectrum of the multiplication operator is sampled. Due to the reciprocal nature of the dual space, the larger is, the finer the resolution becomes.
With these tools at hand we are able to fully analyze a single multiplication operator, but typically we are interested in analyzing a composition of several operators using LFA. As long as the corresponding domains and codomains of these operators are compatible we can use the rules of computation given in “Appendix A” on the level of multiplication operators and/or on the level of the corresponding symbols. While computing the sum, a product and taking the transpose can easily be done on both levels, taking the (pseudo-)inverse is simple only on the level of symbols. The (pseudo-)inverse of a multiplication operator may have an arbitrarily large number4 of multipliers \(m_{L^{-1}}^{(y)} \ne 0\) and thus there is no simple rule to compute it. In case a pseudo-inverse has to be used in the following we opt to employ the Moore-Penrose pseudo-inverse, which we denote by \(S^{\dagger }\) for a multiplication operator S.
In our framework, which tries to automate as much of the LFA as possible, we would like to allow for user friendly descriptions of all occurring operators. That is, it should be possible to describe operators in terms of their individual translational invariance and ordering of the structure element without having to worry about compatibility issues with other operators on the input level of the analysis. The process how to automatically make crystal representations of operators compatible is explained in detail in Sect. 5. Before diving into the gritty details of this automation process we would like to illustrate the developments made so far with an example in order to convey the introduced notation.
4 An example
Consider the red–black Gauss–Seidel method applied to the discretized Laplacian on the unit square with periodic boundary conditions. The most fundamental representation of the discretized unit square with periodic boundary conditions is given by the torus with
Then, the discretized Laplacian using finite differences is given by with non-zero multipliers:
×
The error propagator G of the red–black Gauss–Seidel method can be written with respect to the crystal via
where \(X_{\mathrm{red}}\) and \(X_{\mathrm{black}}\) correspond to the red and black unknowns of the torus as illustrated in Fig. 5b. In order to analyze this composite operator in our framework, we write all occurring operators as multiplication operators. It is now important that the red–black splitting of implies the crystal with
such that , and (cf. Fig. 5b). With respect to this crystal the operators \(S_r\) and \(S_b\) can be written as multiplication operators with
We now have described all individual operators of G, each one defined with respect to its own (minimal) translational invariance, but the domains and codomains are not identical, i.e., , such that we cannot directly use the computation rules described in “Appendix A”. In order to carry on with the analysis we have to rewrite the operators with respect to a common crystal structure. In this example we construct this structure by hand, but this process can be automated as explained in Sect. 5.
As the crystal is yet another representation of , the operator \(L_h\) can be rewritten with respect to this crystal (cf. Fig. 5) as with and non-zero multipliers:
Fig. 5
The discretized Laplace operator with respect to two different crystal representations. In a) the operator is illustrated with respect to the primitive vectors and in b) with respect to
×
×
Thus, the spectrum of the error propagator of the red–black Gauss–Seidel method applied to the Laplacian
can now be obtained elementwise for each fixed by first computing the individual symbols\(I_k, (\hat{S}_r)_k, (\hat{S}_b)_k\) and \((\hat{L}_h)_k\) and assembling the symbols \(\hat{G}_k\) according to Eq. (4.1) and the rules in “Appendix A”, followed by the computation of the eigenvalues of the matrices \(\hat{G}_k\). The resulting spectral information of the discretized Laplace operator \(\hat{L}_h\) and the error propagator \(\hat{G}\) is illustrated in Fig. 6, where it is sampled on the dual lattice . Note, that one naturally obtains two eigenvalues per sampled wave vector k. In case of the spectrum of the red–black Gauss–Seidel error propagator, one of the two eigenvalues is equal to zero for all wave vectors k.
Fig. 6
The spectra of a the discretized Laplace operator and b the red–black Gauss–Seidel smoother with respect to the red–black crystal structure. In here, and denote the columns of
×
5 Crystal representations and natural isomorphisms
In general, we are given several multiplication operators which make up the error propagator of an iterative method, each defined with respect to its own (minimal) translational invariance. In order to analyze the method we thus need to find a common denominator, i.e., a lattice basis corresponding to the collective translational invariance, and rewrite the operators accordingly. The following Theorem yields a set of primitive vectors of such a collective translational invariance for two arbitrary lattices, if it exists.
Theorem 5.1
Given two n-dimensional lattices , . If there exists an \(r\in \mathbb {Z}\), such that , then there is a lattice with and with as small as possible. A lattice basis of is given by
where is a diagonal matrix with , where \(S= V^{-1} M T^{-1} = {\text {diag}}{(s_{1},\ldots ,s_{n})}\) is the SNF of M (cf. Definition 2.7) and \({\text {gcd}}(r,s_{i})\) denotes the greatest common divisor of r and \(s_i\). Consequently, we write and call it the least common multiple of and .
Proof
Due to Lemma 2.1 it is sufficient to find integral matrices , such that
with and as small as possible. Using Theorem 2.2, i.e., , for any unimodular matrices \(U_1,V_1\), we can assume the equality
for any unimodular U and in Hermite normal form (cf. Theorem 2.1). Plugging in the Smith decomposition VST of and defining \(U:=T^{-1}\), we find
Both matrices
have to be integral with
as small as possible. It can easily be verified that
is the optimal choice for the diagonal entries. With this choice, the off-diagonal entries have to be integral multiples of . Due to the fact that is in Hermite normal form, the off-diagonal entries are zero. \(\square \)
We now study different representations of the same crystal structure in order to derive a general way to rewrite a multiplication operator with respect to some coarser crystal structure corresponding to a sublattice, as has been done manually in Sect. 4 for the discretized Laplacian.
Theorem 5.2
(Rewriting a crystal with respect to a sublattice) Let be a crystal and a sublattice. Denoting ,5 the set
defines a primitive cell of , and the tuple
defines a structure element of such that , meant as a one-to-p correspondence.
Proof
Without loss of generality we may assume , \(j = 1,\ldots ,p\). Then, each element in can be written as
and there is a unique y, such that with and . Thus, we find z as a unique part of the element
This argument works in the other direction in the same way. \(\square \)
Remark 5.1
Note, that \(\mathfrak {u}\), as defined in Theorem 5.2, is an explicit representation of , thus using this explicit representation Theorem 5.2 implies a congruence of the function spaces
given by the natural isomorphism ,
as (f) and \((\eta f)\) describe the same value distribution on the crystal. This congruence in turn implies that the coarsest possible crystal interpretation, i.e., , is simply the complex coordinate space
with . The scalar product on then corresponds to the Euclidean scalar product on \(\mathbb {C}^{mn}\) up to a factor of n.
Using the natural isomorphism of function spaces in Remark 5.1, we can derive the transformations of multiplication operators when coarsening the underlying crystal representation corresponding to a sublattice.
Theorem 5.3
(Rewriting a multiplication operator with respect to a sublattice) Consider crystals , , a sublattice and a multiplication operator
Then, using , the multiplication operator
with block matrices \((m_G^{(y)})_{i,k} := m_L^{(y-\mathfrak {t}_i+\mathfrak {t}_k)} \in \mathbb {C}^{|\mathfrak {c}|\times |\mathfrak {d}|}\) fulfills the commutative diagram:
Here, the mappings for \(\mathfrak {s}\in \{\mathfrak {d},\mathfrak {c}\}\),
denote the natural isomorphisms between the congruent crystal representations.
×
Proof
A straightforward calculation for each block-row i yields
\(\square \)
Using Theorem 5.3 we now know how to rewrite multiple multiplication operators with respect to some common crystal structure with a coarser translational invariance. Due to the fact that we do not make any assumption on the initial representation of the crystal structures, the resulting structure elements of Theorem 2.3 might differ in their orderings and might contain shifts with respect to the common shift invariance. To automatically remove these differences and determine the corresponding transformations of the associated multiplication operators we first define the notion of congruent structure elements.
Definition 5.1
Two crystal tori , are congruent with respect to if the structure elements are of the same size, i.e., \(|\mathfrak {s}| = |\mathfrak {t}| = m\), and there is a permutation \(\pi :\{1,\ldots ,m\} \rightarrow \{1,\ldots ,m\}\) as well as shifts , such that
In order to introduce a unique representation for the sake of automation, we introduce the following normal form and the required transformations to transfer any operator to this form.
Definition 5.2
Let be a multiplication operator. We say L is in normal form if
the coordinates of the structure elements are found in the primitive cell spanned by the primitive vectors, i.e., ,
the structure elements \(\mathfrak {d}\) and \(\mathfrak {c}\) are sorted lexicographically.6
We now derive the implications of Definition 5.1 for multiplication operators when the structure element is element wise shifted or permuted. We do so in two steps, Theorems 5.4 and 5.5. First, we show that a shift of an entry of the structure element in the codomain or domain results in a modification of the corresponding row or column of the non-zero multipliers, respectively.
Theorem 5.4
(Shifted structure elements) Consider the two multiplication operators and defined by
Further let \(\hat{\mathfrak {t}}\) be a structure element which is obtained from \(\mathfrak {t}\) when shifted element-wise along , i.e.,
where and \(m=|\mathfrak {t}|\). Then, the operators \(\hat{L}\) and \(\hat{G}\) given by
fulfill the commutative diagram:
×
Proof
The natural isomorphism between the two corresponding function spaces is given by
as f and \((\mathbb {T}f)\) describe the same value distribution on the crystal.7 Again, a straightforward calculation yields
Analogously we find . \(\square \)
Finally, we show that permutations of the entries of the structure element result in a transformation of the non-zero multipliers by corresponding permutation matrices.
Theorem 5.5
(Permuted structure elements) Consider the two multiplication operators and defined by
Let further \(\hat{\mathfrak {t}}\) be a structure element which is a permuted version of \(\mathfrak {t}\), i.e.,
where \(m=|\mathfrak {t}|\), \(\pi :\{1,\ldots ,m\} \rightarrow \{1,\ldots ,m\}\) is a permutation and \(m_\pi \in \{0,1\}^{m\times m}\) the corresponding permutation matrix. Then, the operators \(\hat{L}\) and \(\hat{G}\) given by
fulfill the commutative diagram:
×
Proof
Due to the fact that the natural isomorphism is a multiplication operator defined by \((p f)(x) = m_\pi f(x)\) for all , the statement is true due to the rules of computation in Lemma A.1. \(\square \)
Theorems 2.3 and 5.1 to 5.5 allow for the automatic adjustment of crystal representations within the LFA. The corresponding detailed algorithms which make use of these results are given in “Appendix B”.
6 Application
Before demonstrating the application of aLFA to some selected examples let us briefly recapitulate the individual parts of the framework. The introduction of crystal structures in Sect. 2 allow for a canonical description of translationally invariant operators introduced in Sect. 3. Combined with the definition of the dual of a crystal structure in Definition 3.2 and a corresponding orthonormal basis in Theorem 3.2, the symbol of any single multiplication operator that is translationally invariant with respect to an arbitrary lattice structure, can be expressed (cf. Definition 3.3). This combination of choice of basis functions and the explicit connection of operators to their underlying structure enables an automated mixing analysis. This part of the framework can thus be seen on one hand as a unification of positional approaches to LFA by introducing structures that allow for the native treatment of arbitrary translational invariances and on the other hand as a general strategy for the automation of the frequency part back-end of LFA. In order to deal with compositions of operators as encountered in the analysis of iterative methods, the tools provided in Sect. 5 allow for an automatic transformation of the underlying crystal structures into compatible representations and the corresponding transformations of the operators. Thus, the only task remaining for the user is to provide any, i.e., the simplest or most convenient, crystal representation of the operators. The following examples show how such a construction can be carried out and as such serve as a tutorial for the use of the algorithms in “Appendix B”. Annotated Jupyter Notebooks of the presented examples can be found in [13].
6.1 Multicolored block smoother for the tight-binding Hamiltonian of graphene
In [12] a multigrid method for the tight-binding Hamiltonian of the carbon allotrope graphene based on Kaczmarz smoothing is constructed and analyzed using conventional LFA. Due to the hexagonal structure of graphene, the lexicographic ordering of Kaczmarz and the mixing analysis of the coarse grid correction which involved a mixing of eight frequencies, the analysis turned out to be quite lengthy. In this subsection we now want to analyze a two-grid method for this problem where we replace Kaczmarz by an overlapping colored Gauss–Seidel method that allows for better parallelism in the application of the multigrid method. Thus, the goal of this example is two-fold, first we want to show that the tight-binding Hamiltonian can be easily expressed using the native crystal structure of graphene and second that even the analysis of an overlapping block smoother can be carried out with ease using aLFA due to the fact that only a representation of the involved operators is needed.
The graphene structure can be described as a crystal where the underlying lattice is triangular, i.e., any three nearby lattice points form an equilateral triangle. We have
with the structure element
The parameter \(a= 1.42\AA {}\) which denotes the distance of two neighboring atoms can be omitted as it does not occur in the tight-binding formulation. An illustration of the crystal has already been given in Fig. 2.
The (nearest neighbor) tight-binding Hamiltonian is a multiplication operator
a Schematic stencil of the tight binding Hamiltonian \(L_{[t_0,t_1]}\) of graphene. b Illustration of the domain decomposition into hexagons. Each unknown belongs to 3 different colors
×
×
Overlapping Hexagons We now present an overlapping block smoother for the tight-binding Hamiltonian L. Consider the non-disjoint splitting (or coloring) of the crystal into hexagons as depicted in Fig. 7b. This splitting has a translational invariance of . Rewriting the graphene crystal with respect to this coarser lattice , we find with the structure element
The splitting is then given by the structure elements
such that , , and . In the case of the nearest neighbor Hamiltonian any two hexagons of the same color do not interact. Thus, a relaxed sweep on the unknowns of one color is cheap and, in addition, yields a good degree of parallelism.
There are two options to describe the multiplication operators of the multicolored block smoother. On the one hand, we can construct them from scratch by defining the multiplication operator structure as well as the non-zero multipliers. On the other hand, we can derive the structure and non-zero multipliers of the operators corresponding to the colored blocking from the tight-binding Hamiltonian L by exploiting the fact that a colored block corresponds to the operator L restricted to this block. In order to proceed with the latter approach, we first need to find the description \(\hat{L}\) of the underlying operator, the tight-binding Hamiltonian L, with respect to the translational invariance of the splitting . After that the structure element needs to be adjusted such that all unknowns and their couplings among each other are found within the central multiplier \(m_{\hat{L}}^{(0)}\). Consider the structure element \(\mathfrak {t}\). As can be seen in Fig. 7b, the coupling among the unknowns \(\mathfrak {t}^{(\ell )}\) which we want to update simultaneously are found in the multipliers:
\(\mathfrak {t}^{(1)}\)
\(\mathfrak {t}^{(2)}\)
\(\mathfrak {t}^{(3)}\)
\(\mathfrak {t}^{(4)}\)
\(m_{\hat{L}}^{(0)}\)
Thus, in order to obtain suitable descriptions for \(\mathfrak {t}^{(\ell )}\), \(\ell \in \{2,3,4\}\), we need to consider shifted versions \(\mathfrak {t}+ \tau ^{(\ell )}\). For example
(6.1)
Finally, the error propagator corresponding to a single color relaxed block Gauss–Seidel update can be written as
with \((S^{(\ell )}f)(x) := (m_P m_{\hat{L}}^{(0)} m_P)f(x)\) where \(m_P\) is the diagonal matrix
We summarize the algorithmical steps to obtain the error propagators.
The error propagator of a successive update of the four colors corresponds to the product of the error propagators \(G^{(\ell )} = ( I - \omega (S^{(\ell )})^\dagger \hat{L}^{(\ell )})\).
×
Now that all operators of the overlapping colored block Gauss–Seidel smoother are defined, we can compute its spectrum. The computation of the eigenvalues of the error propagator is carried out with Algorithm B.1 via
The function g denotes the composition of the error propagators
Note, that in this algorithm all operators are checked for compatibility and any incompatibility with respect to domains and codomains is dealt with using the transformations introduced in Sect. 5.
For \(\omega =\frac{1}{2}\) we obtain the plot in Fig. 8a. As the largest spectral radius is greater than one, this method cannot be used as a standalone solver.
Fig. 8
a Plot of the spectral radii of the four-color hexagonal overlap block smoother \(\prod _{\ell =1}^4 G_{\omega }^{(\ell )}\) with under-relaxation of \(\omega = \frac{1}{2}\) for the tight-binding Hamiltonian \(L=L_{[0,-1]}\) plotted along . b Plot of the spectral radii of the two-grid method using the overlap smoother
×
Coarse grid correction In [12] a Galerkin coarse grid correction is used with a corresponding coarse grid correction operator that is defined by
$$\begin{aligned} E = (I- P(L_c)^\dagger R L) \end{aligned}$$
with \(L_c = RLP\) and \(P=R^T\). Just as in the description of the smoother, the shift invariance of the coarse grid is . Defining the coarse structure element by \(2\mathfrak {s}\), and with \(\mathfrak {t}\) denoting the structure element of the fine crystal according to the coarse lattice basis, the restriction operator can be described as
The multipliers of the restriction operator according to [12] then read
×
This coarse grid correction is constructed in a way, such that it preserves the kernel of the tight-binding Hamiltonian L, where with ,
The frequencies corresponding to the kernel modes are known as the Dirac points.
The two-grid analysis can now be carried out using Algorithm B.1 via
The function f denotes the composition of the two-grid error propagator
A plot of the spectral radii of the two-grid error propagator is given in b) of Fig. 8 which shows that the two-grid method converges with a convergence rate of \(\rho _{\max } \approx 0.167\). Thus, this new method with overlapping colored block Gauss–Seidel smoothing not only yields opportunities for parallel computations, but also converges faster than the old approach which used Kaczmarz smoothing.
In order to double-check the results of the developed theory, we show in table 1 that the asymptotic convergence rate of the two-grid method with random initial guess \(x_0\) and right-hand-side 0 coincides with the convergence rate obtained in the LFA with a relative accuracy of roughly \(.002\%\). This comes as no surprise as the theory is exact for this problem with periodic boundary conditions and we have chosen the sampling of the frequency space in accordance with the problem size (cf. Remark 3.1).
Table 1
Convergence history of the two-grid method applied to the tight-binding Hamiltonian of graphene with \((41\times 41)\cdot 2^3\) unknowns/atoms and periodic boundary conditions
The reported asymptotic convergence rate \(\rho _i\) coincides with high precision to the convergence estimate obtained in aLFA
6.2 Two-level analysis for the curl-curl equation
In [3] a complete two-level analysis is carried out for the 2-dimensional curl-curl formulation of Maxwell’s equations using conventional LFA. In this subsection we want to reproduce the results of the two-grid method discussed in this paper making use of the native crystal structure of the staggered discretization of the curl-curl equations. The method consists of a so-called half-hybrid smoother, introduced in [10], and a Galerkin coarse grid correction.
The degrees of freedom of the discrete curl-curl equation
$$\begin{aligned} \left( \frac{1}{h^2}K_{cc} + \sigma M\right) x= b \end{aligned}$$
(6.3)
are associated with the edges of a quadrilateral lattice with
By multiplying Eq. (6.3) with \(h^2\), the grid size can be incorporated into the material parameter \(\sigma _h := h^2\sigma \). Then the discrete operator \(K=K_{cc} + \sigma _h M\) can be expressed as a multiplication operator by
where the elements and correspond to the (midpoints of the) horizontal and the vertical edge, respectively (cf. Fig. 9). According to [3] the multipliers are given by:
Fig. 9
a Crystal structure of the curl-curl discretization. b Illustration of the coarse crystal and the restriction operator; dashed lines correspond to restriction weight \(\frac{1}{4}\), solid lines to \(\frac{1}{2}\)
×
×
Hybrid smoother The (half) hybrid smoother uses an auxiliary space correction. That is, it can be seen as a two-grid method itself where smoothing replaces the exact inversion of the auxiliary space operator. The construction of this operator is as follows.
As already stated, we want to reproduce the results in [3]. Due to the fact that lexicographic Gauss–Seidel smoothers are used, we introduce the exact same ordering of the lattice points used in this paper, that is, the coordinates are ordered from bottom to top and left to right which leads us to the following definition for :
The error propagator of the smoother on the original crystal is a node-based lexicographic Gauss–Seidel iteration. When updating a horizontal edge \(x + \mathfrak {e}_h\), it is assumed that all edges \(y+\mathfrak {e}_h\) and \(y+\hat{\mathfrak {e}}_v\), , with \(y<x\) are already updated. When updating the edge \(y+\hat{\mathfrak {e}}_v\), it is additionally assumed that \(x+\mathfrak {e}_h\) is already updated (cf. [3, Figure 6.1]). In order to obtain the error propagator which exactly represents this ordering, it is convenient to rewrite the operator K with respect to this representation of the structure element, that is
which can be obtained with Algorithm B.6 via
The corresponding error propagator is then given by
In here, only the lower triangular part \(\texttt {tril}(m_{\hat{K}}^{(0)})\) of the central multiplier is used due to the fact that it represents a Gauss–Seidel sweep where a horizontal edge is updated before a vertical edge.
The crystal, where the auxiliary space system is formulated, is given by , i.e., the nodal points between the edges. The transfer operator to this crystal is the discrete gradient operator defined by with non-zero multipliers
Using a Galerkin construction, i.e., \(P_N = R_N^T\), the coarse grid operator \(K_N = R_N K P_N\) can be obtained using the computation rules in Lemma A.1. Inversion of this auxiliary space operator is then approximated by Gauss–Seidel. Thus, the auxiliary space correction with a single smoothing step on the auxiliary space is given by
With this definition of the auxiliary space correction, the half-hybrid smoother consists of the following steps.
1.
Smooth on \(Kx=b\): \(x \leftarrow (I+S_E^\dagger K)x + S_E^\dagger b\),
2.
Restrict the residual: \(r_N \leftarrow R_N(b-Kx)\),
3.
Smooth on \(K_N x_N= r_N\) with zero initial guess: \(x_N \leftarrow S_N^\dagger r_N\),
4.
Prolongate to the primal crystal \(x \leftarrow x + P_N x_N\).
The smoother is analyzed analogously to Sect. 6.1 with Algorithm B.1 by computing the spectral radii via
where g denotes the composition of the error propagators
In Fig. 10 a) a contour plot of \(\rho (G_k)\) with \(\sigma _h = 0.01\), with respect to is given. It corresponds to the result given in [3, Figure 6.2, right].
Coarse grid correction In [3] a Galerkin coarse grid correction is used corresponding to the error propagator
$$\begin{aligned} E = (I- P(K_c)^\dagger R K) \end{aligned}$$
with \(K_c = RKP\) and \(P=R^T\). In here, the coarse crystal is and the original crystal with respect to the lattice \(2\mathcal {A}\) is given by with
Then, according to [3] the restriction operator is given as with the multipliers:
×
Here, each coarse horizontal and vertical edge is connected to its six nearest edges of the same type (cf. Fig. 9b)). The prolongation and coarse grid operator P and \(K_c\) can be obtained via Lemma A.1.
The spectral radii of the two-grid method can then be obtained via
where f denotes the composition of the two-grid error propagator
Figure 10b shows the spectral radii, \(\sup _k \rho (M_k)\), of the two-grid error propagator as a function of \(\sigma _h\). We used exactly the same orderings in pre- and post-smoothing, as described in [3]. Furthermore, we double-checked the results with convergence tests similar to Table 1. However, the obtained results show major differences to the one in [3, Figure 8.1, left], which leads us to believe that our assumptions on the lexicographic orderings employed in pre- or post-smoothing in [3] are wrong, as these have a large impact on the convergence rates.
Fig. 10
a Contour plot of \(\rho (G_k)\) for the hybrid smoother with respect to , \(\sigma _h = 0.01\). b Contour plot of the convergence estimates of the two-grid method \(\sup _k \rho (M_k)\) with respect to \(\sigma _h\). The plots correspond to the results [3, Figure 6.2, right] and [3, Figure 8.1, left], respectively
×
7 Conclusion
In this paper we present an LFA framework that is applicable to arbitrary crystal structures, which are encountered in many applications, e.g., systems of partial differential equations, block smoothers or tight-binding formulations. This was achieved by introducing a rigorous notion of crystal structures and translationally invariant operators that manipulate value distributions on crystal structures. Based on these structures we introduced a complete framework to modify and transform these operators with respect to different crystal representations by using normal forms of integer linear algebra. This allowed us to automate the LFA in both position space, i.e., in terms of multiplication operators/stencils, and frequency space, i.e., in terms of canonical basis functions and samplings. In two examples we showed that the approach can be used for complicated operators, i.e., hexagonal grids, overlapping block smoothers and hybrid smoothers, without requiring insight into the frequency space back-end of LFA. An explicit mixing calculation is no longer needed, and the user only has to provide any representation of the individual operators. The transformation of the individual operators to a compatible representation and the subsequent frequency analysis is then carried out automatically. Even though we have limited ourselves in the examples in this paper to 2-dimensional problems our automated LFA can be applied to operators in higher dimension, where the difference is a larger set of primitive vectors defining the underlying lattice.
The automation presented in this paper does have some limitation. Each individual operator in the analysis is only allowed to change each value of the value distribution at most once. This limitation solely restricts the class of smoothers that can be analyzed with this approach. Any sequential, i.e., lexicographic, smoother with overlapping update regions changes values in the overlap multiple times in one application. This cannot be easily translated to a corresponding local multiplication operator, but it can be dealt with in frequency space (cf. [16, 17, 25]). This particular treatment of sequential overlap is momentarily not covered in our framework. Note, that the mere presence of overlap is not the problem here. By introducing a coloring, such that the complete sweep can be split into a sequence of updates where each one of them only changes values at most once, automated LFA can be applied (cf. Sect. 6.1). Due to the fact that a coloring in overlapping approaches also favors parallelism over their sequential counterparts, we feel that this limitation is relatively minor when targeting actual applications. An open-source implementation of the automated LFA framework [13] is freely available on GitLab.8 Jupyter Notebooks for all examples from Sects. 4 and 6.1 and 6.2 are included in this software package as well.
Acknowledgements
Open Access funding provided by Projekt DEAL.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Calculus of multiplication operators plays a key-role in local Fourier analysis. In this section we list all elementary operations, such as addition and multiplication. Proofs for these rules can be obtained by straightforward calculation.
Lemma A.1
Let two multiplication operators be given by
Then the following operators are multiplication operators as well:
(i)
If \(\mathfrak {s}= \mathfrak {u}\) and \(\mathfrak {t}=\mathfrak {v}\), then .
(ii)
If \(\mathfrak {v}= \mathfrak {s}\), then .
(iii)
The adjoint is given by .
Theorem A.1
Let two multiplication operators be given by
with corresponding symbols \(L_k\) and \(G_k\).
Then we have the following statements.
(i)
Assuming that \({\mathfrak {s}} = {\mathfrak {u}}\) and \({\mathfrak {t}} = {\mathfrak {v}}\), the symbols of \(L+G\) are given by \(L_k+ G_k\).
(ii)
Assuming that \({\mathfrak {v}} = {\mathfrak {s}}\), the symbols of \(L\cdot G\) are given by \(L_k\cdot G_k\).
(iii)
The symbols of \(L^*\) are given by \(L_k^*\).
(iv)
The symbols \((L^\dagger )_k\) are given by \((L_k)^\dagger \).
In case \(\mathfrak {d}_i=\mathfrak {d}_j\) or \(\mathfrak {c}_i = \mathfrak {c}_j\) for any \(i\ne j\) a consistent ordering of i, j has to be defined a priori.
The left-hand side of \([(\mathbb {T}f)(x)]_i=f_i(x-y_i)\) corresponds to the value at position \(x + {\hat{\mathfrak {t}}}_i = (x-y_i)+\mathfrak {t}_i\) which coincides with the position of the value of the right-hand side.
be linearly independent. An n-dimensional lattice \(\mathbb {L}\) is the set of points
The vectors
are known as the primitive vectors or lattice basis. Using matrix notation, i.e.,
, we can abbreviate the notation by
of a lattice
is a (connected) volume of space that, if translated by all vectors of \(\mathbb {L}\), fills up \(\mathbb {R}^n\) completely without any overlap, i.e.,A common choice of primitive cells is given by
i.e., parallelotopes spanned by the primitive vectors of
.
be a lattice and
, \(m \in \mathbb {N}\) be the structure element. A crystal is defined as the set of tuples
The elements of
are collectively written as \(x+\mathfrak {s}=(x+\mathfrak {s}_1,x+\mathfrak {s}_2,\ldots ,x+\mathfrak {s}_m)\).
, a shaded primitive cell
and a structure element \((\mathfrak {s}_1,\mathfrak {s}_2)\). a Staggered discretization of the curl-curl system of PDEs with unknowns on the edges of a rectangular lattice. b Hexagonal lattice of the carbon allotrope graphene. c Checkerboard coloring of a rectangular lattice as it is encountered in the red–black Gauss–Seidel smoother
. On one hand, the representation of any lattice in \(n>1\) dimensions is non-unique, i.e., there exist different sets of primitive vectors that yield the same lattice structure. On the other hand, different representations of the crystal can be obtained by shifting the structure element or manipulating the underlying lattice structure, e.g., by using integer linear combinations of the primitive vectors and adjusting the structure element accordingly.
,
and
with associated structure elements \(\mathfrak {s}, \widehat{\mathfrak {s}}\) and \(\widetilde{\mathfrak {s}}\) such that
. Furthermore, three different primitive cells are illustrated: The corresponding parallelotopes
,
as well as a hexagon corresponding to the Voronoi cell of
and
be two lattices, if
then
is called sublattice of
.
is a sublattice of
if and only if
.
, then In addition both normal forms H and S are unique with respect to
.
is in HNF,
is in SNF.
and
be two lattices then the following statements are equivalent. 
.
and
.
.
and
have the same HNF.
be a crystal and
be a sublattice. We define the crystal torus
by
For every
, their equivalence class \([x+\mathfrak {s}]\) is in
. Furthermore, the elements of
are defined by the equivalence
, \(M \in \mathbb {\mathbb {Z}}^{n \times n}\), uniquely.
with
, and the lattice torus
with
as depicted in Fig. 3. Even though we know that the quotient space consists of
different elements, there is no apparent canonical list of these elements. Fortunately, a canonical ordering of the lattice points on a torus can be formulated using the Hermite or Smith normal form of M.
be arbitrary, i.e.,
for some \(M \in \mathbb {\mathbb {Z}}^{n \times n}\).
denotes the altered lattice basis.
. The second statement follows from
and hence
. \(\square \)
,
and
are depicted in Fig. 3. In the remainder we drop the bracket notation for reasons of readability.
is given by 
is given by where
.
with
being an arbitrary sublattice of
. While it is significantly easier to be mathematically precise in this general finite setting than in an infinite setting it is also much closer to the targeted applications, namely finite dimensional approximations of PDEs and Hamiltonians. Eventually we only work with operators as part of numerical simulations, i.e., we face only a finite number of unknowns/lattice points anyway. The quotient group
,
, precisely describes such an arbitrarily large but finite torus. To shorten notation we use
instead of
whenever we do not specify
explicitly.
where
corresponds to the crystal of the domain and
corresponds to the crystal of the codomain. The function spaces are defined by
A value \(f_j(x)\),
, corresponds to a value at the position \(x + \mathfrak {s}_j\). The function space is equipped with the scalar product
where \(\langle f(x),g(x)\rangle _{2} := \sum _{\ell =1}^{|\mathfrak {s}|} f_\ell (x) \overline{g_\ell (x)}\) denotes the Euclidean scalar product on \(\mathbb {C}^{|\mathfrak {s}|}\).
be a crystal operator. The following statements are equivalent. 
and
we have
-translationally invariant, i.e.,
where the translation operator is defined by
.
be a lattice. Its dual lattice
is the set
A lattice basis of the dual lattice is given by
. The elements of
may also be referred to as wave vectors.
with a structure element \(\mathfrak {s}=(\mathfrak {s}_1,\ldots ,\mathfrak {s}_m)\) is given by the wave functions \(e_{1,k},e_{2,k},\ldots ,e_{m,k}\) defined bywith
.
is given in Smith normal form, making use of Theorem 2.3 and the geometric sum formula. \(\square \)
along with its dual
is given in Fig. 4.
(left) and its dual torus
(right). In here, the lattices bases are denoted by
and
with
be a multiplication operator. Then the subspaces \(H_k\) of Eq. (3.1) are L-invariant, i.e., \(L(H_k) \subseteq H_k\).
-translationally operator via its symbols, which are formally defined as follows.
be a multiplication operator with
Then
.
, i.e., the set of primitive vectors that define an arbitrary sublattice
of
, is to simplify the theory developed in Sect. 3 by turning an infinite dimensional setting to an (arbitrarily large) finite one. Though there is another interpretation to it as well. In Theorem 3.4
explicitly specifies the resolution of the frequency space as seen in Fig. 4, i.e.,
where the spectrum of the multiplication operator is sampled. Due to the reciprocal nature of the dual space, the larger
is, the finer the resolution becomes.
with
Then, the discretized Laplacian
using finite differences is given by
with non-zero multipliers:
via
withwhere \(X_{\mathrm{red}}\) and \(X_{\mathrm{black}}\) correspond to the red and black unknowns of the torus
as illustrated in Fig. 5b. In order to analyze this composite operator in our framework, we write all occurring operators as multiplication operators. It is now important that the red–black splitting of
implies the crystal
with
such that
,
and
(cf. Fig. 5b). With respect to this crystal the operators \(S_r\) and \(S_b\) can be written as multiplication operators
with
We now have described all individual operators of G, each one defined with respect to its own (minimal) translational invariance, but the domains and codomains are not identical, i.e.,
, such that we cannot directly use the computation rules described in “Appendix A”. In order to carry on with the analysis we have to rewrite the operators with respect to a common crystal structure. In this example we construct this structure by hand, but this process can be automated as explained in Sect. 5.
is yet another representation of
, the operator \(L_h\) can be rewritten with respect to this crystal (cf. Fig. 5) as
with
and non-zero multipliers:
and in b) with respect to
by first computing the individual symbols\(I_k, (\hat{S}_r)_k, (\hat{S}_b)_k\) and \((\hat{L}_h)_k\) and assembling the symbols \(\hat{G}_k\) according to Eq. (4.1) and the rules in “Appendix A”, followed by the computation of the eigenvalues of the matrices \(\hat{G}_k\). The resulting spectral information of the discretized Laplace operator \(\hat{L}_h\) and the error propagator \(\hat{G}\) is illustrated in Fig. 6, where it is sampled on the dual lattice
. Note, that one naturally obtains two eigenvalues per sampled wave vector k. In case of the spectrum of the red–black Gauss–Seidel error propagator, one of the two eigenvalues is equal to zero for all wave vectors k.
and
denote the columns of
,
. If there exists an \(r\in \mathbb {Z}\), such that
, then there is a lattice
with
and
with
as small as possible. A lattice basis of
is given by
where
is a diagonal matrix with
, where \(S= V^{-1} M T^{-1} = {\text {diag}}{(s_{1},\ldots ,s_{n})}\) is the SNF of M (cf. Definition 2.7) and \({\text {gcd}}(r,s_{i})\) denotes the greatest common divisor of r and \(s_i\). Consequently, we write
and call it the least common multiple of
and
.
, such that
with
and
as small as possible. Using Theorem 2.2, i.e.,
, for any unimodular matrices \(U_1,V_1\), we can assume the equality
for any unimodular U and
in Hermite normal form (cf. Theorem 2.1). Plugging in the Smith decomposition VST of
and defining \(U:=T^{-1}\), we find
Both matrices
have to be integral with
as small as possible. It can easily be verified that
is the optimal choice for the diagonal entries. With this choice, the off-diagonal entries
have to be integral multiples of
. Due to the fact that
is in Hermite normal form, the off-diagonal entries are zero. \(\square \)
be a crystal and
a sublattice. Denoting
,5 the set
defines a primitive cell of
, and the tuple
defines a structure element of
such that
, meant as a one-to-p correspondence.
, \(j = 1,\ldots ,p\). Then, each element in
can be written as
and there is a unique y, such that
with
and
. Thus, we find z as a unique part of the element
This argument works in the other direction in the same way. \(\square \)
, thus using this explicit representation Theorem 5.2 implies a congruence of the function spaces
given by the natural isomorphism
,
as (f) and \((\eta f)\) describe the same value distribution on the crystal. This congruence in turn implies that the coarsest possible crystal interpretation, i.e.,
, is simply the complex coordinate space
with
. The scalar product on
then corresponds to the Euclidean scalar product on \(\mathbb {C}^{mn}\) up to a factor of n.
,
, a sublattice
and a multiplication operator
Then, using
, the multiplication operator
with block matrices \((m_G^{(y)})_{i,k} := m_L^{(y-\mathfrak {t}_i+\mathfrak {t}_k)} \in \mathbb {C}^{|\mathfrak {c}|\times |\mathfrak {d}|}\) fulfills the commutative diagram: 
denote the natural isomorphisms between the congruent crystal representations.
\(\square \)
,
are congruent with respect to
if the structure elements are of the same size, i.e., \(|\mathfrak {s}| = |\mathfrak {t}| = m\), and there is a permutation \(\pi :\{1,\ldots ,m\} \rightarrow \{1,\ldots ,m\}\) as well as shifts
, such that
be a multiplication operator. We say L is in normal form if
,
and
defined by
Further let \(\hat{\mathfrak {t}}\) be a structure element which is obtained from \(\mathfrak {t}\) when shifted element-wise along
, i.e.,where
and \(m=|\mathfrak {t}|\). Then, the operators \(\hat{L}\) and \(\hat{G}\) given by
fulfill the commutative diagram: 
as f and \((\mathbb {T}f)\) describe the same value distribution on the crystal.7 Again, a straightforward calculation yields
Analogously we find
. \(\square \)
and
defined by
Let further \(\hat{\mathfrak {t}}\) be a structure element which is a permuted version of \(\mathfrak {t}\), i.e.,where \(m=|\mathfrak {t}|\), \(\pi :\{1,\ldots ,m\} \rightarrow \{1,\ldots ,m\}\) is a permutation and \(m_\pi \in \{0,1\}^{m\times m}\) the corresponding permutation matrix. Then, the operators \(\hat{L}\) and \(\hat{G}\) given by
fulfill the commutative diagram: 
is a multiplication operator defined by \((p f)(x) = m_\pi f(x)\) for all
, the statement is true due to the rules of computation in Lemma A.1. \(\square \)
where the underlying lattice is triangular, i.e., any three nearby lattice points form an equilateral triangle. We have
with the structure element
The parameter \(a= 1.42\AA {}\) which denotes the distance of two neighboring atoms can be omitted as it does not occur in the tight-binding formulation. An illustration of the crystal has already been given in Fig. 2.
with non-zero multipliers
. Rewriting the graphene crystal
with respect to this coarser lattice
, we find
with the structure element
The splitting is then given by the structure elements
such that
,
,
and
. In the case of the nearest neighbor Hamiltonian any two hexagons of the same color do not interact. Thus, a relaxed sweep on the unknowns of one color is cheap and, in addition, yields a good degree of parallelism.
. After that the structure element needs to be adjusted such that all unknowns and their couplings among each other are found within the central multiplier \(m_{\hat{L}}^{(0)}\). Consider the structure element \(\mathfrak {t}\). As can be seen in Fig. 7b, the coupling among the unknowns \(\mathfrak {t}^{(\ell )}\) which we want to update simultaneously are found in the multipliers: 
Finally, the error propagator corresponding to a single color relaxed block Gauss–Seidel update can be written as
with \((S^{(\ell )}f)(x) := (m_P m_{\hat{L}}^{(0)} m_P)f(x)\) where \(m_P\) is the diagonal matrixWe summarize the algorithmical steps to obtain the error propagators.
The function g denotes the composition of the error propagators
Note, that in this algorithm all operators are checked for compatibility and any incompatibility with respect to domains and codomains is dealt with using the transformations introduced in Sect. 5.
. b Plot of the spectral radii of the two-grid method using the overlap smoother
. Defining the coarse structure element by \(2\mathfrak {s}\), and with \(\mathfrak {t}\) denoting the structure element of the fine crystal according to the coarse lattice basis, the restriction operator can be described as
The multipliers of the restriction operator according to [12] then read
,
The frequencies corresponding to the kernel modes are known as the Dirac points.
The function f denotes the composition of the two-grid error propagator
A plot of the spectral radii of the two-grid error propagator is given in b) of Fig. 8 which shows that the two-grid method converges with a convergence rate of \(\rho _{\max } \approx 0.167\). Thus, this new method with overlapping colored block Gauss–Seidel smoothing not only yields opportunities for parallel computations, but also converges faster than the old approach which used Kaczmarz smoothing.
obtained in aLFA
with
By multiplying Eq. (6.3) with \(h^2\), the grid size can be incorporated into the material parameter \(\sigma _h := h^2\sigma \). Then the discrete operator \(K=K_{cc} + \sigma _h M\) can be expressed as a multiplication operator by
where the elements
and
correspond to the (midpoints of the) horizontal and the vertical edge, respectively (cf. Fig. 9). According to [3] the multipliers are given by:
are ordered from bottom to top and left to right which leads us to the following definition for
:The error propagator of the smoother on the original crystal
is a node-based lexicographic Gauss–Seidel iteration. When updating a horizontal edge \(x + \mathfrak {e}_h\),
it is assumed that all edges \(y+\mathfrak {e}_h\) and \(y+\hat{\mathfrak {e}}_v\),
, with \(y<x\) are already updated. When updating the edge \(y+\hat{\mathfrak {e}}_v\), it is additionally assumed that \(x+\mathfrak {e}_h\) is already updated (cf. [3, Figure 6.1]). In order to obtain the error propagator which exactly represents this ordering, it is convenient to rewrite the operator K with respect to this representation of the structure element, that is
which can be obtained with Algorithm B.6 via
The corresponding error propagator is then given by
with the multipliersIn here, only the lower triangular part \(\texttt {tril}(m_{\hat{K}}^{(0)})\) of the central multiplier is used due to the fact that it represents a Gauss–Seidel sweep where a horizontal edge is updated before a vertical edge.
, i.e., the nodal points between the edges. The transfer operator to this crystal is the discrete gradient operator defined by
with non-zero multipliers
Using a Galerkin construction, i.e., \(P_N = R_N^T\), the coarse grid operator \(K_N = R_N K P_N\) can be obtained using the computation rules in Lemma A.1. Inversion of this auxiliary space operator is then approximated by Gauss–Seidel. Thus, the auxiliary space correction with a single smoothing step on the auxiliary space is given by
where
consists of the scalar multipliersWith this definition of the auxiliary space correction, the half-hybrid smoother consists of the following steps. The smoother is analyzed analogously to Sect. 6.1 with Algorithm B.1 by computing the spectral radii via
where g denotes the composition of the error propagators
In Fig. 10 a) a contour plot of \(\rho (G_k)\) with \(\sigma _h = 0.01\), with respect to
is given. It corresponds to the result given in [3, Figure 6.2, right].
and the original crystal
with respect to the lattice \(2\mathcal {A}\) is given by
with
Then, according to [3] the restriction operator is given as
with the multipliers:
where f denotes the composition of the two-grid error propagator
Figure 10b shows the spectral radii, \(\sup _k \rho (M_k)\), of the two-grid error propagator as a function of \(\sigma _h\). We used exactly the same orderings in pre- and post-smoothing, as described in [3]. Furthermore, we double-checked the results with convergence tests similar to Table 1. However, the obtained results show major differences to the one in [3, Figure 8.1, left], which leads us to believe that our assumptions on the lexicographic orderings employed in pre- or post-smoothing in [3] are wrong, as these have a large impact on the convergence rates.
, \(\sigma _h = 0.01\). b Contour plot of the convergence estimates of the two-grid method \(\sup _k \rho (M_k)\) with respect to \(\sigma _h\). The plots correspond to the results [3, Figure 6.2, right] and [3, Figure 8.1, left], respectively
