Abstract
This paper concerns the spectral analysis of matrix-sequences that are generated by the discretization and numerical approximation of partial differential equations, in case the domain is a generic Peano–Jordan measurable set. It is observed that such matrix-sequences often present a spectral symbol, that is a measurable function describing the asymptotic behaviour of the eigenvalues. When the domain is a hypercube, the analysis can be conducted using the theory of generalized locally Toeplitz (GLT) sequences, but in case of generic domains, a different kind of matrix-sequences and theory has to be formalized. We thus develop in full detail the theory of reduced GLT sequences and symbols, presenting some application to finite differences and finite elements discretization for linear convection–diffusion–reaction differential equations.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Partial differential equations (PDEs) are extensively used in physics, engineering and applied sciences in order to model real-world problems. A closed form for the analytical solution of such PDEs is normally not available. It is therefore of fundamental importance to approximate the solution u of a PDE by means of some numerical method.
Despite the differences that allow one to distinguish among the various numerical methods, the principle on which most of them are based is essentially the same: they first discretize the continuous PDE by introducing a mesh, characterized by some discretization parameter n, and then they compute the corresponding numerical solution \(u_n\), which will (hopefully) converge in some topology to the solution u of the PDE as \(n\rightarrow \infty \), i.e., as the mesh is progressively refined. If we consider a linear PDE
and a linear numerical method, then the actual computation of the numerical solution reduces to solving a linear system
whose size \(d_n\) diverges with n.
Solving high-dimensional linear systems in an efficient way is fundamental to compute accurate solutions in a reasonable time. In this direction, it is known that the convergence properties of mainstream iterative solvers, such as multigrid and preconditioned Krylov methods, strongly depend on the spectral features of the matrices to which they are applied. The knowledge of the asymptotic distribution of the sequence \(\{A_{n}\}_n\) is therefore a useful tool we can use to choose or to design the best solver and method of discretization.
The discretization methods for linear PDEs often lead to sequences of linear systems admitting a so-called spectral symbol. It is an entity associated with a matrix-sequence of increasing size, and it represents the asymptotic distribution of the spectra of the matrices. More specifically, given a matrix-sequence \( \{A_{n}\}_n \), where \( A_n\in \mathbb C^{d_n\times d_n} \), with \(d_n\xrightarrow {n\rightarrow \infty }\infty \), then we say that \( \{A_{n}\}_n \) possesses a spectral symbol \(f:D\subseteq \mathbb R^q\rightarrow \mathbb C\), \(q\ge 1\), when it satisfies
for every continuous function \(F:\mathbb C\rightarrow \mathbb C\) with compact support. Here D is a measurable set with finite Lebesgue measure \(\mu (D)>0\) and \(\lambda _i(A_n)\) are the eigenvalues of \(A_n\). In this case we write
In case of Toeplitz or Toeplitz-like matrices, this topic has been the subject of several studies and research, starting from Szegö [22], Avram [2], Parter [26], and followed by various other authors [11, 13,14,15,16, 31, 33, 34, 36, 37]. Asymptotic distributions also naturally arise in the theory of orthogonal polynomials, in which case the zeros of the polynomials are seen as the eigenvalues of appropriate Jacobi matrices [18, 21, 23, 24, 35].
A powerful set of tools to compute and analyse the symbols comes from the theory of generalized locally Toeplitz (GLT) sequences. It stems from Tilli’s work on locally Toeplitz (LT) sequences [32] and from the spectral theory of Toeplitz matrices. Nowadays, the main and most comprehensive sources in the literature for theory and applications of GLT spaces are the books [9, 10, 19, 20], in which we can find a careful and complete description of GLT sequences, block GLT sequences, and their respective multivariate versions. For more information, check also the articles [4,5,6,7,8, 27, 28]. In short, the GLT theory enables us to derive the symbol for large families of matrix-sequences, from simple components. Since the relation linking the sequences to the so-built symbols turns out to be an isomorphism of spaces, we can denominate the chosen symbol for \(\{A_{n}\}_n\) as its GLT symbol, and we write
When dealing with Linear PDE such as
the discretization methods often lead to sequences of linear systems admitting a GLT symbol with domain \(([0,1]\times [-\pi ,\pi ])^d\). Interestingly enough, in this paper we observe that when a regular enough domain \(\Omega \) of u is considered, instead of \([0,1]^d\), a similar analysis can be conducted.
There are already well-known cases of linear PDE on non-rectangular domains. In [25], for example, the authors first show how to define a new class of GLT sequences on triangles, and then deal with polygonal domains through a decomposition of the space into a finite numbers of triangles. This approach indeed is a simple way to analyse systems and find the respective symbols on polygonal domains.
In the context of Finite Elements methods with constant coefficients, the domains of the basis functions can be arbitrary since the main focus is on the values of the bilinear form evaluated on couples of basis functions, so the resulting symbols have domain \([-\pi ,\pi ]^d\). The case of FE or collocation methods with variable coefficients has been studied on the condition that the physical domain \(\Omega \) can be described by a global geometry function \(G : [0, 1]^d \rightarrow \Omega \), which is invertible and satisfies \(G(\partial ([0, 1]^d)) = \partial \Omega \) (see Section 7.5 in [20]).
Now we want to explore a more general case, starting from a domain \(\Omega \) with few properties. We consider a bounded \(\Omega \), so that we can operate an affine invertible transformation \(l:\mathbb R^d\rightarrow \mathbb R^d\) , consisting in the composition of a translation and a dilation, such that \(l^{-1}(\Omega )=\Omega '\subseteq [0,1]^d\). Notice that if \(v = u\circ l:\Omega '\rightarrow \mathbb C\), then
so we can solve the problem on \(\Omega '\) for v, and then compute \(u = v\circ l^{-1}\). From now on we will only consider domains \(\Omega \) contained in \([0,1]^d\), and we work in the restricted euclidean topology and Lebesgue measure \(\mu \) of \([0,1]^d\), unless specified differently.
The analysis will lead us to introduce a variation of the classical GLT sequences, that we call reduced GLT sequences. The name “reduced GLT” appears in [28] where some ideas on its construction is given. More attempts following the same arguments can be found in [1, 3, 27, 29], where the class of sequences in use has never been fully formalized. Here we furnish a systematic and rigorous approach to the definition and construction of reduced GLT sequences, finally providing a solid background for all the previous documents.
The paper is organized as follows. In Sect. 2 we recall first the multidimensional notation we will be using throughout all the document, and then we report the main concepts and results already present in previous literature, that we will need to develop our new theory. In particular, we remind the concepts of symbol, approximating classes of sequences and multilevel GLT sequences. Section 3 is devoted to discussions on the domain \(\Omega \) and the grids we use to discretize our problems. In Sect. 4 we introduce the restriction and expansion operators that we need to generate the reduced GLT sequences from classical GLT sequences. Thanks to the properties of these operators, we will be able to derive a number of preliminary results, that will lead in Sect. 5 to the full formalization of the theory of reduced GLT sequences. The following two Sects. 6 and 7 show how the theory of reduced GLT can be applied to discretisation of linear PDEs on a generic domain \(\Omega \), in case of, respectively, a finite differences discretization, and a finite elements discretization. In the final Sect. 8, we report further studies that are currently been conducted on other applications for the reduced GLT sequences, and also a possible generalization.
2 Generalized locally Toeplitz sequences
Here we recall the basic notions, results and concepts of multilevel GLT sequences and linked subjects, without going too much into technical details. All the results we report in this section can be found more in detail in [20, Chapter 6], altogether with an extensive and complete discussion about the GLT sequences.
2.1 Multidimensional notation
When dealing with multilevel sequences, matrices and vectors, we will use the multi-index notation. A multi-index \({\varvec{i}}\in \mathbb N^d\), also called a d-index, is simply a vector in \(\mathbb N^d\); its components are denoted by \(i_1,\ldots ,i_d\).
-
\(\varvec{0},\,{\varvec{1}},\,{\mathbf {2}},\,\ldots \) are the vectors of all zeros, all ones, all twos, \(\ldots \) (their size will be clear from the context).
-
For any d-index \({\varvec{n}}\), \(N({\varvec{n}})=\prod _{j=1}^dn_j\) and \({\varvec{n}}\rightarrow \infty \) means that \(\min ({\varvec{n}})=\min _{j=1,\ldots ,d}n_j\rightarrow \infty \).
-
If \(\varvec{h},\varvec{k}\) are d-indices, \(\varvec{h}\le \varvec{k}\) means that \(h_r\le k_r\) for all \(r=1,\ldots ,d\), while \(\varvec{h}\not \le \varvec{k}\) means that \(h_r>k_r\) for at least one \(r\in \{1,\ldots ,d\}\).
-
If \(\varvec{h},\varvec{k}\in \mathbb N^d\) are multi-indices, \(\varvec{h}\preceq \varvec{k}\) means that \(\varvec{h}\) precedes (or equals) \(\varvec{k}\) in the lexicographic ordering (which is a total ordering on \(\mathbb N^d\)).
-
The multi-index range \(\varvec{h},\ldots ,\varvec{k}\) is the set \(\{{\varvec{j}}\in \mathbb Z^d:\,\varvec{h}\le {\varvec{j}}\le \varvec{k}\}\). We assume for the multi-index range \(\varvec{h},\ldots ,\varvec{k}\) the standard lexicographic ordering:
$$\begin{aligned} \left[ \ \ldots \ \left[ \ \left[ \ (j_1,\ldots ,j_d)\ \right] _{j_d=h_d,\ldots ,k_d}\ \right] _{j_{d-1}=h_{d-1},\ldots ,k_{d-1}}\ \ldots \ \right] _{j_1=h_1,\ldots ,k_1}. \end{aligned}$$(1)For instance, in the case \(d=2\) the ordering is
$$\begin{aligned}&(h_1,h_2),\,(h_1,h_2+1),\,\ldots ,\,(h_1,k_2),\,(h_1+1,h_2),\,(h_1+1,h_2+1),\,\ldots ,\\ {}&(h_1+1,k_2),\ldots \,\ldots ,\,(k_1,h_2),\,(k_1,h_2+1),\,\ldots ,\,(k_1,k_2). \end{aligned}$$ -
When a d-index \({\varvec{j}}\) varies over a multi-index range \(\varvec{h},\ldots ,\varvec{k}\) (this is sometimes written as \({\varvec{j}}=\varvec{h},\ldots ,\varvec{k}\)), it is understood that \({\varvec{j}}\) varies from \(\varvec{h}\) to \(\varvec{k}\) following the specific ordering (1). For instance, if \({\varvec{n}}\in \mathbb N^d\) and if we write \(\varvec{x}=[x_{\varvec{i}}]_{{\varvec{i}}={\varvec{1}}}^{\varvec{n}}\), then \(\varvec{x}\) is a vector of size \(N({\varvec{n}})\) whose components \(x_{\varvec{i}},\ {\varvec{i}}={\varvec{1}},\ldots ,{\varvec{n}}\), are ordered in accordance with (1): the first component is \(x_{\varvec{1}}=x_{(1,\ldots ,1,1)}\), the second component is \(x_{(1,\ldots ,1,2)}\), and so on until the last component, which is \(x_{\varvec{n}}=x_{(m_1,\ldots ,m_d)}\). Similarly, if \(X=[x_{{\varvec{i}}{\varvec{j}}}]_{{\varvec{i}},{\varvec{j}}={\varvec{1}}}^{{\varvec{n}}}\), then X is a \(N({\varvec{n}})\times N({\varvec{n}})\) matrix whose components are indexed by two d-indices \({\varvec{i}},{\varvec{j}}\), both varying from \({\varvec{1}}\) to \({\varvec{n}}\) according to the lexicographic ordering (1).
-
Given \(\varvec{h},\varvec{k}\in \mathbb N^d\) with \(\varvec{h}\le \varvec{k}\), the notation \(\sum _{{\varvec{j}}=\varvec{h}}^{\varvec{k}}\) indicates the summation over all \({\varvec{j}}\) in \(\varvec{h},\ldots ,\varvec{k}\).
-
If \(\varvec{h}\) is a d-index in the range \({\varvec{1}},\dots ,{\varvec{n}}\), then \(|\varvec{h}|\) is
$$\begin{aligned}&h_d + n_d(h_{d-1} -1 + n_{d-1}( h_{d-2}-1 + \dots +n_3(h_2-1 + n_2(h_1-1)))\dots ) \\&= h_d + \sum _{i=1}^{d-1} \left( (h_i-1)\prod _{j=i+1}^{d} n_j \right) \end{aligned}$$maps the d-indices to the set \(\{1,2,\dots ,N({\varvec{n}})\}\), and the map is increasing with respect to the lexicographic ordering, since \(\varvec{h}\succeq \varvec{k}\iff |\varvec{h}|\ge |\varvec{k}|\).
-
Operations involving d-indices that have no meaning in the vector space \(\mathbb Z^d\) must always be interpreted in the componentwise sense. For instance, \({\varvec{i}}{\varvec{j}}=(i_1j_1,\ldots ,i_dj_d)\), \({\varvec{i}}/{\varvec{j}}=(i_1/j_1,\ldots ,i_d/j_d)\), etc.
In this context, by a sequence of matrices (or matrix-sequence) we mean a sequence of the form \(\{A_{\varvec{n}}\}_n\), where \({\varvec{n}}=(n_1,\dots ,n_d)\) depends on n and \({\varvec{n}}\rightarrow \infty \) as \(n\rightarrow \infty \). In many cases, it is natural to assume that \({\varvec{n}}+{\varvec{1}}= n{\varvec{\nu }}\), where \(\varvec{\nu }\) is a vector of rational constants and n diverges to infinity. It is always understood that a matrix \(A_{\varvec{n}}\) parameterized by a d-index \({\varvec{n}}\) has dimension \(N({\varvec{n}}) = n_1\cdot \dots \cdot n_d\); its entries will be indexed by two d-indices \({\varvec{i}},{\varvec{j}}\).
2.2 Singular value symbol and approximating classes of sequences
Along with the concept of spectral symbol already introduced, we need to recall the notion of singular value symbol, that is, a measurable function describing the asymptotic distribution of the singular values of a matrix-sequence. Given a multilevel sequence \(\{A_{{\varvec{n}}}\}_n\), a singular value symbol associated with \(\{A_{{\varvec{n}}}\}_n\) is a measurable function \(f:D\subseteq \mathbb R^q\rightarrow \mathbb C\) satisfying
for every continuous function \(F:\mathbb R\rightarrow \mathbb C\) with compact support, where D is a measurable set with finite Lebesgue measure \(\mu (D)>0\) and \(\sigma _i(A_{\varvec{n}})\) are the singular values of \(A_n\). In this case we write
A sequence of matrices \(\{Z_{\varvec{n}}\}_n\) such that \(\{Z_{\varvec{n}}\}_n\sim _\sigma 0\) is referred to as a zero-distributed sequence. In other words, \(\{Z_{\varvec{n}}\}_n\) is zero-distributed iff
where \(N({\varvec{n}})\) is the size of \(Z_{\varvec{n}}\). Given a sequence of matrices \(\{Z_{\varvec{n}}\}_n\), with \(Z_{\varvec{n}}\) of size \(N({\varvec{n}})\), the following properties hold. In what follows, we use the natural convention \(C/\infty =0\) for all numbers C.
- Z 1.:
-
\(\{Z_{\varvec{n}}\}_n\sim _\sigma 0\) iff \(Z_{\varvec{n}}=R_{\varvec{n}}+N_{\varvec{n}}\) with
$$\begin{aligned} \lim _{n\rightarrow \infty }(N({\varvec{n}}))^{-1}\mathrm{rank}(R_{\varvec{n}})=\lim _{n\rightarrow \infty }\Vert N_{\varvec{n}}\Vert =0. \end{aligned}$$ - Z 2.:
-
\(\{Z_{\varvec{n}}\}_n\sim _\sigma 0\) if there exists a \(p\in [1,\infty ]\) such that
$$\begin{aligned} \lim _{n\rightarrow \infty }(N({\varvec{n}}))^{-1/p}\Vert Z_{\varvec{n}}\Vert _p=0, \end{aligned}$$where \(\Vert \cdot \Vert _p\) is the p-Schatten norm.
The space of matrix-sequences also presents a metric structure, induced by a distance inspired from the concept of Approximating Class of Sequences (a.c.s.). In fact, a sequence of matrix-sequences \(\{B_{{\varvec{n}},m}\}_n\) is said to be an a.c.s. for \(\{A_{{\varvec{n}}}\}_n\) if there exist \(\{N_{{\varvec{n}},m}\}_n\) and \(\{R_{{\varvec{n}},m}\}_n\) such that for every m there exists \(n_m\) with
for every \(n>n_m\), and
In this case, we say that \(\{B_{{\varvec{n}},m}\}_n\) is a.c.s. convergent to \(\{A_{{\varvec{n}}}\}_n\), and we use the notation \(\{B_{{\varvec{n}},m}\}_n\xrightarrow {a.c.s.}\{A_{{\varvec{n}}}\}_n\). In other words, \(\{B_{{\varvec{n}},m}\}_n\) converges to \(\{A_{{\varvec{n}}}\}_n\) if the difference \(\{A_{\varvec{n}}-B_{{\varvec{n}},m}\}_n\) can be decomposed into \(\{N_{{\varvec{n}},m}\}_n\) of ’small norm’ and \(\{R_{{\varvec{n}},m}\}_n\) of ’small rank’.
We say that a sequence \(\{A_{{\varvec{n}}}\}_n\) is sparsely unbounded (s.u.), whenever the rate of diverging singular values goes to zero. This happens, for example, whenever the sequence admits a singular value symbol. Using this notion, we can enunciate the property of the a.c.s. we will need in the following.
-
ACS 1. \(\{A_{\varvec{n}}\}_n\sim _\sigma f\) iff there exist sequences of matrices \(\{B_{{\varvec{n}},m}\}_n\sim _\sigma f_m\) such that \(\{B_{{\varvec{n}},m}\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}\}_n\) and \(f_m\rightarrow f\) in measure.
-
ACS 2. Suppose each \(A_{\varvec{n}}\) is Hermitian. Then, \(\{A_{\varvec{n}}\}_n\sim _\lambda f\) iff there exist sequences of Hermitian matrices \(\{B_{{\varvec{n}},m}\}_n\sim _\lambda f_m\) such that \(\{B_{{\varvec{n}},m}\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}\}_n\) and \(f_m\rightarrow f\) in measure.
-
ACS 3. If \(\{B_{{\varvec{n}},m}\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}\}_n\) and \(\{B_{{\varvec{n}},m}'\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}'\}_n\), with \(A_{\varvec{n}}\) and \(A_{\varvec{n}}'\) of the same size \(N({\varvec{n}})\), then
-
\(\{B_{{\varvec{n}},m}^*\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}^*\}_n\),
-
\(\{\alpha B_{{\varvec{n}},m}+\beta B_{{\varvec{n}},m}'\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{\alpha A_{\varvec{n}}+\beta A_{\varvec{n}}'\}_n\) for all \(\alpha ,\beta \in \mathbb C\),
-
\(\{B_{{\varvec{n}},m}B_{{\varvec{n}},m}'\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}A_{\varvec{n}}'\}_n\) whenever \(\{A_{\varvec{n}}\}_n,\{A_{\varvec{n}}'\}_n\) are s.u.,
-
\(\{B_{{\varvec{n}},m}C_{\varvec{n}}\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}C_{\varvec{n}}\}_n\) whenever \(\{C_{\varvec{n}}\}_n\) is s.u.
-
-
ACS 4. Let \(p\in [1,\infty ]\) and assume for each m there is \(n_m\) such that, for \(n\ge n_m\),
$$\begin{aligned} \Vert A_{\varvec{n}}-B_{{\varvec{n}},m}\Vert _p\le \varepsilon (m,n)(N({\varvec{n}}))^{1/p}, \quad \lim _{m\rightarrow \infty }\limsup _{n\rightarrow \infty }\varepsilon (m,n)=0. \end{aligned}$$Then \(\{B_{{\varvec{n}},m}\}_n{\mathop {\longrightarrow }\limits ^{\mathrm{a.c.s.}}}\{A_{\varvec{n}}\}_n\).
It turns out that the notion of a.c.s. begets a metric structure on the space of sequences \({\mathscr {E}}\). The distance
where, by convention, \(\sigma _{N({\varvec{n}})+1}(C_{\varvec{n}})=0\), has been proved to induce the a.c.s. convergence between sequences. Moreover, \(d_{\mathrm{a.c.s.}}(\{A_{\varvec{n}}\}_n,\{B_{\varvec{n}}\}_n)=0\) iff \(\{A_{\varvec{n}}-B_{\varvec{n}}\}_n\) is zero-distributed, and \(d_{\mathrm{a.c.s.}}\) turns \(\,{\mathscr {E}}\) into a complete pseudometric space \(({\mathscr {E}},d_{\mathrm{a.c.s.}} )\) where the statement “\(\{\{B_{{\varvec{n}},m}\}_n\}_m\) converges to \(\{A_{\varvec{n}}\}_n\)” is equivalent to “\(\{\{B_{{\varvec{n}},m}\}_n\}_m\) is an a.c.s. for \(\{A_{\varvec{n}}\}_n\)”. In particular, we can reformulate the definition of a.c.s. in the following way: a sequence of sequences of matrices \(\{\{B_{{\varvec{n}},m}\}_n\}_m\) is said to be an a.c.s. for \(\{A_{\varvec{n}}\}_n\) if \(\{B_{{\varvec{n}},m}\}_n\) converges to \(\{A_{\varvec{n}}\}_n\) in \(({\mathscr {E}},d_{\mathrm{a.c.s.}} )\) as \(m\rightarrow \infty \), i.e., if \(d_\mathrm{a.c.s.} (\{B_{{\varvec{n}},m}\}_n,\{A_{\varvec{n}}\}_n)\rightarrow 0\) as \(m\rightarrow \infty \). The theory of a.c.s. may then be interpreted as an approximation theory for sequences of matrices, and for this reason we will use the convergence notation \(\{B_{{\varvec{n}},m}\}_n{\mathop {\longrightarrow }\limits ^\mathrm{a.c.s.}}\{A_{\varvec{n}}\}_n\) to indicate that \(\{\{B_{{\varvec{n}},m}\}_n\}_m\) is an a.c.s. for \(\{A_{\varvec{n}}\}_n\).
In view of what follows, let \(D\subset \mathbb R^k\) be a measurable set such that \(0<\mu (D)<\infty \) and define \(\mathscr {M}_D\) the space of measurable functions over D. If
then \(d_\mathrm{mea} \) is a distance on \(\mathscr {M}_D\) such that \(d_\mathrm{mea} (f,g)=0\) iff \(f=g\) a.e.; moreover, \(d_\mathrm{mea} \) turns \(\mathscr {M}_D\) into a complete pseudometric space \((\mathscr {M}_D,d_\mathrm{mea} )\) where the statement “\(f_m\) converges to f” is equivalent to “\(f_m\) converges to f in measure”.
2.3 Multilevel GLT
We now recall the theory of the multilevel generalized locally Toeplitz (GLT) sequences and symbols. A d-level GLT sequence \(\{A_{\varvec{n}}\}_n\) is a special d-level matrix-sequence equipped with a measurable function \(\kappa :[0,1]^d\times [-\pi ,\pi ]^d\rightarrow \mathbb C\), the so-called GLT symbol. Unless otherwise specified, the notation
means that \(\{A_{\varvec{n}}\}_n\) is a d-level GLT sequence with symbol \(\kappa \). The symbol of a d-level GLT sequence is unique in the sense that if \(\{A_{\varvec{n}}\}_n\sim _{GLT}\kappa \) and \(\{A_{\varvec{n}}\}_n\sim _{GLT}\xi \) then \(\kappa =\xi \) a.e. in \([0,1]^d\times [-\pi ,\pi ]^d\); conversely, if \(\{A_{\varvec{n}}\}_n\sim _{GLT}\kappa \) and \(\kappa =\xi \) a.e. in \([0,1]^d\times [-\pi ,\pi ]^d\) then \(\{A_{\varvec{n}}\}_n\sim _{GLT}\xi \). We report all the main properties of the GLT space summarized in 9 points.
-
GLT 1. If \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) then \(\{A_{\varvec{n}}\}_n\sim _{\sigma }\kappa \). If \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) and each \(A_{\varvec{n}}\) is normal, then \(\{A_{\varvec{n}}\}_n\sim _{\lambda }\kappa \).
-
GLT 2. If \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) and \(A_{\varvec{n}}=X_{\varvec{n}}+Y_{\varvec{n}}\), where
-
every \(X_{\varvec{n}}\) is Hermitian,
-
\(N({\varvec{n}})^{-1/2}\Vert Y_{\varvec{n}}\Vert _2\rightarrow 0\),
then \(\{A_{\varvec{n}}\}_n\sim _{\lambda }\kappa \).
-
-
GLT 3. Here we list three important examples of GLT sequences.
-
Given a function f in \(L^1([-\pi ,\pi ]^q)\), its associated Toeplitz sequence is \(\{T_{\varvec{n}}(f)\}_n\), where the elements are multidimensional Fourier coefficients of f:
$$\begin{aligned} T_{\varvec{n}}( f ) = [ f_{{\varvec{i}}-{\varvec{j}}} ]^{\varvec{n}}_{{\varvec{i}}, {\varvec{j}}=\mathbf{1}}, \qquad f_{\varvec{k}}= \frac{1}{(2\pi )^q} \int _{-\pi }^{\pi } f({\varvec{\theta }}) e^{-\text{ i } {\varvec{k}}\cdot {\varvec{\theta }}} {\mathrm{d}}\theta . \end{aligned}$$\(\{T_{\varvec{n}}(f)\}_n\) is a GLT sequence with symbol \(\kappa ({\mathbf {x}},{\varvec{\theta }})=f({\varvec{\theta }})\).
-
Given an almost everywhere continuous function, \(a:[0,1]^q\rightarrow \mathbb C\), its associated diagonal sampling sequence \(\{D_{\varvec{n}}(a)\}_n\) is defined as
$$\begin{aligned} D_{\varvec{n}}(a) = \text {diag}\left( \left\{ a\left( \frac{{\varvec{i}}}{{\varvec{n}}}\right) \right\} _{{\varvec{i}}=1}^{\varvec{n}}\right) . \end{aligned}$$\(\{D_{\varvec{n}}(a)\}_n\) is a GLT sequence with symbol \(\kappa ({\mathbf {x}},{\varvec{\theta }})=a({\mathbf {x}})\).
-
Any zero-distributed sequence \(\{Z_{\varvec{n}}\}_n\sim _\sigma 0\) is a GLT sequence with symbol \(\kappa ({\mathbf {x}},{\varvec{\theta }})=0\).
-
-
GLT 4. If \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) and \(\{B_{\varvec{n}}\}_n\sim _\mathrm{GLT}\xi \), then
-
\(\{A_{\varvec{n}}^H\}_n\sim _\mathrm{GLT}{{\overline{\kappa }}}\), where \(A_{\varvec{n}}^H\) is the conjugate transpose of \(A_{\varvec{n}}\),
-
\(\{\alpha A_{\varvec{n}}+\beta B_{\varvec{n}}\}_n\sim _\mathrm{GLT}\alpha \kappa +\beta \xi \) for all \(\alpha ,\beta \in \mathbb C\),
-
\(\{A_{\varvec{n}}B_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \xi \).
-
-
GLT 5. If \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) and \(\kappa \ne 0\) a.e., then \(\{A_{\varvec{n}}^\dag \}_n\sim _\mathrm{GLT}\kappa ^{-1}\), where \(A_{\varvec{n}}^\dag \) is the Moore–Penrose pseudoinverse of \(A_{\varvec{n}}\).
-
GLT 6. If \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) and each \(A_{\varvec{n}}\) is normal, then \(\{f(A_{\varvec{n}})\}_n\sim _\mathrm{GLT}f(\kappa )\) for all continuous functions \(f:\mathbb C\rightarrow \mathbb C\).
-
GLT 7. \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) if and only if there exist GLT sequences \(\{B_{{\varvec{n}},m}\}_n\sim _\mathrm{GLT}\kappa _m\) such that \(\kappa _m\) converges to \(\kappa \) in measure and \(\{B_{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}\{A_{\varvec{n}}\}_n\) as \(m\rightarrow \infty \).
-
GLT 8. If \(\{A_{\varvec{n}}\}_n\sim _\mathrm{GLT}\kappa \) and \(\{B_{\varvec{n}}\}_n\sim _\mathrm{GLT}\xi \) then \(d_{\mathrm{a.c.s.}}(\{A_{\varvec{n}}\}_n,\{B_{\varvec{n}}\}_n)=d_\mathrm{mea}(\kappa ,\xi )\).
-
GLT 9. For any measurable function \(\kappa :[0,1]^d\times [-\pi ,\pi ]^d\rightarrow \mathbb C\) there exists a d-level sequence \(\{A_{{\varvec{n}}}\}_n\) and functions \(a_{i,m},f_{i,m},\ i=1,\ldots ,N_m\), such that
-
\(\{A_{{\varvec{n}}}\}_n\sim _{GLT}\kappa \),
-
\(a_{i,m}\in C^\infty ([0,1]^q)\) and \(f_{i,m}\) is a trigonometric polynomial in q variables,
-
\(\sum _{i=1}^{N_m}a_{i,m}({\mathbf {x}})f_{i,m}({\varvec{\theta }})\) converges to \(\kappa ({\mathbf {x}},{\varvec{\theta }})\) a.e.,
-
\(\bigl \{\sum _{i=1}^{N_m}D_{{\varvec{n}}}(a_{i,m})T_{{\varvec{n}}}(f_{i,m})\bigr \}_n\xrightarrow {\mathrm{a.c.s.}}\{A_{\varvec{n}}\}_n\) as \(m\rightarrow \infty \).
-
A similar scheme can be found in [20], where all the points are the same, except for GLT1, GLT2 and GLT6, that can be deduced from the results in [6, 8]. Moreover, GLT8 has been substituted with its more powerful version from [10] and GLT9 has been expanded to include the fact that every measurable function is a GLT symbol for some sequence.
In the applications, one usually identifies the matrix-sequence at hand as a combination or limit of the simpler sequences in GLT3, for which a symbol is already known. Using the algebraic properties of GLT4, GLT5 and GLT6, or the metric property of GLT7, one can compute the GLT symbol of the sequence, that is automatically a singular value symbol by GLT1. Eventually, using the perturbation result in GLT2, one can prove that the GLT symbol is also a spectral symbol.
3 Characteristic sequences
We know by GLT9 that every measurable function with support in \(([0,1]\times [-\pi ,\pi ])^d\) is a GLT symbol for a sequence of matrices. Using this connection, we can associate to each measurable set \(\Omega \subseteq [0,1]^d\) a diagonal sequence \(\{D_{{\varvec{n}}}\}_n\) such that \(\{D_{{\varvec{n}}}\}_n\sim _{GLT}\upchi _\Omega \).
An important remark to be noted here is that we do not have a single choice of domain, functions and sequence. In fact two measurable sets \(\Omega ,\Omega '\) are identified whenever they differ for a negligible set, and it happens if and only if \(\upchi _\Omega \) and \(\upchi _{\Omega '}\) differ on the same negligible set. Moreover, two sequences have the same GLT symbol if and only if they differ by a zero-distributed sequence by GLT3 and GLT4.
In the case of characteristic function, though, it is always possible to choose \(\{D_{{\varvec{n}}}\}_n\) to be diagonal sequences with binary entries. This is easy to see in the case the characteristic function \(\upchi _\Omega \) is continuous almost everywhere, since we know from GLT3 that
In the remaining cases, one can obtain \(\upchi _\Omega \) as limit of characteristic functions of regular domains, so it is possible to reach the same conclusion using a diagonal argument.
Let us focus on the case \(\upchi _\Omega \) is continuous a.e., that is a condition common to almost every domain used in linear PDE. Given a measurable set \(\Omega \), the following assertions are equivalent:
-
the function \(\upchi _\Omega \) is continuous a.e.,
-
the function \(\upchi _\Omega \) is Riemann integrable,
-
\(\mu (\partial \Omega ) =0\),
-
the set \(\Omega \) is Peano–Jordan measurable,
where \(\partial \Omega \) is the boundary of the set \(\Omega \). Moreover, every measurable set \(\Omega \) respecting the condition, is equal, up to a negligible set, to its interior \(\Omega ^\circ \) and to its closure \(\overline{\Omega }\). The matrices \(D_{{\varvec{n}}}(\upchi _\Omega )\) give us a natural way to link its rows and columns to the points of type \(z_{{\varvec{i}}}:=\frac{\varvec{i}}{\varvec{n}}\) with \(\varvec{1}\le \varvec{i}\le {\varvec{n}}\) inside and outside of \(\Omega \). A Peano–Jordan measurable set \(\Omega \) is also well described by the diagonal matrices \(D_{\varvec{n}}(\upchi _\Omega )\), and consequently by the points \(z_{\varvec{i}}\), in the sense described by the following result.
Lemma 3.1
If \(\Omega \) is a Peano–Jordan measurable set, then
Proof
We know from GLT1 that
so in particular, if we consider a continuous function \(F:\mathbb R\rightarrow \mathbb C\) with compact support and such that \(F(1)=1\), \(F(0)=0\), then
\(\square \)
Actually, when \(\Omega \) is Peano–Jordan measurable, we can show also that the number of points \(z_{\varvec{i}}\) arbitrarily close to the boundary is negligible with respect to \(N({\varvec{n}})\). Call
the set of points whose distance from \(\partial \Omega \) is at most \(c\ge 0\). In the next result, we prove that \(K_c\) contains few points \(z_{\varvec{i}}\) when c tends to zero, so that in the applications we can ignore the conditions that arise from grid points that are close enough to the boundary.
Lemma 3.2
Given a sequence \(h_n\) of real nonnegative numbers converging to zero, and a Peano–Jordan measurable set \(\Omega \), then
Proof
Remember that \(\partial \Omega \) is always a closed set contained into \([0,1]^d\). Notice that \(K_c\) converge to \(K_0 = \partial \Omega \) as c tends to zero, so we know that
\(K_c\) is a closed subset of \([0,1]^d\) for every c since
and in both case there’s an open neighbourhood of p disjoint from \(K_c\). Moreover, if \(c>0\) then
and it is known that the set of points at fixed positive distance from a closed set is negligible [17], so we can conclude that \(\mu (\partial K_c) =0\). This is actually true also for \(K_0\) since
We can thus use Lemma 3.1 to infer that for every \(c\ge 0\)
Notice that if \(h_n < h_m\) then \(K_{h_n}\subseteq K_{h_m}\) and consequently \({{\,\mathrm{rk}\,}}(D_{{\varvec{n}}}(\upchi _{K_{h_n}}))\le {{\,\mathrm{rk}\,}}(D_{{\varvec{n}}}(\upchi _{K_{h_m}}))\). When we fix an index \(m>0\), we know that definitively \(h_n< h_m\) since \(h_n\) are converging to zero, so the following relation holds
\(\square \)
The points \(z_{\varvec{i}}\) form an uniform grid on \([0,1]^d\), but in applications the most used grid, denoted as \(\Xi _n\), is composed by points of the form
Consequentially we define a new diagonal matrix associated to \(\Omega \)
that has dimension \(N({\varvec{n}})\times N({\varvec{n}})\), the same as \(D_{{\varvec{n}}}(\upchi _\Omega )\). More in general, for any continuous a.e. function \(a:[0,1]^d\rightarrow \mathbb C\) we denote
so that \(I_{{\varvec{n}}}(a)\) and \(D_{{\varvec{n}}}(a)\) have the same dimension, and can actually be proved that they enjoy the same GLT and spectral symbol.
Lemma 3.3
If \(a:[0,1]^d\rightarrow \mathbb C\) is a continuous a.e. function, then
Proof
Notice that \(a:[0,1]^d\rightarrow \mathbb C\) is a continuous a.e. if and only if when we split it into real and imaginary part \(a = a_1 + \text {i} a_2\), both the real functions \(a_1\) and \(a_2\) are continuous a.e.. In the same way, we can split \(a_1\) and \(a_2\) in their positive and negative parts, and they are still continuous a.e.. By GLT4, we can thus suppose that \(a:[0,1]^d\rightarrow \mathbb R^+\), since it is sufficient to prove the general thesis.
The proof is divided into 3 steps, where we prove that the statement holds first when a is continuous, then when a is Riemann-integrable and eventually when a is continuous a.e..
Step 1. Suppose a is continuous and call \(\omega _a\) its continuity module. Notice that
so we can obtain a bound on the norm of \(I_{\varvec{n}}(a) - D_{\varvec{n}}(a)\) as
By Z1, \(\{I_{\varvec{n}}(a) - D_{\varvec{n}}(a) \}_n\) is zero-distributed and consequentially GLT4 tells us that \(\{ I_{{\varvec{n}}}(a) \}_n\sim _{GLT}a\).
Step 2. Suppose a is Riemann-integrable, and consider a sequence of continuous function \(a_m\) converging to a in \(L^1\) norm. A continuous function is in particular Riemann-integrable, so \(a_m-a\) is also Riemann-integrable and we can compute
We can thus write the difference as \(\Vert I_{{\varvec{n}}}(a_m)-I_{{\varvec{n}}}(a)\Vert _1 = N({\varvec{n}})\varepsilon (n,m)\) where \(\lim _{m\rightarrow \infty }\lim _{n\rightarrow \infty }\varepsilon (n,m)=0\) and using ACS 4, we discover that
We know from Step 1 that \(\{ I_{{\varvec{n}}}(a_m) \}_n\sim _{GLT}a_m\) for every m, and \(a_m\xrightarrow {m\rightarrow \infty } a\) in measure, so we conclude that \(\{ I_{{\varvec{n}}}(a) \}_n\sim _{GLT}a\) by GLT 7.
Step 3. Suppose a is continuous a.e and call \(a_m(x): = \max \{ a(x),m\}\) its truncated function for every \(m\in \mathbb N\). Notice that \(a_m\) are still continuous a.e. and also bounded, thus Riemann-integrable. Moreover, since a is measurable we know that
We know from Step 2 that \(\{ I_{{\varvec{n}}}(a_m) \}_n\sim _{GLT}a_m\) for every m, so we can fix \(1>\varepsilon >0\) and consider \(G_m(x)\) continuous and compact supported functions such that \(\upchi _{[0,m-\varepsilon ]}\le G_m\le \upchi _{[-\varepsilon ,m]}\) to obtain
Note that \(G_m(m)=0\), so \(G_m(a_m)=G_m(a)\) and taking the limits of the preceding relations, one can see that
Consequently, for every m we can find \(n_m\) such that for every \(n>n_m\), \({{\,\mathrm{rk}\,}}( I_{\varvec{n}}(a_m) - I_{\varvec{n}}(a) ) \le c(m) N({\varvec{n}})\) with \(c(m)\xrightarrow {m\rightarrow \infty } 0\), and it leads to
We know that \(a_m\xrightarrow {m\rightarrow \infty } a\) in measure, so we conclude again by GLT7 that \(\{ I_{{\varvec{n}}}(a) \}_n\sim _{GLT}a\). \(\square \)
This result shows that for every \(a:[0,1]^d\rightarrow \mathbb C\) continuous a.e. function, the sequences \(\{ I_{{\varvec{n}}}(a) \}_n\) and \(\{ D_{{\varvec{n}}}(a) \}_n\) have the same GLT (and consequently, spectral) symbol. In particular, if \(\Omega \) is Peano–Jordan measurable, \(\upchi _{\Omega }\) is continuous a.e., so \(\{ I_{{\varvec{n}}}(\upchi _\Omega ) \}_n\sim _{GLT}\upchi _\Omega \). In this case, it is also possible show that the difference \(I_{{\varvec{n}}}(\upchi _\Omega ) -D_{{\varvec{n}}}(\upchi _\Omega )\) has rank negligible when compared to \(N({\varvec{n}})\).
Lemma 3.4
If \(\Omega \) is Peano–Jordan measurable, then
Proof
It is enough to show that
has cardinality negligible when compared to \(N({\varvec{n}})\), since
Note that if \({\varvec{i}}\in E_n\) then there’s a point of the boundary \(\partial \Omega \) on the segment connecting the points \({\varvec{i}}/{\varvec{n}}\) and \({\varvec{i}}/({\varvec{n}}+{\varvec{1}})\). The distance between the two points is always bounded and tends to zero when n goes to infinity
It means that for every \({\varvec{i}}\in E_n\) we have \(d({\varvec{i}}/{\varvec{n}},\partial \Omega )\le h_n\), so Lemma 3.2 let us conclude that
\(\square \)
The latest result shows that the two diagonal sequences \( \{ I_{{\varvec{n}}}(\upchi _\Omega ) \}_n\) and \( \{ D_{\varvec{n}}(\upchi _\Omega ) \}_n\) hold essentially the same information about the domain \(\Omega \). The first one will be fundamental to operate on the grid \(\Xi _n\) through diagonal matrices, and also the quantity
counts the number of grid points inside \(\Omega \). As a corollary, we find again the same results of Lemmas 3.1 and 3.2, referred to the sequence \( \{ I_{{\varvec{n}}}(\upchi _\Omega ) \}_n\). We will not prove them, since the arguments are the same we used in the proofs of Lemmas 3.1 and 3.2.
Corollary 3.1
If \(\Omega \) is a Peano–Jordan measurable set, then
Corollary 3.2
Given a sequence \(h_n\) of real nonnegative numbers converging to zero, and a Peano–Jordan measurable set \(\Omega \), then
In particular, if \(\mu (\Omega ) >0\), then
Note that if \(h_n=0\) for every n, we have \(K_{h_n} = K_0=\partial \Omega \) for every n, so \(d_n^{\partial \Omega } = o(d_n^\Omega ) = o(N({\varvec{n}}))\). As a corollary, we can also derive the limits of \(d_n^{\overline{\Omega }}(N({\varvec{n}}))^{-1}\) and \(d_n^{\Omega ^\circ }(N({\varvec{n}}))^{-1}\), since we know that \(\overline{\Omega }\) and \(\Omega ^\circ \) differ from \(\Omega \) for a negligible set inside \(\partial \Omega \).
Notice that Corollary 3.1 shows \(\lim _{n\rightarrow \infty } d^\Omega _n = +\infty \) whenever the measure of \(\Omega \) is not zero, so from now on, we suppose that \(\mu (\Omega )>0\).
4 Restriction and expansion operators
If we fix a Peano–Jordan measurable set \(\Omega \), then we can build the map
From now on, we abuse the notation and write \(Z_\Omega (A_{\varvec{n}})\) for the matrix \(I_{{\varvec{n}}}(\upchi _\Omega ) A_{{\varvec{n}}}I_{{\varvec{n}}}(\upchi _\Omega ) \). If we call \(\mathscr {G}_d\) the set of d-dimensional GLT sequences, notice that \(Z_\Omega (\mathscr {G}_d)\subseteq \mathscr {G}_d\) by GLT4, since it multiplies a GLT sequence with other GLT sequences, as shown in Lemma 3.4. Some properties of this operation are
-
\(Z_\Omega \) is linear,
-
\(Z_\Omega \) is idempotent,
-
if \(\{A_{{\varvec{n}}}\}_n\sim _{GLT}k(x,\theta )\), then \(Z_\Omega (\{A_{{\varvec{n}}}\}_n)\sim _{GLT}k(x,\theta )\upchi _\Omega (x)\),
-
if \(\{A_{{\varvec{n}}}\}_n\) is a real sequence, then \(Z_\Omega (\{A_{{\varvec{n}}}\}_n)\) is still real,
-
if \(\{A_{{\varvec{n}}}\}_n\) is a Hermitian sequence, then \(Z_\Omega (\{A_{{\varvec{n}}}\}_n)\) is still Hermitian.
If we associate each multi-index \(\varvec{i}\) in the matrix \(A_{{\varvec{n}}}\) to the point \(\frac{\varvec{i}}{\varvec{n}+{\varvec{1}}}\in \Xi _n\), then \(Z_\Omega \) sets to zero every row and column corresponding to a point not in \(\Omega \). We can thus try to delete the zero rows and columns in the matrices, and obtain a matrix with size \(d_n^\Omega \times d_n^\Omega \).
Given a set \(\Omega \) with negligible boundary, we consider \(I_{{\varvec{n}}}(\upchi _\Omega ) \) and we enumerate the non-zero rows and the zero rows through two strictly increasing functions
such that the \(\phi _{{\varvec{n}}}(j)\)-th row of \(I_{{\varvec{n}}}(\upchi _\Omega ) \) is non-zero for every j, and the \(\psi _{{\varvec{n}}}(j)\)-th row of \(I_{{\varvec{n}}}(\upchi _\Omega ) \) is zero for every j. In particular, the images of \(\phi _{\varvec{n}}\) and \(\psi _{\varvec{n}}\) correspond to the set of points \({\varvec{i}}/({\varvec{n}}+{\varvec{1}})\) in \(\Xi _n\) respectively belonging and not belonging to \(\Omega \). Notice that \(\phi _{\varvec{n}}\) and \(\psi _{\varvec{n}}\) are uniquely determined by their properties.
For every \({\varvec{n}}\), we define a rectangular matrix \(\Pi _{{\varvec{n}},\Omega }\) of size \(d_n^\Omega \times N({\varvec{n}})\) as
so that, for any matrix \(A_{\varvec{n}}\) of size \(N({\varvec{n}})\times N({\varvec{n}})\), we can delete the rows and columns corresponding to points not belonging to \(\Omega \) through the restriction map
and add zero rows and columns corresponding to points not belonging to \(\Omega \) to any matrix \(S_{\varvec{n}}^\Omega \) of size \(d_n^\Omega \times d_n^\Omega \) through the expansion map
We will use the notation \(R_\Omega (A_{\varvec{n}})\) for \(\Pi _{{\varvec{n}},\Omega } A_{{\varvec{n}}}(\Pi _{{\varvec{n}},\Omega })^T \) and the notation \(E_\Omega (S^\Omega _{\varvec{n}})\) for \((\Pi _{{\varvec{n}},\Omega })^TS^\Omega _{\varvec{n}}\Pi _{{\varvec{n}},\Omega }\). Moreover, unless differently specified, we use the exponent \(\Omega \) to distinguish the sequences \(\{S^\Omega _{{\varvec{n}}}\}_n\) of size \(d_n^\Omega \times d_n^\Omega \) from classical sequences \(\{A_{{\varvec{n}}}\}_n\) of size \(N({\varvec{n}})\times N({\varvec{n}})\).
Remark 4.1
Note that the operators \(E_\Omega ,R_\Omega ,Z_\Omega \), the matrices \(\Pi _{{\varvec{n}},\Omega }, I_{{\varvec{n}}}(\upchi _\Omega ) \) and the quantity \(d_n^\Omega \) can be defined for any measurable set \(\Omega \), even if not Peano–Jordan measurable.
4.1 Effects on the sequences
Let us check some basic properties of the matrices \(\Pi _{{\varvec{n}},\Omega }, I_{{\varvec{n}}}(\upchi _\Omega ) \) and the operators \(E_\Omega ,R_\Omega ,Z_\Omega \).
Lemma 4.1
For every index \({\varvec{n}}\), we have
-
1.
\((\Pi _{{\varvec{n}},\Omega })^T\Pi _{{\varvec{n}},\Omega } = I_{{\varvec{n}}}(\upchi _\Omega ) \),
-
2.
\( \Pi _{{\varvec{n}},\Omega }(\Pi _{{\varvec{n}},\Omega })^T = I_{\varvec{n}}^\Omega \).
In particular, given any matrix \(A_{\varvec{n}}\) of size \(N({\varvec{n}})\times N({\varvec{n}})\), and any matrix \(S^\Omega _{\varvec{n}}\) of size \(d_n^\Omega \times d_n^\Omega \), we have
-
3.
\(R_\Omega (A_{{\varvec{n}}}) = R_\Omega \circ Z_\Omega (A_{{\varvec{n}}})\),
-
4.
\(R_\Omega (E_\Omega (S^\Omega _{\varvec{n}})) = S^\Omega _{\varvec{n}}\),
-
5.
\(E_\Omega (R_\Omega (A_{{\varvec{n}}})) = Z_\Omega (A_{{\varvec{n}}})\),
-
6.
\(Z_\Omega (E_\Omega (S^\Omega _{\varvec{n}})) = E_\Omega (S^\Omega _{\varvec{n}})\).
Moreover \((E_\Omega (S^\Omega _{\varvec{n}}))^* = E_\Omega ((S^\Omega _{\varvec{n}})^*)\) and \((R_\Omega (A_{\varvec{n}}))^* = R_\Omega (A^*_{\varvec{n}})\), so
-
7.
\(S^\Omega _{\varvec{n}}\) Hermitian \(\implies E_\Omega (S^\Omega _{\varvec{n}})\) Hermitian,
-
8.
\(A_{\varvec{n}}\) Hermitian \(\implies R_\Omega (A_{\varvec{n}})\) Hermitian.
Proof
For items 1. and 2. we need to prove that the matrix multiplications returns diagonal matrices, with 0 or 1 diagonal elements.
Using now 1. and 2., let us prove items 3., 4. and 5. as follows.
Item 6. is now a consequence of items 4. and 5. as
and eventually the last two items are straightforward computations of the Hermitian transpose of the respective matrices.
\(\square \)
The operator \(R_\Omega \) has the job to extract a principal minor from the matrices, so it is easy to see that it makes the norm drop.
Lemma 4.2
For every \(1\le p\le \infty \),
where \(\Vert \cdot \Vert _p\) is the p-Schatten norm.
Proof
The matrices \(\Pi _{{\varvec{n}},\Omega }\) are unitary, so we can apply the Cauchy interlacing theorem and find that
The thesis easily follows from the definition of p-Schatten norm. \(\square \)
The map \(R_\Omega \) applied to \(Z_\Omega (A_{{\varvec{n}}})\) has the effect to delete only rows and columns that are already zero, and we can easily tell the behaviour of their singular values and eigenvalues.
Lemma 4.3
There exists a permutation matrix P of size \(N({\varvec{n}})\times N({\varvec{n}})\) such that for every matrix \(A_{\varvec{n}}\) of size \(N({\varvec{n}})\times N({\varvec{n}})\),
In particular, \( Z_\Omega (A_{\varvec{n}})\) has the same eigenvalues and singular values of the matrix \(R_\Omega (A_{\varvec{n}})\) except for \(N({\varvec{n}}) - d_n^\Omega \) null eigenvalues and singular values.
Proof
Let \(B_{\varvec{n}}= Z_\Omega (A_{\varvec{n}})\) and \(S^\Omega _{\varvec{n}}=R_\Omega (A_{\varvec{n}})\). If we define the permutation matrix P as
then the matrix \(P B_{\varvec{n}}P^T\) can be written as
In fact
whose expression depends on whether \(|{\varvec{i}}|, |{\varvec{j}}|\) are grater or less than \(d_n^\Omega \). In fact, if \(|{\varvec{i}}|\le d_n^\Omega , |{\varvec{j}}|\le d_n^\Omega \), then
if \(|{\varvec{i}}|> d_n^\Omega ,|{\varvec{j}}|\le d_n^\Omega \), then
if \(|{\varvec{i}}|\le d_n^\Omega ,|{\varvec{j}}|> d_n^\Omega \), then
and if \(|{\varvec{i}}|> d_n^\Omega ,|{\varvec{j}}|> d_n^\Omega \), then
Moreover,
The proof is thus concluded, since \(S^\Omega _{\varvec{n}}\) has the same eigenvalues and singular values of \(B_{\varvec{n}}\) except for \(N({\varvec{n}}) -d_n^\Omega \) zeros. \(\square \)
Corollary 4.1
There exists a permutation matrix P of size \(N({\varvec{n}})\times N({\varvec{n}})\) such that for every matrix \(S^\Omega _{\varvec{n}}\) of size \(d_n^\Omega \times d_n^\Omega \),
In particular, \(E_\Omega (S^\Omega _{\varvec{n}})\) has the same eigenvalues and singular values of the matrix \(S^\Omega _{\varvec{n}}\) except for \(N({\varvec{n}}) - d_n^\Omega \) null eigenvalues and singular values.
Proof
Let \(A_{\varvec{n}}= E_\Omega (S^\Omega _{\varvec{n}})\). Using items 4. and 6. of Lemma 4.1, we get
As a consequence, we can apply Lemma 4.3 on \( A_{\varvec{n}}\) to find a permutation matrix P such that
so \(S^\Omega _{\varvec{n}}\) has the same eigenvalues and singular values of \(A_{\varvec{n}}\) except for \(N({\varvec{n}}) -d_n^\Omega \) zeros.
\(\square \)
Corollary 4.2
There exists a permutation matrix P of size \(N({\varvec{n}})\times N({\varvec{n}})\) such that for every matrix \(A_{\varvec{n}}\) of size \(N({\varvec{n}})\times N({\varvec{n}})\),
Proof
Using items 1. and 2. of Lemma 4.1,
so Lemma 4.3 shows that there exists P such that
As a consequence, we have that
\(\square \)
4.2 Effects on the symbols
We have seen how \(R_\Omega ,E_\Omega \) modify the sequences of matrices. Now we focus on how the symbols change though these operators. Let us start with the reduction operator \(R_\Omega \).
Lemma 4.4
Let \(\{A_{\varvec{n}}\}_n\) be a sequence with \(A_{\varvec{n}}\) of size \(N({\varvec{n}})\times N({\varvec{n}})\) that is a fixed point for the operator \(Z_\Omega \), and let \(k:[0,1]^d\times [-\pi ,\pi ]^d\rightarrow \mathbb C\) be a measurable function with \(k(x,\theta )|_{x\not \in \Omega } = 0\). If \(\{A_{{\varvec{n}}}\}_n\sim _\sigma k\), then
If \(\{A_{{\varvec{n}}}\}_n\sim _\lambda k\), then
Proof
Suppose that \(\{A_{{\varvec{n}}}\}_n\sim _\sigma k\). Consider any continuous function \(F:\mathbb R\rightarrow \mathbb C\) with compact support, and call \(S^\Omega _{\varvec{n}}=R_\Omega ( A_{\varvec{n}})\). By hypothesis \( A_{\varvec{n}}=Z_\Omega (A_{\varvec{n}})\), so we can use Lemma 4.3 and obtain
Notice that \(\{A_{{\varvec{n}}}\}_n\sim _\sigma k(x,\theta ) = k(x,\theta )\upchi _\Omega (x)\), so Corollary 3.1 shows that
The last formula holds for every continuous function F with compact support, so
If we suppose \(\{A_{{\varvec{n}}}\}_n\sim _\lambda k\), the proof is analogous. Consider any continuous and compact supported function \(F:\mathbb C\rightarrow \mathbb C\) and use Lemma 4.3 to show that
and exploiting \(\{B_{{\varvec{n}}}\}_n\sim _\lambda k(x,\theta ) = k(x,\theta )\upchi _\Omega (x)\) and Corollary 3.1, we conclude that
The last formula holds for every continuous function F with compact support, so
\(\square \)
On the contrary let us analyse the effects of the extension operator \(E_\Omega \).
Lemma 4.5
Let \(\{S^\Omega _{\varvec{n}}\}_n\) be a sequence with \(S^\Omega _{\varvec{n}}\) of size \(d_n^\Omega \times d_n^\Omega \), let \(\kappa :\Omega \times [-\pi ,\pi ]^d\rightarrow \mathbb C\) be a measurable function, and define
If \(\{S^\Omega _{{\varvec{n}}}\}_n\sim _\sigma k\), then
If \(\{S^\Omega _{{\varvec{n}}}\}_n\sim _\lambda \kappa \), then
Proof
Suppose that \(\{S^\Omega _{{\varvec{n}}}\}_n\sim _\sigma \kappa \), and denote \(\{A_{{\varvec{n}}}\}_n=E_\Omega (\{S^\Omega _{{\varvec{n}}}\}_n)\). If we consider any continuous function \(F:\mathbb R\rightarrow \mathbb C\) with compact support, then we can use Corollary 4.1 on \(\{S^\Omega _{{\varvec{n}}}\}_n\) to obtain
As a consequence of Corollary 3.1, we can show that
where \((2\pi )^d = \mu ([0,1]^d\times [-\pi ,\pi ]^d)\). The last formula holds for every continuous function F with compact support, so
If we suppose \(\{S^\Omega _{{\varvec{n}}}\}_n\sim _\lambda \kappa \), the proof is analogous. If we consider any continuous function \(F:\mathbb C\rightarrow \mathbb C\) with compact support, then we can use Corollary 4.1 on \(\{S^\Omega _{{\varvec{n}}}\}_n\) to obtain
As a consequence of Corollary 3.1, we can show that
The last formula holds for every continuous function F with compact support, so
\(\square \)
4.3 Effects on the convergence
When dealing with the space of matrix sequences, we already know that it is a complete pseudometric space, equipped with the a.c.s. convergence and the distance
The operators \(R_\Omega \) and \(E_\Omega \) link two different matrix sequence spaces, so we can analyse how they affect the metrics and the convergences.
Lemma 4.6
Given a sequence \(\{S^\Omega _{{\varvec{n}}}\}_n\) with \(S^\Omega _{\varvec{n}}\) of size \(d_n^\Omega \times d_n^\Omega \) and a sequence \(\{A_{{\varvec{n}}}\}_n\) with \(A_{\varvec{n}}\) of size \(N({\varvec{n}})\times N({\varvec{n}})\), we have
Proof
Easy corollary of Lemmas 4.5 and 4.4. \(\square \)
Lemma 4.7
Given two sequences \(\{A_{{\varvec{n}}}\}_n\) and \(\{B_{{\varvec{n}}}\}_n\) with matrices of size \(N({\varvec{n}})\times N({\varvec{n}})\),
In particular,
Proof
Let P be the permutation matrix in Corollary 4.2, so that
Using the Cauchy interlacing theorem for singular values, we get that
for every \(1\le i\le d_n^\Omega \). We can thus use the definition of \(d_{acs}\) and Corollary 3.1 to obtain that \(d_\mathrm{a.c.s.}\left( \{A_{{\varvec{n}}}\}_n,\{B_{{\varvec{n}}}\}_n\right) \) is equal to
Consequentially,
\(\square \)
Lemma 4.8
Given two sequences \(\{A_{{\varvec{n}}}^\Omega \}_n\) and \(\{B_{{\varvec{n}}}^\Omega \}_n\) with matrices of size \(d_n^\Omega \times d_n^\Omega \),
In particular,
Proof
Thanks to item 4. of Lemma 4.1, we know that \(R_\Omega (E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n)) =\{A_{{\varvec{n}}}^\Omega \}_n\), and the same happens to \(\{B_{{\varvec{n}}}^\Omega \}_n\), so we can apply Lemma 4.7 and obtain
On the other hand, since \(Z_\Omega (E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n-\{B_{{\varvec{n}}}^\Omega \}_n)) = E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n-\{B_{{\varvec{n}}}^\Omega \}_n)\), Corollary 4.1 assures us that the singular values of \(\{A_{{\varvec{n}}}^\Omega \}_n-\{B_{{\varvec{n}}}^\Omega \}_n\) are the same of the singular values of \(E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n-\{B_{{\varvec{n}}}^\Omega \}_n)\) except \(N({\varvec{n}})-d_n^\Omega \) for zeros. Hence, \(d_\mathrm{a.c.s.}\left( E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n),E_\Omega (\{B_{{\varvec{n}}}^\Omega \}_n)\right) \) is equal to
Consequentially,
\(\square \)
4.4 Different grids
The operators \(Z_\Omega ,R_\Omega ,E_\Omega \) are always referred to a measurable set \(\Omega \) that tells us which rows and columns to add or remove from the matrices depending on the points of the regular grid \(\Xi _n\) inside \(\Omega \). Suppose now that we want to choose a slight different set of points for every n, and we ask whether the resulting sequence of matrices still enjoys a symbol. Remember that the symmetric difference \(\triangle \) between two sets is the set of elements belonging to only one of the two sets. In symbols, \(A\triangle B = (A\setminus B)\cup (B\setminus A)\).
Lemma 4.9
Let \(\Gamma _n\) be a measurable set in \([0,1]^d\) (not necessarily Peano–Jordan measurable) and let \(\Omega \) be a Peano–Jordan measurable set with positive measure in \([0,1]^d\). Suppose that
Given a sequence \(\{A_{\varvec{n}}\}_n\) with \(A_{\varvec{n}}\) of size \(N({\varvec{n}})\times N({\varvec{n}})\), and a measurable function k, we have that
Moreover, if \(A_{\varvec{n}}\) are Hermitian, then
Proof
Consider the difference
The matrix has at most \(d_n^{\Omega \setminus \Gamma _n}\le d_n^{\Omega \triangle \Gamma _n } = o(N({\varvec{n}}))\) non-zero rows and columns, and from Corollary 3.1, we infer also that \(d_n^{\Omega \setminus \Gamma _n} = o(d_n^\Omega )\). Consequently, \(d_n^{\Omega \setminus \Gamma _n} = o(d_n^{\Omega \cup \Gamma _n})\), so the sequence is zero-distributed. Moreover, the matrix \(B^{\Omega \cup \Gamma _n}_{\varvec{n}}:= R_{\Omega \cup \Gamma _n}(E_{\Omega } (R_{\Omega }(A_{\varvec{n}})))\) is actually \(R_{\Omega }(A_{\varvec{n}})\) with additional \(d_n^{\Gamma _n\setminus \Omega }\le d_n^{\Omega \triangle \Gamma _n } = o(N({\varvec{n}}))\) zero columns and rows, so we just added few zero singular values, for which holds again \(d_n^{ \Gamma _n\setminus \Omega } = o(d_n^{\Omega \cup \Gamma _n})\). In particular, if we consider any continuous function \(F:\mathbb C\rightarrow \mathbb C\) with compact support, then
and asymptotically we have
It leads to
and the same argument can be applied to \(R_{\Gamma _n}(A_{\varvec{n}})\), so we can conclude that
If \(A_{\varvec{n}}\) are hermitian, then all the matrices considered until now are also Hermitian, so the same results apply to the spectral symbols and
\(\square \)
This result is quite powerful since it tells us that we can add and remove a small number of rows and columns without changing the symbol of the sequence. It will be useful in applications when dealing with near-boundary conditions.
5 Reduced GLT
In the following propositions, we denote the image of \(R_\Omega \) when applied to GLT sequences as \(\mathscr {G}^\Omega _d := R_\Omega (\mathscr {G}_d)\), and we call it the space of reduced GLT with respect to \(\Omega \).
5.1 Reduced GLT symbol
Lemma 5.1
Given a GLT sequence \(\{A_{\varvec{n}}\}_n\sim _{GLT}k(x,\theta )\) with \(k:[0,1]^d\times [-\pi ,\pi ]^d\rightarrow \mathbb C\), then
If \(A_{\varvec{n}}\) are also Hermitian matrices, then
Proof
Thanks to item 3. of Lemma 4.1, we have \( R_\Omega (\{A_{{\varvec{n}}}\}_n) = R_\Omega (Z_\Omega (\{A_{{\varvec{n}}}\}_n)) \) and if we call \(\{B_{{\varvec{n}}}\}_n =Z_\Omega (\{A_{{\varvec{n}}}\}_n)\), then \(Z_\Omega (\{B_{{\varvec{n}}}\}_n)= \{B_{{\varvec{n}}}\}_n\) since \(Z_\Omega \) is an idempotent operator. Moreover, \(\{B_{{\varvec{n}}}\}_n\sim _{GLT}k(x,\theta )\upchi _\Omega (x)\), so in particular \(\{B_{{\varvec{n}}}\}_n\sim _\sigma k(x,\theta )\upchi _\Omega (x)\) due to GLT1. We can thus use Lemma 4.4 and obtain that
If \(A_{\varvec{n}}\) are Hermitian matrices, then also \(\{B_{{\varvec{n}}}\}_n=Z_\Omega (\{A_{{\varvec{n}}}\}_n)\) is a Hermitian sequence, since \(Z_\Omega \) preserves the Hermitianity, so
due to GLT1. As before, \(Z_\Omega (\{B_{{\varvec{n}}}\}_n)= \{B_{{\varvec{n}}}\}_n\) and Lemma 4.4 assure us that
\(\square \)
Notice that the map \(R_\Omega \) is not injective, but one can prove that all the GLT sequences with the same image have symbols that coincide on \(\Omega \times [-\pi ,\pi ]\).
Lemma 5.2
Given \(\{A_{{\varvec{n}}}\}_n\sim _{GLT}k\), \(\{B_{{\varvec{n}}}\}_n\sim _{GLT}h\) such that \(R_\Omega (\{A_{{\varvec{n}}}\}_n)=R_\Omega (\{B_{{\varvec{n}}}\}_n)= \{S^\Omega _{{\varvec{n}}}\}_n\in \mathscr {G}^\Omega _d\), the symbols k, h coincide on \(\Omega \times [-\pi ,\pi ]^d\).
Proof
Since \(R_\Omega \) is linear, we can use Lemma 5.1 and GLT4 and say that \(\{A_{{\varvec{n}}}\}_n -\{B_{{\varvec{n}}}\}_n\sim _{GLT}k-h \) implies
Notice that if the set where \(0<L<|\kappa |<M\) has non-zero measure, then we can consider a nonnegative continuous function \(F:\mathbb R\rightarrow \mathbb C\) with compact support such that \(F(0)=0\) and \(F(x)>\delta >0\) for every \(x\in (L,M)\) to get an absurd
We conclude that \(\kappa =0\), and so k, h coincide on \(\Omega \times [-\pi ,\pi ]^d\). \(\square \)
As a corollary, every GLT sequence mapped into \(\{S^\Omega _{{\varvec{n}}}\}_n\) possesses a symbol with a fixed value on \(\Omega \times [-\pi ,\pi ]^d\), so we can associate to each reduced GLT sequence \(\{S^\Omega _{{\varvec{n}}}\}_n\) an unique symbol, called reduced GLT symbol, obtained as the restriction of any GLT symbol of the sequences in the counter-image \(R_\Omega ^{-1}(\{S^\Omega _{{\varvec{n}}}\}_n)\cap \mathscr {G}_d\). From now on, we will use the notation \(\{S^\Omega _{{\varvec{n}}}\}_n\sim _{GLT}^\Omega s\) to indicate that \(s:\Omega \times [-\pi ,\pi ]^d\rightarrow \mathbb C\) is the restriction of a symbol \(k:[0,1]^d\times [-\pi ,\pi ]^d\rightarrow \mathbb C\) such that \(\{A_{{\varvec{n}}}\}_n\sim _{GLT}k\) and \(R_\Omega (\{A_{{\varvec{n}}}\}_n)=\{S^\Omega _{{\varvec{n}}}\}_n\).
Given any reduced GLT sequence \(\{S^\Omega _{{\varvec{n}}}\}_n\), it is easy to produce a GLT sequence \(\{A_{{\varvec{n}}}\}_n\) such that \(R_\Omega (\{A_{{\varvec{n}}}\}_n)=\{S^\Omega _{{\varvec{n}}}\}_n\) using the operator \(E_\Omega \). We can thus reverse Lemma 5.1.
Lemma 5.3
If \(\{S^\Omega _{{\varvec{n}}}\}_n\sim _{GLT}^\Omega \kappa \), then
and \(R_\Omega (E_\Omega (\{S^\Omega _{{\varvec{n}}}\}_n))=\{S^\Omega _{{\varvec{n}}}\}_n\).
Proof
Since \(\{S^\Omega _{{\varvec{n}}}\}_n\in \mathscr {G}_d^\Omega = R_\Omega (\mathscr {G}_d)\), there exists a GLT sequence \(\{A_{{\varvec{n}}}\}_n\) with symbol h such that \(R_\Omega (\{A_{{\varvec{n}}}\}_n) = \{S^\Omega _{{\varvec{n}}}\}_n\), but thanks to item 3. of Lemma 4.1 we know that also \(R_\Omega (Z_\Omega (\{A_{{\varvec{n}}}\}_n)) =\{S^\Omega _{{\varvec{n}}}\}_n\) and
Using now item 5. of Lemma 4.1, we can conclude, since
\(\square \)
5.2 Axioms of reduced GLT
Using the connection between \(\mathscr {G}_d\) and \(\mathscr {G}_d^\Omega \), we can prove that many properties of the first space transfer to the second.
Theorem 5.1
Suppose \(\{A_{{\varvec{n}}}^\Omega \}_n\), \(\{B_{{\varvec{n}}}^\Omega \}_n\) are reduced GLT sequences and \(\{X_{{\varvec{n}}}^\Omega \}_n\) \(\{Y_{{\varvec{n}}}^\Omega \}_n\) are sequences with \(X^\Omega _{\varvec{n}},Y^\Omega _{\varvec{n}}\in \mathbb C^{d_n^\Omega \times d_n^\Omega }\).
-
GLT\(^\Omega \) 1. If \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) then \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{\sigma }\kappa \). If \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and each \(A^\Omega _{\varvec{n}}\) is Hermitian then \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{\lambda }\kappa \).
-
GLT\(^\Omega \) 2. If \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and \(\{A_{{\varvec{n}}}^\Omega \}_n=\{X_{{\varvec{n}}}^\Omega \}_n+\{Y_{{\varvec{n}}}^\Omega \}_n\), where
-
every \(X^\Omega _{\varvec{n}}\) is Hermitian,
-
\((d_n^\Omega )^{-1}\Vert Y^\Omega _{\varvec{n}}\Vert _2^2\rightarrow 0\),
then \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{\lambda }\kappa \).
-
-
GLT\(^\Omega \) 3. Here we list three important examples of reduced GLT sequences.
-
Given a function f in \(L^1([-\pi ,\pi ]^d)\), its associated reduced Toeplitz sequence is \(\{ T^\Omega _{\varvec{n}}(f)\}_n= R_\Omega (\{T_{\varvec{n}}(f)\}_n)\), where the elements are multidimensional Fourier coefficients of f:
$$\begin{aligned} T_{\varvec{n}}( f ) = [ f_{{\varvec{i}}-{\varvec{j}}} ]^{\varvec{n}}_{{\varvec{i}}, {\varvec{j}}={\varvec{1}}}, \qquad f_{\varvec{k}} = \frac{1}{(2\pi )^d} \int _{-\pi }^{\pi } f(\theta ) e^{-\text {i} \varvec{k}\cdot \theta } d\theta . \end{aligned}$$\(\{ T^\Omega _{\varvec{n}}(f)\}_n\) is a reduced GLT sequence with symbol \(\kappa ( x,\theta )=f(\theta )\).
-
Given an almost everywhere continuous function, \(\widetilde{a}:[0,1]^d\rightarrow \mathbb C\) and its restriction \(a=\widetilde{a}|_{\Omega }\), its associated diagonal sampling sequence \(\{D_{\varvec{n}}^\Omega (a)\}_n\) is defined as
$$\begin{aligned} D_{\varvec{n}}^\Omega (a) = \text {diag}\left( \left\{ a\left( \frac{\phi (i)}{{\varvec{n}}+{\varvec{1}}}\right) \right\} _{i=1}^{d_n^\Omega }\right) . \end{aligned}$$\(\{D_{\varvec{n}}^\Omega (a)\}_n\) is a reduced GLT sequence with symbol \(\kappa ( x,\theta )=a( x)\).
-
Any zero-distributed sequence \(\{Y^\Omega _{\varvec{n}}\}_n\sim _\sigma 0\) is a reduced GLT sequence with symbol \(\kappa ( x,\theta )=0\).
-
-
GLT\(^\Omega \) 4. If \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and \(\{B_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \xi \), then
-
\(\{ (A_{\varvec{n}}^\Omega )^*\}_n\sim _{GLT}^\Omega {{\overline{\kappa }}}\), where \((A^\Omega _{\varvec{n}})^*\) is the conjugate transpose of \(A^\Omega _{\varvec{n}}\),
-
\(\{\alpha A^\Omega _{\varvec{n}}+\beta B^\Omega _{\varvec{n}}\}_n\sim _{GLT}^\Omega \alpha \kappa +\beta \xi \) for all \(\alpha ,\beta \in \mathbb C\),
-
\(\{A^\Omega _{\varvec{n}}B^\Omega _{\varvec{n}}\}_n\sim _{GLT}^\Omega \kappa \xi \).
-
-
GLT\(^\Omega \) 5. If \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and \(\kappa \ne 0\) a.e., then \(\{(A_{\varvec{n}}^\Omega )^\dag \}_n\sim _{GLT}^\Omega \kappa ^{-1}\), where \((A^\Omega _{\varvec{n}})^\dag \) is the Moore–Penrose pseudoinverse of \(A_{\varvec{n}}^\Omega \).
-
GLT\(^\Omega \) 6. If \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and each \(A_{\varvec{n}}^\Omega \) is Hermitian, then \(\{f(A^\Omega _{\varvec{n}})\}_n\sim _{GLT}^\Omega f(\kappa )\) for all continuous functions \(f:\mathbb C\rightarrow \mathbb C\).
-
GLT\(^\Omega \) 7. \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) if and only if there exist GLT sequences \(\{B_{{\varvec{n}},m}\}_n\) with reduced symbols \(\kappa _m\) such that \(\kappa _m\) converges to \(\kappa \) in measure and \(\{B_{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}\{A_{{\varvec{n}}}^\Omega \}_n\) as \(m\rightarrow \infty \).
-
GLT\(^\Omega \) 8. Suppose \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and \(\{B^\Omega _{{\varvec{n}},m}\}_n\sim _{GLT}^\Omega \kappa _m\), where both \(A^\Omega _{\varvec{n}}\) and \(B^\Omega _{{\varvec{n}},m}\) have the same size \(d_n^\Omega \times d_n^\Omega \). Then, \(\{B^\Omega _{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}\{A_{{\varvec{n}}}^\Omega \}_n\) as \(m\rightarrow \infty \) if and only if \(\kappa _m\) converges to \(\kappa \) in measure.
-
GLT\(^\Omega \) 9. If \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) then there exist functions \(a_{i,m},f_{i,m}\), with \(i=1,\ldots ,N_m\), such that
-
\(a_{i,m}\in C^\infty (\Omega )\) and \(f_{i,m}\) is a trigonometric polynomial,
-
\(\sum _{i=1}^{N_m}a_{i,m}(x)f_{i,m}(\theta )\) converges to \(\kappa (x,\theta )\) a.e.,
-
\(\bigl \{\sum _{i=1}^{N_m}D_{\varvec{n}}^\Omega (a_{i,m})T_{{\varvec{n}}}^\Omega (f_{i,m})\bigr \}_n\xrightarrow {\mathrm{a.c.s.}}\{A_{{\varvec{n}}}^\Omega \}_n\) as \(m\rightarrow \infty \).
-
Proof
Given \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \), \(\{B_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \xi \), call
where \(\kappa '\) and \(\xi '\) are the extension of \(\kappa \) and \(\xi \) as specified in Lemma 5.3. We know that \(\kappa '|_{x\in \Omega } =\kappa \), \(\xi '|_{x\in \Omega } =\xi \) and \(R_\Omega (\{A_{{\varvec{n}}}\}_n)=\{A_{{\varvec{n}}}^\Omega \}_n\), \(R_\Omega (\{B_{{\varvec{n}}}\}_n)=\{B_{{\varvec{n}}}^\Omega \}_n\). Notice that in every proof we use the axioms GLT1-9 referred to the regular multilevel GLT.
-
GLT\(^\Omega \) 1. Using Lemma 5.1, we know that \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{\sigma }\kappa '|_{x\in \Omega } =\kappa \). If \(\{A_{{\varvec{n}}}^\Omega \}_n\) is Hermitian, then \(\{A_{{\varvec{n}}}\}_n\) is Hermitian by item 7. of Lemma 4.1, so Lemma 5.1 let us conclude that \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{\lambda }\kappa '|_{x\in \Omega } =\kappa \).
-
GLT \(^\Omega \) 2. Let \(\{X_{{\varvec{n}}}\}_n=E_\Omega (\{X_{{\varvec{n}}}^\Omega \}_n)\) and \(\{Y_{{\varvec{n}}}\}_n=E_\Omega (\{Y_{{\varvec{n}}}^\Omega \}_n)\). The operator \(E_\Omega \) is linear, so \(\{ A_{{\varvec{n}}}\}_n = \{X_{{\varvec{n}}}\}_n+\{Y_{{\varvec{n}}}\}_n\), where \(\{A_{{\varvec{n}}}\}_n\sim _{GLT}\kappa '\). Using Corollary 4.1, we know that the singular values of \(Y_{\varvec{n}}\) are the same of \(Y^\Omega _{\varvec{n}}\) except for zero singular values. As a consequence,
$$\begin{aligned} \lim _{n\rightarrow \infty }(N({\varvec{n}}))^{-1}\Vert Y_{\varvec{n}}\Vert _2^2 = \lim _{n\rightarrow \infty }\frac{d_n^\Omega }{N({\varvec{n}})}(d_n^\Omega )^{-1}\Vert Y^\Omega _{\varvec{n}}\Vert _2^2 = \mu (\Omega )\cdot 0=0. \end{aligned}$$We can thus assert that \(\{A_{{\varvec{n}}}\}_n\sim _\lambda \kappa '\). Since we know that \(\kappa '|_{x\not \in \Omega } = 0\) and \(R_\Omega (\{A_{{\varvec{n}}}\}_n)=\{A_{{\varvec{n}}}^\Omega \}_n\), we can apply Lemma 4.4 and conclude that
$$\begin{aligned} \{A_{{\varvec{n}}}^\Omega \}_n=R_\Omega (\{A_{{\varvec{n}}}\}_n)\sim _\lambda \kappa '|_{x\in \Omega } = \kappa . \end{aligned}$$ -
GLT\(^\Omega \) 3. We know that \(\{T_{\varvec{n}}(f)\}_n\sim _{GLT}f\), so Lemma 5.1 assures us that
$$\begin{aligned} \{ T^\Omega _{\varvec{n}}(f)\}_n= R_\Omega (\{T_{\varvec{n}}(f)\}_n)\sim _{GLT}^\Omega f(\theta ).\end{aligned}$$Analogously, Lemma 3.3 shows that \(\{I_{\varvec{n}}(\widetilde{a}) \}_n\sim _{GLT}\widetilde{a}\) and it is easy to check that \(\{D_{\varvec{n}}^\Omega (a) \}_n = R_\Omega (\{I_{\varvec{n}}(\widetilde{a}) \}_n)\), so
$$\begin{aligned} \{D_{\varvec{n}}^\Omega (a) \}_n \sim _{GLT}^\Omega a. \end{aligned}$$Moreover, Lemma 4.6, shows that
$$\begin{aligned} \{Y_{{\varvec{n}}}^\Omega \}_n\sim _\sigma 0&\implies E_\Omega (\{Y_{{\varvec{n}}}^\Omega \}_n)\sim _\sigma 0 \implies E_\Omega (\{Y_{{\varvec{n}}}^\Omega \}_n)\sim _{GLT}0\\&\implies \{Y_{{\varvec{n}}}^\Omega \}_n = R_\Omega (E_\Omega (\{Y_{{\varvec{n}}}^\Omega \}_n))\sim _{GLT}^\Omega 0. \end{aligned}$$ -
GLT\(^\Omega \) 4. Using Lemmas 4.1 and 5.1, we know that
$$\begin{aligned} \{(A_{\varvec{n}}^\Omega )^*\}_n = (R_\Omega (\{A_{{\varvec{n}}}\}_n))^*= R_\Omega (\{A^*_{{\varvec{n}}}\}_n)\sim _{GLT}^\Omega \overline{\kappa }'|_{x\in \Omega } =\overline{\kappa }. \end{aligned}$$Moreover, \(R_\Omega \) is linear, so we can apply Lemma 5.1 on \(\alpha \{A_{{\varvec{n}}}\}_n +\beta \{B_{{\varvec{n}}}\}_n \sim _{GLT}\alpha \kappa '+\beta \xi '\) and obtain
$$\begin{aligned} \{\alpha A^\Omega _{\varvec{n}}+\beta B^\Omega _{\varvec{n}}\}_n = R_\Omega (\alpha \{A_{{\varvec{n}}}\}_n +\beta \{B_{{\varvec{n}}}\}_n) \sim _{GLT}^\Omega \alpha \kappa '+\beta \xi '|_{x\in \Omega } = \alpha \kappa +\beta \xi . \end{aligned}$$In order to prove the last point, remember that \(Z_\Omega (A_{\varvec{n}})=A_{\varvec{n}}\), so we can use item 1. of Lemma 4.1 and obtain the relation
$$\begin{aligned} R_\Omega (A_{{\varvec{n}}}B_{\varvec{n}})&= \Pi _{{\varvec{n}},\Omega } A_{{\varvec{n}}}B_{\varvec{n}}(\Pi _{{\varvec{n}},\Omega })^T \\&= \Pi _{{\varvec{n}},\Omega } I_{\varvec{n}}(\upchi _\Omega ) A_{{\varvec{n}}}I_{\varvec{n}}(\upchi _\Omega ) B_{\varvec{n}}(\Pi _{{\varvec{n}},\Omega })^T \\&= \Pi _{{\varvec{n}},\Omega } I_{\varvec{n}}(\upchi _\Omega ) A_{{\varvec{n}}}(I_{\varvec{n}}(\upchi _\Omega ))^2 B_{\varvec{n}}(\Pi _{{\varvec{n}},\Omega })^T\\&= \Pi _{{\varvec{n}},\Omega } A_{{\varvec{n}}}I_{\varvec{n}}(\upchi _\Omega ) B_{\varvec{n}}(\Pi _{{\varvec{n}},\Omega })^T\\&= \Pi _{{\varvec{n}},\Omega } A_{{\varvec{n}}}(\Pi _{{\varvec{n}},\Omega })^T\Pi _{{\varvec{n}},\Omega } B_{\varvec{n}}(\Pi _{{\varvec{n}},\Omega })^T\\&= R_\Omega (A_{{\varvec{n}}})R_\Omega (B_{\varvec{n}}). \end{aligned}$$Using Lemma 5.1, we conclude that
$$\begin{aligned} \{A_{{\varvec{n}}}^\Omega \}_n\{B_{{\varvec{n}}}^\Omega \}_n&= R_\Omega (\{A_{{\varvec{n}}}\}_n)R_\Omega (\{B_{{\varvec{n}}}\}_n) \\ {}&= R_\Omega (\{A_{{\varvec{n}}}\}_n\{B_{{\varvec{n}}}\}_n) \\ {}&\sim _{GLT}^\Omega \kappa '\xi '|_{x\in \Omega } = \kappa \xi . \end{aligned}$$ -
GLT\(^\Omega \) 5. Notice that \(\partial \Omega =\partial (\Omega ^C)\), so \(\{I_{\varvec{n}}(\upchi _{\Omega ^C}) \}_n\sim _{GLT}\upchi _{\Omega ^C}\) by Lemma 3.3. If we define \(\{C_{{\varvec{n}}}\}_n = \{A_{{\varvec{n}}}\}_n + \{I_{\varvec{n}}(\upchi _{\Omega ^C}) \}_n\), then
$$\begin{aligned} \{C_{{\varvec{n}}}\}_n\sim _{GLT}\kappa '(x,\theta ) + \upchi _{\Omega ^C}(x)= {\left\{ \begin{array}{ll} \kappa &{} x\in \Omega ,\\ 1 &{} x \not \in \Omega , \end{array}\right. } \end{aligned}$$so \(\kappa '(x,\theta ) + \upchi _{\Omega ^C}(x) = 0\) if and only if \(x\in \Omega \) and \(\kappa (x,\theta ) =0\). In particular it is different from zero a.e., so
$$\begin{aligned} \{C^\dag _{{\varvec{n}}}\}_n\sim _{GLT}(\kappa '(x,\theta ) + \upchi _{\Omega ^C}(x))^{-1}= {\left\{ \begin{array}{ll} \kappa ^{-1} &{} x\in \Omega ,\\ 1 &{} x \not \in \Omega . \end{array}\right. } \end{aligned}$$We know that \(Z_\Omega (\{A_{{\varvec{n}}}\}_n)=\{A_{{\varvec{n}}}\}_n\) and using items 1. and 2. of Lemma 4.1,
$$\begin{aligned} Z_\Omega (I_{\varvec{n}}(\upchi _{\Omega }))&= I_{\varvec{n}}(\upchi _{\Omega })I_{\varvec{n}}(\upchi _{\Omega })I_{\varvec{n}}(\upchi _{\Omega })=I_{\varvec{n}}(\upchi _{\Omega }), \\ R_\Omega (I_{\varvec{n}}(\upchi _{\Omega }))&= \Pi _{{\varvec{n}},\Omega } I_{\varvec{n}}(\upchi _{\Omega })(\Pi _{{\varvec{n}},\Omega })^T\\ {}&= \Pi _{{\varvec{n}},\Omega }(\Pi _{{\varvec{n}},\Omega })^T\Pi _{{\varvec{n}},\Omega }(\Pi _{{\varvec{n}},\Omega })^T\\ {}&= I_{\varvec{n}}^\Omega I_{\varvec{n}}^\Omega = I_{\varvec{n}}^\Omega . \end{aligned}$$Let P be the permutation matrix in Lemma 4.3, so that
$$\begin{aligned} PA_{\varvec{n}}P^T= \begin{pmatrix} A_{\varvec{n}}^\Omega &{}0\\ 0&{}0 \end{pmatrix}, \end{aligned}$$$$\begin{aligned} PI_{\varvec{n}}(\upchi _{\Omega ^C})P^T = P(I_{\varvec{n}}- I_{\varvec{n}}(\upchi _{\Omega }))P^T = I_{\varvec{n}}- \begin{pmatrix} I_{\varvec{n}}^\Omega &{}0\\ 0&{}0 \end{pmatrix} = \begin{pmatrix} 0&{}0\\ 0&{} I_{\varvec{n}}^{\Omega ^C} \end{pmatrix}, \end{aligned}$$$$\begin{aligned} PC_{\varvec{n}}P^T = P(A_{\varvec{n}}+ I_{\varvec{n}}(\upchi _{\Omega ^C}))P^T= \begin{pmatrix} A_{\varvec{n}}^\Omega &{}0\\ 0&{}I_{\varvec{n}}^{\Omega ^C} \end{pmatrix} \end{aligned}$$$$\begin{aligned}\implies PC_{\varvec{n}}^\dag P^T = \begin{pmatrix} (A_{\varvec{n}}^\Omega )^\dag &{}0\\ 0&{}I_{\varvec{n}}^{\Omega ^C} \end{pmatrix}. \end{aligned}$$Consequentially,
$$\begin{aligned} \begin{pmatrix} R_\Omega (C^\dag _{\varvec{n}})&{}0\\ 0&{}0 \end{pmatrix}&= P Z_\Omega (C^\dag _{\varvec{n}}) P^T\\&= P I_{\varvec{n}}(\upchi _\Omega ) C_{\varvec{n}}^\dag I_{\varvec{n}}(\upchi _\Omega ) P^T\\&= P I_{\varvec{n}}(\upchi _\Omega ) P^T \begin{pmatrix} (A_{\varvec{n}}^\Omega )^\dag &{}0\\ 0&{}I_{\varvec{n}}^{\Omega ^C} \end{pmatrix} P I_{\varvec{n}}(\upchi _\Omega ) P^T\\&= \begin{pmatrix} I_{\varvec{n}}^\Omega &{}0\\ 0&{}0 \end{pmatrix} \begin{pmatrix} (A_{\varvec{n}}^\Omega )^\dag &{}0\\ 0&{}I_{\varvec{n}}^{\Omega ^C} \end{pmatrix} \begin{pmatrix} I_{\varvec{n}}^\Omega &{}0\\ 0&{}0 \end{pmatrix} \\&= \begin{pmatrix} (A_{\varvec{n}}^\Omega )^\dag &{}0\\ 0&{}0 \end{pmatrix} \end{aligned}$$and Lemma 5.1 let us conclude that
$$\begin{aligned} \{(A_{\varvec{n}}^\Omega )^\dag \}_n =R_\Omega (\{C^\dag _{{\varvec{n}}}\}_n)\sim _{GLT}^\Omega (\kappa '(x,\theta ) + \upchi _{\Omega ^C}(x))^{-1}|_{x\in \Omega } = \kappa ^{-1}. \end{aligned}$$ -
GLT\(^\Omega \) 6. If \(A^\Omega _{\varvec{n}}\) is Hermitian, then \(A_{\varvec{n}}=E_\Omega (A^\Omega _{\varvec{n}})\) is also Hermitian and \(\{A_{{\varvec{n}}}\}_n\sim _{GLT}\kappa '\), so
$$\begin{aligned} \{f(A_{\varvec{n}})\}_n\sim _{GLT}f(\kappa ') = {\left\{ \begin{array}{ll} f(\kappa (x,\theta )) &{} x\in \Omega ,\\ f(0) &{} x\not \in \Omega . \end{array}\right. } \end{aligned}$$Notice that, using Lemma 4.3,
$$\begin{aligned} Pf(A_{\varvec{n}}) P^T =f(PA_{\varvec{n}}P^T)= \begin{pmatrix} f(A^\Omega _{\varvec{n}})&{}0\\ 0&{}f(0)I_{\varvec{n}}^{\Omega ^C} \end{pmatrix}, \end{aligned}$$so one can prove that
$$\begin{aligned} \begin{pmatrix} R_\Omega (f(A_{\varvec{n}}))&{}0\\ 0&{}0 \end{pmatrix}&= P Z_\Omega (f(A_{\varvec{n}})) P^T\\&= P I_{\varvec{n}}(\upchi _\Omega ) f(A_{\varvec{n}}) I_{\varvec{n}}(\upchi _\Omega ) P^T\\&= P I_{\varvec{n}}(\upchi _\Omega ) P^T \begin{pmatrix} f(A^\Omega _{\varvec{n}})&{}0\\ 0&{}f(0)I_{\varvec{n}}^{\Omega ^C} \end{pmatrix} P I_{\varvec{n}}(\upchi _\Omega ) P^T\\&= \begin{pmatrix} I_{\varvec{n}}^\Omega &{}0\\ 0&{}0 \end{pmatrix} \begin{pmatrix} f(A^\Omega _{\varvec{n}})&{}0\\ 0&{}f(0)I_{\varvec{n}}^{\Omega ^C} \end{pmatrix} \begin{pmatrix} I_{\varvec{n}}^\Omega &{}0\\ 0&{}0 \end{pmatrix} \\&= \begin{pmatrix} f(A^\Omega _{\varvec{n}})&{}0\\ 0&{}0 \end{pmatrix} \end{aligned}$$and consequentially Lemma 5.1 let us conclude
$$\begin{aligned} \{f(A^\Omega _{\varvec{n}})\}_n = R_\Omega (\{f(A_{\varvec{n}})\}_n)\sim _{GLT}^\Omega f(\kappa ')|_{x\in \Omega } = f(\kappa ). \end{aligned}$$ -
GLT\(^\Omega \) 7. Notice that if \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and \(A^\Omega _{\varvec{n}}= B^\Omega _{{\varvec{n}},m}\) for every m, then \(\{B^\Omega _{{\varvec{n}},m}\}_n\sim _{GLT}^\Omega \kappa _m=\kappa \), \(\kappa _m\) converges to \(\kappa \) and \(\{B^\Omega _{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}\{A_{{\varvec{n}}}^\Omega \}_n\). On the opposite, assume there exist reduced GLT sequences \(\{B^\Omega _{{\varvec{n}},m}\}_n\sim _{GLT}^\Omega \kappa _m\) such that \(\kappa _m\) converges to \(\kappa \) in measure and \(\{B^\Omega _{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}\{A_{{\varvec{n}}}^\Omega \}_n\). In this case, let \(B_{{\varvec{n}},m}=E_\Omega (B^\Omega _{{\varvec{n}},m})\) and let \(\kappa '_m\) be the extension of \(\kappa \) given by Lemma 5.3, so that \(\{B_{{\varvec{n}},m} \}_n\sim _{GLT}\kappa '_m\). Using Lemma 4.8, we know that \(\{B_{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n)\), and moreover
$$\begin{aligned} \kappa '_m = {\left\{ \begin{array}{ll} \kappa _m(x,\theta ) &{}x\in \Omega ,\\ 0 &{} x\not \in \Omega , \end{array}\right. } \rightarrow \kappa ' = {\left\{ \begin{array}{ll} \kappa (x,\theta ) &{}x\in \Omega ,\\ 0 &{} x\not \in \Omega , \end{array}\right. } \end{aligned}$$so \(E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n)\sim _{GLT}\kappa '\) and Lemma 5.1 let us conclude that
$$\begin{aligned} R_\Omega (E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n)) =\{A_{{\varvec{n}}}^\Omega \}_n \sim _{GLT}^\Omega \kappa '|_{x\in \Omega } = \kappa . \end{aligned}$$ -
GLT\(^\Omega \) 8. Let \(B_{{\varvec{n}},m}=E_\Omega (B^\Omega _{{\varvec{n}},m})\) and let \(\kappa '_m\) be the extension of \(\kappa \) given by Lemma 5.3, so that \(\{B_{{\varvec{n}},m} \}_n\sim _{GLT}\kappa '_m\). Using Lemma 4.8, we know that
$$\begin{aligned} \{B^\Omega _{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}\{A_{{\varvec{n}}}^\Omega \}_n \iff \{B_{{\varvec{n}},m}\}_n\xrightarrow {\text {a.c.s.}}E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n) \iff \kappa '_m\rightarrow \kappa '. \end{aligned}$$All the functions \(\kappa '_m\) and \(\kappa '\) are zero outside \(\Omega \), and \(\Omega \) has positive measure, so
$$\begin{aligned} \kappa '_m-\kappa ' \rightarrow 0 \iff \kappa '_m-\kappa '|_{x\in \Omega } \rightarrow 0\iff \kappa _m -\kappa \rightarrow 0\iff \kappa _m\rightarrow \kappa . \end{aligned}$$ -
GLT\(^\Omega \) 9. The functions in \( C^\infty (\Omega )\) are restrictions of functions in \(C^\infty ([0,1]^d)\), so, given \(\kappa \), we can consider \(E_\Omega (\{A_{{\varvec{n}}}^\Omega \}_n)\sim _{GLT}\kappa '\) and find smooth \(a'_{i,m}\) and trigonometric polynomials \(f_{i,m}\) such that
$$\begin{aligned} \sum _{i=1}^{N_m}a'_{i,m}(x)f_{i,m}(\theta )\rightarrow \kappa '(x,\theta ) \end{aligned}$$a.e., and if \(a'_{i,m}|_{x\in \Omega } = a_{i,m}\), then
$$\begin{aligned} \sum _{i=1}^{N_m}a'_{i,m}(x)f_{i,m}(\theta )|_{x\in \Omega } =\sum _{i=1}^{N_m}a_{i,m}(x)f_{i,m}(\theta ) \end{aligned}$$converges to \(\kappa '|_{x\in \Omega } =\kappa \) almost everywhere. Thanks to GLT\(^\Omega \) 3 we know that \(\{D_{\varvec{n}}^\Omega (a_{i,m})\}_n\sim _{GLT}^\Omega a_{i,m}\) and \(\{T_{{\varvec{n}}}^\Omega (f_{i,m})\}_n\sim _{GLT}^\Omega f_{i,m}\), so we can apply GLT\(^\Omega \) 4 and obtain
$$\begin{aligned} \left\{ \sum _{i=1}^{N_m}D_{\varvec{n}}^\Omega (a_{i,m})T_{{\varvec{n}}}^\Omega (f_{i,m})\right\} _n\sim _{GLT}^\Omega \sum _{i=1}^{N_m}a_{i,m}(x)f_{i,m}(\theta )\rightarrow \kappa , \end{aligned}$$so that GLT\(^\Omega \) 8 let us conclude that
$$\begin{aligned} \left\{ \sum _{i=1}^{N_m}D_{\varvec{n}}^\Omega (a_{i,m})T_{{\varvec{n}}}^\Omega (f_{i,m})\right\} _n \xrightarrow {\mathrm{a.c.s.}}\{A_{{\varvec{n}}}^\Omega \}_n. \end{aligned}$$
\(\square \)
5.3 Isometry with measurable functions
It has been proved that the space of GLT sequences, up to zero-distributed sequences, is actually isomorphic as an algebra and isometric as a complete pseudometric space to the space of measurable functions on an opportune domain. In particular, every measurable function with domain \([0,1]^d\times [-\pi ,\pi ]^d\) is a GLT symbol for some multilevel GLT sequence. The same can be said for the space of reduced GLT sequences.
Let \(\hat{\mathscr {S}}^\Omega \) be the map connecting each reduced GLT sequence with its symbol
where \(\mathscr {M}_\Omega \) is the space of measurable functions from \(\Omega \times [-\pi ,\pi ]^d\) to \(\mathbb C\), equipped with the metric of the convergence in measure \(d_m\). GLT\(^\Omega \) 4 assures us that \(\hat{\mathscr {S}}^\Omega \) is a linear map, and GLT\(^\Omega \) 1,3 identify the kernel as the set \(\mathscr {Z}\) of zero-distributed sequences. We can thus define the map
and prove it is an isomorphism and an isometry.
Lemma 5.4
The map \(\mathscr {S}^\Omega \) is an isomorphism of algebras.
Proof
By construction, we already know that \(\mathscr {S}^\Omega \) is a linear injective map. Given now any \(\kappa \in \mathscr {M}_\Omega \), let \(\kappa '\) be the extension of \(\kappa \) to \([0,1]^d\) obtained by setting \(\kappa '=0\) outside \(\Omega \). Let \(\{A_{{\varvec{n}}}\}_n\sim _{GLT}\kappa '\), and notice that \(\mathscr {S}^\Omega (R_\Omega (\{A_{{\varvec{n}}}\}_n))\) is \(\kappa \), proving that \(S^\Omega \) is also surjective. \(\square \)
Theorem 5.2
The map \(\mathscr {S}^\Omega \) is an isometry of pseudometric spaces.
Proof
Let \(\{S^\Omega _{{\varvec{n}}}\}_n\sim _{GLT}^\Omega \kappa \) and notice that
Call \(L := \rho _\mathrm{mea}(\kappa )\). By the definition of the infimum, if we set \(\varepsilon >0\), we can always find a measurable set H such that
From now on, let us call \(M={{\,\mathrm{ess}\,}}\sup _H |\kappa |\). Let \(F:\mathbb R\rightarrow \mathbb R\) be a continuous and compact supported function such that \(\upchi _{[-\varepsilon ,M+\varepsilon ]}\ge F\ge \upchi _{[0,M]}\).
Since \(\{S^\Omega _{{\varvec{n}}}\}_n \sim _\sigma \kappa \), we know that
but
For the converse, let \(j_n\) be the sequence of indices that satisfies
The sequence \(r_n\) is bounded by \(L+\varepsilon \) definitively, and \(\frac{j_n-1}{d_n^\Omega }\le 1\), so \(\sigma _{j_n}(S^\Omega _{\varvec{n}})\) is also bounded and admits a subsequence \(j_{n_k}\) that converges to a value N. Consequently,
Let \(F:\mathbb R\rightarrow \mathbb R\) be a continuous and compact supported function such that \(\upchi _{[-\varepsilon ,N+2\varepsilon ]}\ge F\ge \upchi _{[0,N+\varepsilon ]}\).
Since \(\{S^\Omega _{{\varvec{n}}}\}_n \sim _\sigma \kappa \), we know that
Notice that definitively in k,
so
Since we proved that \(\rho _\mathrm{mea}(\kappa ) +2\varepsilon \ge \rho (\{S_{{\varvec{n}}}^\Omega \}_n)\ge \rho _\mathrm{mea}(\kappa ) -2\varepsilon \) for every \(\varepsilon >0\), we conclude that \(\rho (\{S_{{\varvec{n}}}^\Omega \}_n)= \rho _\mathrm{mea}(\kappa )\). Now the proof is finished, since if we take \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \) and \(\{B_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \xi \), then we have by GLT\(^\Omega \) 4 that \(\{A_{{\varvec{n}}}^\Omega \}_n-\{B_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa -\xi \), so
\(\square \)
Corollary 5.1
The space \(\mathscr {G}_d^\Omega \) is a complete pseudometric space when equipped with the acs distance.
Proof
Suppose that \(\{B^\Omega _{{\varvec{n}},m}\}_n\) is a Cauchy sequence in the acs metric and \(\{B^\Omega _{{\varvec{n}},m}\}_n\sim _{GLT}^\Omega \kappa _m\). By Theorem Theorem 5.2, also \(\kappa _m\) is a Cauchy sequence for the convergence in measure. Both the spaces of matrix sequences and measurable functions are complete spaces, so \(\{B^\Omega _{{\varvec{n}},m}\}_n\xrightarrow {a.c.s.}\{A_{{\varvec{n}}}^\Omega \}_n\) and \(\kappa _m\rightarrow \kappa \). GLT\(^\Omega \) 7 let us conclude that \(\{A_{{\varvec{n}}}^\Omega \}_n\sim _{GLT}^\Omega \kappa \), so any Cauchy sequence in \(\mathscr {G}_d^\Omega \) converges in \(\mathscr {G}_d^\Omega \). \(\square \)
Let us now show how the theory of reduced GLT is useful in the context of linear PDE and their discretization.
6 Application to finite difference discretizations
Consider a linear partial differential equation
equipped with some boundary conditions (Dirichlet, Neumann, etc.) when \(x\in \partial \Omega \). Suppose that \(\Omega \subseteq [0,1]^d\) is a closed Peano–Jordan measurable set and b is a function defined over \(\Omega \).
We can try to discretize the equation by considering the d-dimensional grid \(\Xi _n\) over \([0,1]^d\) and by applying a Finite Difference method only on the points of the grid inside \(\Omega \). Notice that the union of \(\Xi _n\) for every n is the set \(\mathbb Q^d\cap [0,1]^d\), that is dense in \([0,1]^d\), and consequently even the set
is dense in \(\Omega ^\circ \). The grids are hence bound to describe well the interior of \(\Omega \), but the same cannot be said about the border. In fact, it may happen that
and in this case no point from \(\Xi _n\) belongs to \(\partial \Omega \), hence the discretization does not take in account the boundary conditions of the problem. When dealing with hyper-tetrahedrons, one can build regular grids whose points on the border are dense through an affinity. Otherwise, we need to use non regular grids shaped accordingly to the boundary, like the ones that arise from the Shortley–Weller Approximation for a convection–diffusion–reaction linear PDE, that we analyse in the following section. Another way to deal with FD discretization over general domain \(\Omega \) that still uses reduced GLT sequences can be found for example in [1].
6.1 Convection–diffusion–reaction PDE
Let us consider the problem
where \(a_{i}\), \(b_i\), c and f are given real-valued continuous functions defined on \(\Omega \) and \(a_{i}\in C^1(\Omega )\). Moreover, suppose that \(\Omega \) is a closed Peano–Jordan measurable set inside \([0,1]^d\) with positive measure. We set \({\varvec{h}}=\frac{{\varvec{1}}}{{\varvec{n}}+{\varvec{1}}}\), so that \(x_{\varvec{j}}={\varvec{j}}{\varvec{h}}\) for \({\varvec{j}}={\mathbf {0}},\ldots ,{\varvec{n}}+{\varvec{1}}\) are the points of the grid \(\Xi _{n}\). It is also natural to assume that \({\varvec{n}}+{\varvec{1}}= n{\varvec{c}}\), where \(\varvec{c}\) is a vector of rational constants. Let \({\mathbf {e}}_i\) be the vectors of the canonical basis of \(\mathbb R^d\) and notice that \(x_{\varvec{j}}+ sh_i\varvec{e}_i = x_{{\varvec{j}}+ s\varvec{e}_i}\). Then, for \({\varvec{j}}={\varvec{1}},\ldots ,{\varvec{n}}\), we try to approximate the terms appearing in (2) according to the classical central FD discretizations on \([0,1]^d\) as follows:
for \(i=1,\ldots ,d\). This approach requires that all the segments connecting the points \(x_{\varvec{j}}\) with \({\varvec{j}}={\varvec{1}},\ldots ,{\varvec{n}}\), to their neighbours \(x_{{\varvec{j}}\pm \varvec{e}_i}\) still lie inside the domain of the problem. It always happens if the domain is \([0,1]^d\), but when we consider \(\Omega \), we need to modify the scheme by adding some points. In particular, we define a new set of neighbours for every point in \(\Xi _n':=\Omega ^\circ \cap \Xi _n\). Given \(x_{\varvec{j}}\in \Xi '_n\) and a direction \(\varvec{e}_i\), we can set the numbers \(s_i^+({\varvec{j}}),s_i^-({\varvec{j}})\) as
that is the size of the biggest connected line contained in the segment connecting \(x_{\varvec{j}}\) to \(x_{{\varvec{j}}+ \varvec{e}_i}\) and containing \(x_{\varvec{j}}\). We can thus call \(x_{\varvec{j}}+s_i^\pm ({\varvec{j}})h_i\varvec{e}_i = x_{{\varvec{j}}+ s_i^\pm ({\varvec{j}})\varvec{e}_i}\) the right/left neighbour of \(x_{\varvec{j}}\) along the direction \(\varvec{e}_i\). The values \(s_i^\pm ({\varvec{j}})\) depend on the point \(x_{\varvec{j}}\), but when it is evident, we can omit the index and write simply \(s_i^\pm \).
As we can see in Fig. 1, even if \(x_{\varvec{j}}\) and \(x_{{\varvec{j}}+ \varvec{e}_i}\) belong to \(\Xi '_n\), it doesn’t mean that \(s_i^+({\varvec{j}})=1\), because the segment connecting \(x_{\varvec{j}}\) to \(x_{{\varvec{j}}+ \varvec{e}_i}\) may not be contained entirely in \(\Omega ^\circ \) (this happens often, for example, when \(\Omega \) is not convex).
Notice that every neighbour is a point of \(\Omega \), so when one of the neighbours is not included in \(\Xi '_n\), it surely belongs the boundary \(\partial \Omega \), and in any case we have \(s_i^\pm >0\). Adding these boundary points to \(\Xi _n'\), we obtain the discretization grid \(\Xi _n^\Omega \) over \(\Omega \), and we can rewrite the formulas (3)–(5) for \(x_{\varvec{j}}\in \Xi '_n\) as
called the difference scheme of Shortley and Weller [30]. Notice that when \(s_j^\pm =1\) for every j and sign ±, we fall again in the classical scheme of central differences.
The evaluations \(u(x_{\varvec{j}})\) of the solution at the grid points \(x_{\varvec{j}}\in \Xi _n^\Omega \) are approximated by the values \(u_{\varvec{j}}\), where \(u_{\varvec{j}}=0\) for \(x_{\varvec{j}}\in \partial \Omega \), and the vector \(\varvec{u}=(u_{\varvec{j}})^T_{x_{\varvec{j}}\in \Omega ^\circ }\) is the solution of the linear system
If we order the indices \({\varvec{j}}\) in \(\Xi _n'\) by lexicographic order, then we can write the system in compact form as
where \(A_{\varvec{n}}^{\Omega ^\circ }\in \mathbb C^{d_n^{\Omega ^\circ }\times d_n^{\Omega ^\circ }}\) and \(\varvec{f}\in \mathbb C^{d_n^{\Omega ^\circ }}\). The coefficients are
Notice that one can rewrite the nonzero off-diagonal coefficients as
6.2 Spectral analysis
As already noted, if all \(s_i^\pm \) are equal to 1, then the relations (6)–(8) reduces to the classic finite difference scheme (3)–(5), so we may ask how many are the points \(x_{\varvec{j}}\in \Omega ^\circ \) such that one of the \(s_i^\pm \) is not equal to 1. By the definition of \(s_i^\pm \), this is equivalent to say that the segment \((x_{\varvec{j}}-h_i\varvec{e}_i,x_{\varvec{j}}+h_i\varvec{e}_i)\) does not lie completely inside \(\Omega ^\circ \). In the next result, we will prove that given any positive integer number k, the number of points \(x_{\varvec{j}}\in \Xi _n'\) for which there exists a direction \(\varvec{e}_i\) such that \((x_{\varvec{j}}-kh_i\varvec{e}_i,x_{\varvec{j}}+kh_i\varvec{e}_i)\) does not lie completely inside \(\Omega ^\circ \) is negligible when compared with the number of points in \(\Xi _n'\).
Lemma 6.1
Let
For every \(k>0\), we have
Proof
Notice that if \(x_{\varvec{j}}\in D(n, k)\), then there exists a direction \(\varvec{e}_i\) and a value \(t\in (-k,k)\) such that \(x_{\varvec{j}}+ th_i\varvec{e}_i\in \partial \Omega \) and \(t\ne 0\). In particular, we infer that \(d(x_{\varvec{j}}, \partial \Omega )<kh_i\) and if we denote \(h=\max _i h_i\), then \(d(x_{\varvec{j}}, \partial \Omega )<kh\).
Using notations and results of Corollary 3.2, we know that \(x_{\varvec{j}}\in K_{kh}\cap \Xi _n'\), but \(kh\rightarrow 0\) as n goes to infinity, so
\(\square \)
We just proved that, except for few relations, the system (9) mimics a classical FD scheme. We can thus consider the extended problem
where \(a'_{i},b'_i,c',f'\) are functions that extend \(a_{i},b_i,c,f\)
Notice that \(b'_i,c'\) are bounded functions since \(\Omega \) is a compact set, and moreover \(a'_{i}\) are bounded and continuous a.e. functions. In [8], it is showed that these conditions on the coefficients are enough to prove that the matrices \(A_{\varvec{n}}\) induced by the relations (3)–(5) build a GLT sequence with symbol
where \({\varvec{n}}+{\varvec{1}}= n\varvec{\nu }\). This is also enough to let us conclude that \(\{ n^{-2} A_{\varvec{n}}^{\Omega ^\circ } \}_n\) is actually a reduced GLT sequence.
Theorem 6.1
Proof
Denote with \(B_{\varvec{n}}^{\Omega ^\circ }\) and \(Z^{\Omega ^\circ }_{\varvec{n}}\) the matrices
where the rows and columns are associated to the points \(x_{\varvec{j}}\in \Xi '_n\). If \(x_{\varvec{j}}\in \Xi _n'\setminus D(n,2)\), then \(x_{\varvec{j}}\) is a point of the grid \(\Xi _n\) inside \(\Omega ^\circ \) such that all its neighbours still belong to \(\Omega ^\circ \). In this case, \((A_{\varvec{n}}^{\Omega ^\circ })_{{\varvec{j}},{\varvec{i}}}\) is the same as \((B_{\varvec{n}}^{\Omega ^\circ })_{{\varvec{j}},{\varvec{i}}}\) and \((A_{\varvec{n}})_{{\varvec{j}},{\varvec{i}}}\), so
hence the row corresponding to \(x_{\varvec{j}}\) in \(Z^{\Omega ^\circ }_{\varvec{n}}\) is zero. From Lemma 6.1, we conclude that the number of non-zero rows in \(Z^{\Omega ^\circ }_{\varvec{n}}\) is \(o(N({\varvec{n}}))\), so \(\{Z^{\Omega ^\circ }_{{\varvec{n}}}\}_n\) is a zero-distributed sequence, since Corollary 3.1 assures us that
From GLT\(^\Omega \) 3 and GLT\(^\Omega \) 4, we conclude that
\(\square \)
A more involved analysis is needed to conclude that \(\{ n^{-2}A_{\varvec{n}}^{\Omega ^\circ } \}_n\sim _\lambda \kappa \). If \(A_{\varvec{n}}^{\Omega ^\circ }\) were Hermitian matrices, the result would follow from GLT\(^\Omega \) 1, but it is almost never the case. Notice that \(\kappa \) is a real valued function, so we can decompose \(A_{\varvec{n}}^{\Omega ^\circ }\) into its Hermitian and skew-Hermitian part. Using GLT\(^\Omega \) 1, 4, we have
On the other hand, the skew-Hermitian part is zero-distributed, but in order to write the expression for its coefficients, we need to remind that the values \(s_i^\pm \) depend on the point \(x_{\varvec{j}}\). To avoid confusion, in this case we will denote them by \(s_i^\pm ({\varvec{j}})\).
Notice that the only non-zero entries \((\mathfrak {I}(n^{-2}A_{\varvec{n}}^{\Omega ^\circ }) )_{{\varvec{j}},{\varvec{i}}}\) are for \({\varvec{i}}= {\varvec{j}}+\varvec{e}_i\) or \({\varvec{i}}= {\varvec{j}}-\varvec{e}_i\). In fact, if \({\varvec{i}}= {\varvec{j}}+\varvec{e}_i\), then \((\mathfrak {I}(n^{-2}A_{\varvec{n}}^{\Omega ^\circ }) )_{{\varvec{j}},{\varvec{i}}}\) is
and if \({\varvec{i}}= {\varvec{j}}-\varvec{e}_i\), then \((\mathfrak {I}(n^{-2}A_{\varvec{n}}^{\Omega ^\circ }) )_{{\varvec{j}},{\varvec{i}}}\) is
Notice that \(s_i^\pm \in (0,1]\), so we can bound every entry by
where \(\nu = \max _i\nu _i\). Moreover, suppose \(x_{\varvec{j}}\) is a grid point in \(\Xi _n' \setminus D(n,3)\). In particular, we have \(s_i^\pm ({\varvec{j}}) = s_i^\pm ({\varvec{j}}+ e_i) = s_i^\pm ({\varvec{j}}- e_i) = 1\) for every i. In this case, the row \({\varvec{j}}\) is easier to write
and we can bound the entries by
Lemma 6.1 assures us that almost all points in \(\Xi '_n\) respect these conditions. Now we are ready to prove that \(\{ n^{-2}A_{\varvec{n}}^{\Omega ^\circ } \}_n\sim _\lambda \kappa \).
Theorem 6.2
Proof
Using the decomposition into Hermitian and skew-Hermitian part, we write
where \(\mathfrak {R}(n^{-2}A_{\varvec{n}}^{\Omega ^\circ })\) are Hermitian and \(\{\mathfrak {R}(n^{-2}A_{\varvec{n}}^{\Omega ^\circ }) \}_n \sim _\lambda \kappa \). Notice that every row of \(\mathfrak {I}(A_{\varvec{n}})\) has at most 2d non-zero elements. Using Lemma 6.1 and the relations (11, 12) we can compute
GLT\(^\Omega \) 2 let us conclude that
\(\square \)
For example, let \(\Omega \) be the union of a quarter of circle with centre in zero and radius 1/2 and the square \([1/2,1]^2\). Consider the coefficients \(a_1(x,y) = 1/(x^2-2x+1+y^2)\) and \(a_2(x,y) = 1/(x^2+y^2-2y+1)\), that are in \(C^1(\Omega )\), and \(b_1(x,y) = |x-y|\), \(b_2(x,y)=\sqrt{x} + \sqrt{y}\), \(c(x,y) = 1/(2xy-x-y+1)\) that are continuous on \(\Omega \). Also, suppose that \(\mathbf \nu ={\mathbf {1}}\), so that \(\kappa (x,\theta ) = \sum _{i=1}^{2}a_{i}(x)(2 - 2\cos (\theta _i))\). When we take the eigenvalues of \(n^{-2}A_{\varvec{n}}^{\Omega ^\circ }\) for \(n=10,20,40,80\), we notice that their imaginary part is never greater than \(10^{-3}\), so we can plot their real parts, sorted in increasing order, and compare them with the increasing rearrangement of the symbol \(\kappa (x,\theta )\). We can notice that up to a number of outliers whose rate goes to zero, the plots converge to the symbol (Fig. 2).
Remark 6.1
The Shortley–Weller approximation just described is actually so general it comprehends classical finite differences methods used on regular domains. For example, in 2 dimensions, every triangular domain can be transformed by affine maps into the isosceles right triangle T described by the vertices with coordinates (0, 0), (0, 1), (1, 0) (Fig. 3). If we superimpose the regular grid \(\Xi _n\) onto the triangle, we find that the union of the points on the border for every n is a dense set in \(\delta T\).
Operating a classical second order method to discretize Problem 2 in 2 dimensions, we fall again in the Shortley–Weller method, so we already know the symbol of the resulting linear system.
7 Application to finite element discretizations
Consider a linear partial differential equation
equipped with some boundary conditions (Dirichlet, Neumann, etc.) when \(x\in \partial \Omega \), where \(\Omega \subseteq [0,1]^d\) is a closed Peano–Jordan measurable set with positive measure and f is a function defined over \(\Omega \).
A common way to discretize the problem is to use a finite elements method, that is based on the choice of a basis for the functions on the domain \(\Omega \). The basis does not necessarily depend on a grid of points inside \(\Omega \), but usually they do, so on a generic \(\Omega \) there’s again the problem to describe the boundary. For this reason, usually the domains are polyhedral or with a regular enough boundary. When we deal with more general shapes, we may need to map the domain into a regular one, or to modify the grids of discretization, and a more involved analysis is required.
Let us consider the problem
where \(\Omega \) is a closed set inside \([0,1]^2\) with negligible boundary and positive measure. Moreover \(a_{i,j}\), \(b_i\), c and f are given complex-valued continuous functions defined on \(\Omega \) and \(a_{i,j}\in C^1(\Omega )\). If \(A=(a_{i,j})_{i,j=1}^2\) is a matrix of functions and \(\varvec{b} = (b_1,b_2)^T\), then the equivalent weak form of (13) reads as
The space \([0,1]^2\) is divided into triangles as shown in Fig. 6, whose vertices are the nodes of \(\Xi _n\). The \(P_1\) finite elements method, studied in [3, 25], uses base functions supported on the grid triangles that fall inside \(\Omega \). We say that the adjacent nodes of a point \(p\in \Xi _n\) are its neighbours, and we call N(p) the set composed of p and its neighbours. Each point p is a vertex for at most 6 triangles, that we call \(T_{i,p}\) as shown in Fig. 4, and we denote their union as \(T_p\) (notice that they depend also on n, but for brevity we omit the index). The collection of all the triangles in the scheme associated to the grid \(\Xi _n\) is
For every point \(p\in \Xi _n\) such that \(T_p\subseteq [0,1]^2\), we define a function \(\psi _{p,n}\) that is linear on each triangle, whose value is 1 at p and 0 on every other point of \(\Xi _n\).
We can explicitly write \(\psi _{p,n}\) and its partial derivatives. If \(p=(x_p,y_p)\) and \(\widetilde{x} = x-x_p\), \(\widetilde{y} = y-y_p\), then
where \(h = 1/(n+1)\). \(P_1\) elements usually arises when the domain is not a square, but it is polyhedral or regular enough. For example, as we can see in Fig. 5, the subdivision scheme adopted has the property to describe also the boundary of the triangle, in opposition to the classical tensor-product hat-functions considered in [20, Section 7.4].
This does not happen when dealing with more complicated domains \(\Omega \), as shown in Fig. 6. In fact we can see that, for example, on a curvilinear shape, the points of \(\Xi _n\) are not enough to approximate the boundary \(\partial \Omega \). This is why Lemma 4.9 is important: we can always modify a small number of points to better approximate the boundary, without changing the relative symbol. Regular grids for non-polyhedral shapes and FE methods can be found in the context of Fictitious Domains (also called Immersed Boundary Methods) for fluid mechanics problems, see for example [12]. Often with curvilinear shape, though, a non-regular polygonal or isoparametric mesh is adopted, and in these cases Theorem 7.2 is a fundamental tool to have, but it needs to be combined with the results of Sect. 7.3, or in [25], to reach the wanted spectral symbol. Since different grids require dedicated analysis, they are worth of a separate study.
When we work on a closed set \(\Omega \subseteq [0,1]^2\) with \(\mu (\partial \Omega )=0\), we focus on the points p such that \(T_p\) is contained in \(\Omega \), so we call
We look for a function u that is a linear combination of the \(\psi _{p,n}\) such that (14) is satisfied for every \(w=\psi _{p,n}\). If we substitute \(u=\sum _{p\in \Xi _n(\Omega )} u_p \psi _{p,n}\) and \(w=\psi _{q,n}\) into (14), then we obtain the system
for every \(q\in \Xi _n(\Omega )\). We call \(S_{\varvec{n}}\) the resulting matrix with entries \(s_{p,q}\) for every \(p,q\in \Xi _n(\Omega )\), where the nodes are sorted in lexicographic order. We can notice that \(p\in \Xi _n(\Omega )\implies p\in \Omega ^\circ \cap \Xi _n\), even if the converse is not always true, so
where \(|\Xi _n(\Omega )|\) is the size of the matrix \(S_{\varvec{n}}\). It leads to solve the system
Remark 7.1
A different boundary condition does not change the stiffness matrix, so the analysis is the same if we impose, for example, \(u = g\) on \(T_D\) and \(\partial u/\partial n = h\) on \(T_N\) where \(\partial T = T_D \coprod T_N\).
7.1 Case on the square
When \(\Omega =[0,1]^2\), we already know that, under suitable hypotheses on the regularity of the coefficients, the sequence of stiffness matrices \(\{S_{n}\}_n\) described in (15) is actually a multilevel GLT sequence, for which we can compute GLT and spectral symbol. Here we prove that the same holds when \(A,\varvec{b},c\) are just \(L^1\) functions.
Theorem 7.1
We call B the \(3\times 2\) matrix
and we indicate with \(B_1,B_2,B_3\) its rows. Given \(L^1\) functions \(A:(0,1)^2\rightarrow \mathbb C^{2\times 2}\), \(\varvec{b}:(0,1)^2 \rightarrow \mathbb C^2\) and \(c:(0,1)^2 \rightarrow \mathbb C\), we have that the sequence \(\{S_{{\varvec{n}}}\}_n\) is a multilevel GLT sequence with symbol \(k(x,\theta )\), where
If A is also Hermitian for every \(x\in (0,1)^2\), then the sequence \(\{ S_{{\varvec{n}}}\}_n\) has \(k(x,\theta )\) as spectral symbol.
Proof
We split the matrix \( S_{\varvec{n}}\) into \( P_{\varvec{n}}+ Z_{\varvec{n}}\), where
and we prove that \(\{ P_{{\varvec{n}}}\}_n\sim _{GLT}k(x,\theta )\) and \(\{ Z_{{\varvec{n}}}\}_n\) is zero distributed.
Notice that \(\psi _{p}\) is supported on \(T_p\), so \( ( S_{\varvec{n}})_{p,q}, ( P_{\varvec{n}})_{p,q}, ( Z_{\varvec{n}})_{p,q}\) are different from zero only when q is one of the 6 neighbours of p or p itself, that is \(q\in N(p)\). Moreover, every \(\psi _{p,n}\) is nonnegative and less than 1, and each component of \(\nabla \psi _{p,n}\) is bounded by 1/h in absolute value.
Notice that the area of \(T_{p}\) is \(3h^2\) for every p. Moreover, the functions \(b_1,b_2,c\) are \(L^1\), so for every \(\varepsilon >0\) there exists a \(\delta >0\) such that
Notice that every triangle \(T_{(i)}\) of the triangulation \(\mathscr {T}_n\) is inside \(T_p\) for at most 3 different points p, that are its vertices, and if \(3h^2\le \delta \), we get
Since we can take \(\varepsilon \) arbitrarily small as n tends to infinity, we infer that \(n^{-1}\Vert Z_{\varvec{n}}\Vert _2\rightarrow 0\), so we can use Z2 and conclude that \(\{ Z_{{\varvec{n}}}\}_n\) is zero-distributed.
Let us analyse now the matrix \( P_{\varvec{n}}\).
The elements of \( P_{\varvec{n}}\) on the row associated to \(p=x_{\varvec{j}}\) are different from zero only when \(q\in N(p)\). Call \(t_{p,a,b} = (P_{\varvec{n}})_{p,p+a\varvec{e}_1 + b\varvec{e}_2}\), and a computation shows that
and \(t_{p,a,b} = 0\) for every other a, b.
Assume that A is a continuous function, so that there exists a modulus of continuity \(\omega _A\) defined as
and such that \(\lim _{\delta \rightarrow 0} \omega _A(\delta ) = 0\). Let us define a 2-level GLT sequence \(\{ G_{n}\}_n\) as
with symbol \(k(x,\theta )\). The elements of \( P_{\varvec{n}}- G_{\varvec{n}}\) on the row associated to \(p=x_{\varvec{j}}\) are different from zero only when \(q\in N(p)\). If we call \(z_{p,a,b} = (P_{\varvec{n}})_{p,p+\varvec{e}_1 +b\varvec{e}_2} - (Q_{\varvec{n}})_{p,p+\varvec{e}_1 +b\varvec{e}_2}\), then we can bound the values of \(|z_{p,0,0}|\) with \( 6\omega _A(h\sqrt{2})\) and \(|z_{p,0,1}|\) with \(2\omega _A(h\sqrt{2})\) as follows.
Analogous computations show that \( |z_{p,1,0}|, |z_{p,0,-1}|, |z_{p,-1,0}|\) are also bounded by \(2\omega _A(h\sqrt{2})\). Moreover, we can bound \(|z_{p,1,-1}| \) with \(\omega _A(h\sqrt{2})\) as follows.
A similar argument shows that \( |z_{p,-1,1}|\) is also bounded by \(\omega _A(h\sqrt{2})\). Since every row of \( P_{\varvec{n}}- G_{\varvec{n}}\) has at most 7 non-zero elements and they are all bounded in absolute value by \(6 \omega _A(h\sqrt{2})\), then
and using again Z2, we obtain that \( P_{\varvec{n}}- G_{\varvec{n}}\) is zero-distributed. Since \(\{ G_{{\varvec{n}}}\}_n\) has GLT symbol \(k(x,\theta )\), we conclude that
If we now assume that A is an \(L^1\) function, then we can find a sequence \(A_m\) of continuous functions such that \(\Vert A-A_m\Vert _1 \le 2^{-m}\), where
If we define \(r_{a,b,m}\) like in (17) with \(A_m\) instead of A, and \(k_m(x,\theta )\) like in (16) with \(r_{a,b,m}\) instead of \(r_{a,b}\), then we get \(k_m\rightarrow k\) in \(L^1\). Moreover, if \(\{ S^{(m)}_{{\varvec{n}}}\}_n\) is defined as above, but with \(A_m\) instead of A, then from the previous analysis, we know that \(\{ S^{(m)}_{{\varvec{n}}}\}_n\sim _{GLT}k_m\). The difference
presents two zero-distributed sequences \(\{ Z^{(m)}_{{\varvec{n}}}\}_n\) and \(\{ Z_{{\varvec{n}}}\}_n\), so we need to analyse the other two sequences. Notice that for every measurable set \(U\subseteq [0,1]^2\) and every indices i, j we know that
but \(A-A_m\) is also \(L^1\), so given \(\varepsilon \) there exists a \(\delta \) such that \(\mu (U)<\delta \) implies that
If \(\mu (T_p)=3h^2\le \delta \), then we can bound the 1 Schatten norm of \( P_{\varvec{n}}^{(m)} - P_{\varvec{n}}\) by the sum of the absolute values of their elements, so
Using ACS 4, we obtain that \(\{ P_{\varvec{n}}^{(m)}\}_n\xrightarrow {a.c.s.}\{ P_{\varvec{n}}\}_n\) and \(\{ S_{\varvec{n}}^{(m)}\}_n\xrightarrow {a.c.s.}\{ S_{\varvec{n}}\}_n\). We conclude that \(\{ S_{{\varvec{n}}}\}_n\sim _{GLT}k\).
When A is Hermitian, we can prove that \( P_{\varvec{n}}\) is Hermitian. In fact
Since \(\{ S_{{\varvec{n}}}\}_n = \{ P_{{\varvec{n}}}\}_n +\{ Z_{{\varvec{n}}}\}_n\) and from (18), we know that \(\Vert \widetilde{Z}_{\varvec{n}}\Vert _2 = o(n)\), we can apply GLT 2 and conclude that \(\{ S_{{\varvec{n}}}\}_n\sim _\lambda k\). \(\square \)
7.2 Problem on sub-domains
Let us now consider a closed Peano–Jordan measurable set \(\Omega \subseteq [0,1]^2\) with positive measure. Consider the problem (14) on \(\Omega \), where now \(A,\varvec{b},c\) are \(L^1\) functions defined on \(\Omega \). When we apply a \(P_1\) discretization. The resulting matrices form a sequence equivalent to a reduced GLT sequence that descends from the square case. In particular, we can prove the following theorem.
Theorem 7.2
Given a closed Peano–Jordan measurable set \(\Omega \subseteq [0,1]^2\) with positive measure. Let \(\widetilde{A}\), \(\widetilde{\varvec{b}}\) and \(\widetilde{c}\) be extensions of A, \(\varvec{b}\) and c to \((0,1)^2\), obtained by setting \(\widetilde{a}_{i,j}(z) = \widetilde{b_j}(z)=\widetilde{c}(z)=0\) outside \(\Omega \) for every i, j. Moreover, let \(\widetilde{k}\) be the symbol described in Theorem 7.1 referred to the problem with coefficients \(\widetilde{A}\), \(\widetilde{\varvec{b}}\), \(\widetilde{c}\), and denote \(k = \widetilde{k}|_{\Omega ^\circ }\). If \(S^{\Omega }_{{\varvec{n}}}\) is the matrix resulting from the \(P_1\) discretization using the grid \(\Xi _{n}( \Omega )\), then
and if A is Hermitian for every \(x\in \Omega \), then k is also a spectral symbol for \(\{ S^{\Omega }_{{\varvec{n}}}\}_n\).
Proof
Let \( S_{{\varvec{n}}}\) be the matrix resulting from the \(P_1\) discretization of the problem with coefficients \(\widetilde{A}\), \(\widetilde{\varvec{b}}\), \(\widetilde{c}\) on the square \([0,1]^2\) using the grid \(\Xi _{n}\). We want to show that \(R_{\Xi _n(\Omega )}( S_{{\varvec{n}}}) = S^{\Omega }_{{\varvec{n}}}\), that is, for every pair of points (p, q) in \(\Xi _{n}(\Omega )\), we prove \(( S_{{\varvec{n}}})_{p,q} = (S^{\Omega }_{{\varvec{n}}})_{p,q}\). From (15), the equations for the two quantities are
but \(p\in \Xi _n(\Omega )\) so \(T_p^\circ \subseteq \Omega ^\circ \) and therefore the two quantities are the same since \(A,\varvec{b}\) and c coincide with \(\widetilde{A}\), \(\widetilde{\varvec{b}}\) and \(\widetilde{c}\) on \(\Omega \). In this case, it may happen that \(\Xi _n(\Omega ) \subsetneq \Xi _n\cap \Omega ^\circ \) since \(\Omega \) may not be convex, but the two sets are actually almost the same. In fact,
so any point \(p\in E_n\) is at distance at most \(h_n=1/(n+1)\) from the boundary \(\partial \Omega \), and using Corollary 3.2, we conclude
As a consequence,
and Lemma 4.9 assures us that it is sufficient to prove the thesis for \(R_{\Omega ^\circ }(S_{\varvec{n}})\).
Using the definition of reduced GLT, we can affirm that
If we now assume that A is an Hermitian matrix for every \(x\in \Omega \), then automatically also \(\widetilde{A}\) is Hermitian for every x, since it is equal to A or it is the zero matrix. From the proof of Theorem 7.1, we know that \( S_{{\varvec{n}}} = P_{{\varvec{n}}} + Z_{{\varvec{n}}}\), where \( P_{{\varvec{n}}}\) is Hermitian and \(\Vert Z_{{\varvec{n}}}\Vert _2 = o(n)\). If we call \(P^{\Omega ^\circ }_{{\varvec{n}}} = R_{\Omega ^\circ }( P_{{\varvec{n}}})\) and \(Z^{\Omega ^\circ }_{{\varvec{n}}} = R_{\Omega ^\circ }( Z_{{\varvec{n}}})\) then we find that \(R_{\Omega ^\circ }(S_{\varvec{n}}) = P^{\Omega ^\circ }_{{\varvec{n}}} + Z^{\Omega ^\circ }_{{\varvec{n}}}\), \(P^{\Omega ^\circ }_{{\varvec{n}}}\) is Hermitian and for Lemmas 4.3, 4.2 and 3.1,
Notice that \(\{P_{{\varvec{n}}}^{\Omega ^\circ }\}_k\sim _\lambda k\), so we can use GLT\(^\Omega \) 2, and conclude that
\(\square \)
Notice that \(k(x,\theta )\) has the same form described in (16), (17), where A is now defined only on \(\Omega \).
7.3 P1 on mapped grids
When the domain \(\Omega \) is compact, but presents an irregular boundary, or when we want to focus the discretization to particular points in the domain, the adopted grids are usually adapted to the problem geometry. We can find examples of such grids and relative spectral analyses already in [20] for \(\Omega =[0,1]^d\) and in [3] for more general domains. In both cases, the grids taken into account were produced starting from a regular grid and by applying an invertible function \(\phi \). For clarity sake, we start from a smooth (\(C^1\)) embedding \(\varphi \) that maps \(\Omega \) into \([0,1]^d\), and if \(D=\varphi (\Omega )\), then we call the inverse \(\phi := \varphi ^{-1}:D\rightarrow \Omega \). Notice that \(\varphi \) is in particular a closed locally Lipschitz map, so D is a compact set in \([0,1]^d\) and it is still Peano–Jordan measurable. We can thus induce a discretization grid on \(\Omega \) given by \(\phi (D\cap \Xi _n)\) for every n (Fig. 7).
We now discretize the diffusion problem (13) using modified \(P_1\) finite elements on a compact domain \(\Omega \subseteq \mathbb R^2\) with positive measure, \(\mu (\partial \Omega ) = 0\) and grids described by the function \(\phi \).
where \(a_{i,j}\), \(b_i\), c and f are given complex-valued \(L^1\) functions defined on \(\Omega \).
The basis function we consider on \(\Omega \) are produced from the classical \(P_1\) elements by composition with the map \(\varphi \). In fact, if \(p\in \Xi _n(D)\subseteq \Xi _n\cap D\) and \(p' = \phi (p)\) we can define the basis function associated to \(p'\) as
Note that the support of \(\xi _{p',n}\) is \(T_{p'}:= \phi (T_p)\) and \(T_p\subseteq D\iff T_{p'}\subseteq \Omega \). In the classical \(P_1\) setting, we consider a basis function for each point in \(\Xi (D)\), so here we will produce a function \(\xi _{p',n}\) only for the points \(p'\in \phi (\Xi (D))\), and we call the set of such points
The weak form of the problem (14) leads us to a linear system similar to the ones already considered. In fact, if we substitute \(u=\sum _{p'\in \Xi _n(\Omega )} u_{p'} \xi _{p',n}\) and \(w=\xi _{q',n}\) into problem (14), then we obtain the relation
for every \(q'\) in \(\Xi _n(\Omega )\). Sorting the relations in lexicographical order with respect to the appearance of \(\varphi (q')\) in the grid \(\Xi _n\), we obtain a linear system \(S_n^\Omega \varvec{u}_n = \varvec{f}_n\) of size \(|\Xi _n(\Omega )|=|\Xi _n(D)|\).
The analysis of this particular instance descends from the fact that we can find opportune coefficients for the problem (14) on the domain D so that the linear system arising from the \(P_1\) elements applied to the regular grid \(\Xi _n(D)\) coincides with \(S_n^\Omega \). Consider in fact the problem
and its weak form
where
are \(L^1\) functions on D. Using the \(P_1\) elements we obtain the relations
for every \(q\in \Xi _n(D)\), that give rise to the system \(S_n^D \widetilde{\varvec{u}} =\widetilde{\varvec{f}}_n\) of size \(|\Xi _n(D)|\). Notice that if \(p',q' \in \Xi _n(\Omega )\) such that \(p'=\phi (p)\) and \(q'=\phi (q)\), then
so comparing Eqs. 22 and 19 we conclude that \(s_{p,q}^D = s_{p',q'}^\Omega \) for every \(p,q\in \Xi (D)\) and therefore \(S_n^\Omega = S_n^D\). The symbols of the sequence can be easily computed from Theorem 7.2.
8 Future work
We have introduced and thoroughly analysed the space of reduced GLT, showing how they can prove useful in applications. Reduced GLT sequences have already been applied on discretizations of fractional PDEs on generic domains, and they can also be applied straightforwardly on graph structures, as showed in [1]. More applications are straightforward to analyse by generalizing the ones of classical GLT, like fractional PDE, multigrid techniques, isogeometric analysis, preconditioned methods and many others.
Following the lead of the classical GLT sequences, the next step is to generalize the space of reduced GLT to the case of block sequences, studied in [9, 10], in order to tackle also systems of PDEs and high-order approximations on generic domains.
References
Adriani, A., Bianchi, D., Serra-Capizzano, S.: Asymptotic spectra of large (grid) graphs with a uniform local structure (part I): theory. Milan J. Math. 88, 409–454 (2020)
Avram, F.: On bilinear forms in Gaussian random variables and Toeplitz matrices. Probab. Theory Relat. 79, 37–45 (1988)
Beckermann, B., Serra-Capizzano, S.: On the asymptotic spectrum of finite element matrix sequences. SIAM J. Numer. Anal. 45, 746–769 (2007)
Barbarino, G.: Equivalence between GLT sequences and measurable functions. Linear Algebra Appl. 529, 397–412 (2017)
Barbarino, G.: Spectral Measures. Structured Matrices in Numerical Linear Algebra: Analysis, Algorithms and Applications. Springer International Publishing, Cham, pp. 1–24 (2019)
Barbarino, G.: Normal Form for GLT Sequences. arXiv:1805.08708 (2018)
Barbarino, G., Garoni, C.: From convergence in measure to convergence of matrix-sequences through concave functions and singular values. Electron. J. Linear Algebra 32, 500–513 (2017)
Barbarino, G., Serra-Capizzano, S.: Non-Hermitian perturbations of Hermitian matrix-sequences and applications to the spectral analysis of approximated PDEs. Numer. Linear Algebra Appl. 27, e2286 (2020)
Barbarino, G., Garoni, C., Serra-Capizzano, S.: Block generalized locally Toeplitz sequences: theory and applications in the unidimensional case. Electron. Trans. Numer. Anal. 53(1), 28–112 (2020)
Barbarino, G., Garoni, C., Serra-Capizzano, S.: Block generalized locally Toeplitz sequences: theory and applications in the multidimensional case. Electron. Trans. Numer. Anal. 53(1), 113–216 (2020)
Bini, D.A., Capovani, M.: Spectral and computational properties of band symmetric Toeplitz matrices. Linear Algebra Appl. 52–53, 99–126 (1983)
Boffi, D., Gastaldi, L., Heltai, L.: A Distributed Lagrange Formulation of the Finite Element Immersed Boundary Method for Fluids Interacting with Compressible Solids. Mathematical and Numerical Modeling of the Cardiovascular System and Applications, SEMA SIMAI Springer Series, vol 16. Springer, Cham (2018)
Böttcher, A., Grudsky, S.M.: Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis. Birkhäuser Verlag, Basel (2000)
Böttcher, A., Grudsky, S.M.: Spectral Properties of Banded Toeplitz Matrices. SIAM, Philadelphia (2005)
Böttcher, A., Silbermann, B.: Introduction to Large Truncated Toeplitz Matrices. Springer, New York (1999)
Böttcher, A., Silbermann, B.: Analysis of Toeplitz Operators, 2nd edn. Springer, Berlin (2006)
Erdős, P.: Some remarks on the measurability of certain sets. Bull. Am. Math. Soc. 51(4), 728–731 (1945)
Fasino, D., Serra-Capizzano, S.: From Toeplitz matrix sequences to zero distribution of orthogonal polynomials. Contemp. Math. 323, 329–339 (2003)
Garoni, C., Serra-Capizzano, S.: Generalized Locally Toeplitz Sequences: Theory and Applications, vol. I. Springer, Cham (2017)
Garoni, C., Serra-Capizzano, S.: Generalized Locally Toeplitz Sequences: Theory and Applications, vol. II. Springer, Cham (2018)
Golinskii, L., Serra-Capizzano, S.: The asymptotic properties of the spectrum of nonsymmetrically perturbed Jacobi matrix-sequences. J. Approx. Theory 144, 84–102 (2007)
Grenader, U., Szegö, G.: Toeplitz Forms and Their Applications, 2nd edn. AMS Chelsea Publishing, New York (1984)
Kuijlaars, A.B.J., Serra-Capizzano, S.: Asymptotic zero distribution of orthogonal polynomials with discontinuously varying recurrence coefficients. J. Approx. Theory 113, 142–155 (2001)
Kuijlaars, A.B.J., Van Assche, W.: The asymptotic zero distribution of orthogonal polynomials with varying recurrence coefficients. J. Approx. Theory 99, 167–197 (1999)
Morozov, S., Serra-Capizzano, S., Tyrtyshnikov, E.: Computation of asymptotic spectral distributions for sequences of grid operators. Comput. Math. Math. Phys. 60(11), 1761–1777 (2020)
Parter, S.V.: On the distribution of the singular values of Toeplitz matrices. Linear Algebra Appl. 80, 115–130 (1986)
Serra-Capizzano, S.: Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations. Linear Algebra Appl. 366, 371–402 (2003)
Serra-Capizzano, S.: The GLT class as a generalized Fourier analysis and applications. Linear Algebra Appl. 419(1), 180–233 (2006)
Serra-Capizzano, S., Tablino-Possio, C.: Superlinear preconditioners for finite differences linear systems. SIAM J. Matrix Anal. Appl. 25, 152–164 (2003)
Shortley, G.H., Weller, R.: The numerical solution of Laplace’s equation. J. Appl. Phys. 9, 334–348 (1938)
Tilli, P.: A note on the spectral distribution of Toeplitz matrices. Linear Multilinear Algebra 45, 147–159 (1998)
Tilli, P.: Locally Toeplitz sequences: spectral properties and applications. Linear Algebra Appl. 278, 91–120 (1998)
Tyrtyshnikov, E.E.: A unifying approach to some old and new theorems on distribution and clustering. Linear Algebra Appl. 232, 1–43 (1996)
Tyrtyshnikov, E.E., Zamarashkin, N.L.: Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships. Linear Algebra Appl. 270, 15–27 (1998)
Tyrtyshnikov, E.E., Zamarashkin, N.L.: A general equidistribution theorem for the roots of orthogonal polynomials. Linear Algebra Appl. 366, 433–439 (2003)
Widom, H.: Extreme eigenvalues of translation kernels. Trans. Am. Math. Soc. 100, 252–262 (1961)
Zamarashkin, N.L., Tyrtyshnikov, E.E.: Distribution of eigenvalues and singular values of Toeplitz matrices under weakened conditions on the generating function. Sb. Math. 188, 1191–1201 (1997)
Funding
Open access funding provided by Aalto University.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Daniel Kressner.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This 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/.
About this article
Cite this article
Barbarino, G. A systematic approach to reduced GLT. Bit Numer Math 62, 681–743 (2022). https://doi.org/10.1007/s10543-021-00896-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-021-00896-7
Keywords
- Multilevel generalized locally Toeplitz sequence
- Asymptotic distribution of singular values and eigenvalues
- Algebra of sequences
- Discretization of PDE on general domain
- Finite differences
- Finite elements