In this work we review some proposals to define the fractional Laplace operator in two or more spatial variables and we provide their approximations using finite differences or the so-called Matrix Transfer Technique. We study the structure of the resulting large matrices from the spectral viewpoint. In particular, by considering the matrix-sequences involved, we analyze the extreme eigenvalues, we give estimates on conditioning, and we study the spectral distribution in the Weyl sense using the tools of the theory of Generalized Locally Toeplitz matrix-sequences. Furthermore, we give a concise description of the spectral properties when non-constant coefficients come into play. Several numerical experiments are reported and critically discussed.
Hinweise
This work was funded by GNCS-INdAM. The authors are members of the INdAM research group GNCS.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The study of the fractional Laplace operator was initiated in 1938 by Marcel Riesz in his seminal work [37]. However, since then numerous definitions for such operator have been proposed due to the need of describing several distinct types of applications (for a recent survey, refer to [24] and to the references therein). In the present paper, we review two main proposals to define the fractional Laplace operator which enable us to construct approximations in two or more spatial variables. As it is well-known, the standard Laplacian in \({\mathbb {R}}^d\) can be formulated as
For generalizing such operator towards the fractional case two different strategies can be followed:
(a)
compute a fractional power of the d-dimensional Laplacian in (1);
(b)
‘fractionalize’ each integer order partial derivative in (1).
Obviously, these two strategies coincide in the 1D case, while they lead to different operators in more than one dimension. Formulation (a) is particularly useful when imposing boundary conditions which differ from the standard Dirichlet ones. Indeed, in [21] Ilić et al. showed that the problems involving the fractional Laplacian of the form (a) are well defined on finite domains with homogeneous boundary conditions of Dirichlet, Neumann and Robin type. This is due to the fact that the fractional Laplacian as in (a) has the same interpretation as the standard Laplacian in terms of spectral decomposition for such boundary conditions. Formulation (b) should be preferred instead when modeling phenomena that show a direction-dependent character and then require a different fractional order along each spatial dimension. In this regard, we mention the application of the fractional paradigm to cardiac electrophysiology (see, e.g., [26]). Formulation (b) suits better than (a) here because in the heart the myocyte fibers tend to align in a particular direction and therefore the propagation of the electrical wave is different orthogonally, longitudinally, and transversally along the fibers.
Discretizing (1) by means of finite differences with uniform step-size in each direction and considering an hypercube as domain, we obtain a d-level Toeplitz matrix associated to a generating function [10], also known as symbol [17, 18], which provides an asymptotic description of the spectrum of the discretization matrices. In the light of formulations (a) and (b), for generalizing the symbol to the fractional case we can:
(1)
take a fractional power of the symbol associated to the discretization of the d-dimensional Laplacian in (1);
(2)
‘fractionalize’ the symbol associated to the discretization of each integer order partial derivative in (1).
Suitable (finite difference) approximations of the fractional Laplacian are then obtained by considering the corresponding d-level Toeplitz matrices (we refer the reader to [30, 34, 35] for the unidimensional case). It is worth mentioning that a similar idea was introduced by Lubich in [27, 28] for constructing the so-called Fractional Linear Multistep Methods (FLMMs). In that case, the resulting schemes for a one-sided fractional operator (in the Riemann-Liouville or in the Caputo sense) were derived by considering a fractional power of the generating function of the coefficients of a classical linear multistep method for ordinary differential equations.
Anzeige
An alternative matrix representation of the fractional Laplacian can be obtained by means of the so-called Matrix Transfer Technique (MTT) proposed in [21, 22]. The approximation to the fractional Laplacian in this case is given by a fractional power of the matrix representation obtained by using any reasonable method for discretizing the standard Laplacian. As an application, we mention that in [45] the MTT has been used for solving fractional Bloch-Torrey models in 2D with fractional Laplacian following both formulations (a) and (b). The interest in these models is due to the fact that they are used to study anomalous diffusion in the human brain. We point out that in order to face the high computational efforts that may result from this approach, rational approximations to the MTT and rational Krylov methods have been recently introduced in [1‐4, 8, 20].
The aim of this paper is twofold: first, we review the spectral properties of finite difference discretizations, which are of Toeplitz type associated with symbols, as in (i) and (ii); second, we investigate the spectral properties of the matrices obtained by the MTT as fractional powers of both finite difference and finite element approximations of the standard Laplacian. Aside from the study of the spectrum/conditioning of the above matrices, we show that the corresponding matrix-sequences belong to the Generalized Locally Toeplitz (GLT) class.
One reason for characterizing all the aforementioned discretization matrix-sequences as GLT matrix-sequences relates to the solution of the corresponding linear systems. Iterative schemes such as multigrid and preconditioned Krylov methods—able to exploit the GLT structure—can be found in [13, 23, 25, 29, 32].
The rest of this paper is organized as follows. In Sect. 2 we briefly recall the main results of the classical theory on the spectral behavior of Toeplitz matrices generated by integrable functions, as well as the notion of symbol for a generic matrix-sequence and the main properties of the GLT class. In Sect. 3 we collect various definitions and results concerning the 1D fractional Laplacian. Section 4 is devoted to the construction of matrix approximations to the fractional Laplacian both in one and in two dimensions. Section 5 contains a detailed spectral analysis of the underlying matrices. Few numerical tests that confirm our theoretical findings are discussed in Sect. 6. Finally, in Sect. 7 we draw some conclusions.
Anzeige
2 Preliminaries on Toeplitz and GLT matrix-sequences
For an independent reading, in this section we formalize the definition of (d-level) Toeplitz matrix associated to a Lebesgue integrable function and we recall few key analytical features of the generating function, which provide information on the spectral properties of the associated Toeplitz matrix (Sect. 2.1). Moreover, we introduce the GLT class, a \(*\)-algebra of matrix-sequences containing Toeplitz sequences, diagonal sampling matrix-sequences, and zero-distributed matrix-sequences (Sect. 2.2).
2.1 Spectral results for Toeplitz matrices
Let f be an integrable function defined on \([-\pi ,\pi ]\) and extended periodically to the whole real axis \({\mathbb {R}}.\) We denote by
the Toeplitz matrix related to f (called generating funtion) whose coefficients \(a_j,\)\(j=0,\pm 1,\)\(\pm 2, \dots , \pm (n-1),\) are the Fourier coefficients of f, i.e.,
In the case where f is an even, real-valued and nonnegative function, the related \(T_n(f)\) is a real, symmetric and positive semidefinite matrix. If f is only real-valued, then the matrix \(T_n(f)\) is Hermitian.
The following result allows to localize the spectrum of \(T_n(f)\) in terms of \({\mathrm{ess}}\inf f\) and \({\mathrm{ess}}\sup f,\) the essential infimum and the essential supremum of f (that is the infimum and the supremum of f, up to zero-measure sets); see, e.g., [17] for a proof.
Theorem 1
Let\(m_f={\mathrm{ess}}\inf f\) and \(M_f= {\mathrm{ess}}\sup f\). If \(m_f <M_f\)then the spectrum of\(T_n(f)\)is contained in the interval\((m_f, M_f)\)independently of\(n\in {\mathbb {N}}\). If\(m_f= M_f\)then we have the trivial case where\(T_n(f)=m_f I_n\), with\(I_n\)denoting the identity of ordern.
More generally, when f and g are real-valued and g is nonnegative and not identically zero, the range of f/g gives precise indications regarding the spectrum of \(T_n^{-1}(g) T_n(f)\).
Theorem 2
([39, Theorem 2.1]) Letf, gbe two real-valued integrable functions on\([-\pi ,\pi ]\)such that
$$\begin{aligned} 0< r \le \frac{f}{g} \le R < \infty , \end{aligned}$$
with\(r={\mathrm{ess}}\inf (f/g)\) and \(R={\mathrm{ess}}\sup (f/g).\) If \(g \ge 0\) (not identically zero) and\(r<R\), then the spectrum of\(T_n^{-1}(g) T_n(f)\)is contained in the interval (r, R) independently of\(n\in {\mathbb {N}}\). If\(r= R\)then we have the trivial case where\(T_n^{-1}(g) T_n(f)=r I_n\), with\(I_n\)denoting the identity of ordern.
To provide a result concerning the behavior of the minimum eigenvalue of \(T_n(f)\) the following definitions must be introduced first.
Definition 1
Let f, g be two nonnegative integrable functions (not identically zero) on \(\varOmega \subset \mathbb {R}^{d}\), \(d\ge 1\). We write \(f \sim g\) if and only if there exist two positive constants \(0<r\le R <\infty\) such that
$$\begin{aligned} rg \le f \le Rg \end{aligned}$$
uniformly on \(\varOmega .\)
Definition 2
Let f be a nonnegative integrable function on \(\varOmega \subset \mathbb {R}^{d}\), \(d\ge 1\). We say that f has a zero of order \(\beta\) in \(\theta = {\bar{\theta }}\) if and only if there exist two positive constants \(0<c\le \hat{c} <\infty\) such that
holds in a suitable neighborhood \(I\subset \varOmega\) of \({\bar{\theta }}\). If \(I=\varOmega ,\) then \({\bar{\theta }}\) is also the unique zero of f and in this case the definition is equivalent to the relation \(f \sim \Vert \theta -{\bar{\theta }}\Vert _2^\beta\), according to Definition 1.
Using the notations introduced in Definitions 1 and 2, the following result holds (see [9, 39]).
Theorem 3
Letfbe a nonnegative integrable function defined on\([-\pi ,\pi ]\)such that\({\mathrm{ess}}\inf f=0\) and \({\mathrm{ess}}\sup f>0.\)In addition, if for some\({\bar{\theta }} \in [-\pi ,\pi ]\)fsatisfies the condition\(f \sim |\theta -{\bar{\theta }}|^\beta ,\)\(\beta >0\), then\(T_n(f)\)is a positive definite matrix for any\(n\in {\mathbb {N}}\)and\(\lambda _{\min } (T_n(f)) \sim 1/n^\beta\).
We remark that a similar result holds true also for the maximum eigenvalue; of course, in this case we should consider the minimum eigenvalue of \(T_n(M_f-f)=M_f I_n -T_n(f)\), according to the notations of Theorem 1.
Theorem 4
Letf, gbe two nonnegative integrable functions on\([-\pi ,\pi ]\)such that\({\mathrm{ess}}\inf f=0,\)\({\mathrm{ess}}\sup f>0,\)\({\mathrm{ess}}\inf g=0,\)and\({\mathrm{ess}}\sup g>0.\)Assuming that
$$\begin{aligned} 0< r \le \frac{f}{g} \le R < \infty , \end{aligned}$$
then,
$$\begin{aligned} r \, \lambda _{\min } (T_n(g)) \le \lambda _{\min } (T_n(f)) \le R \, \lambda _{\min } (T_n(g)). \end{aligned}$$
The previous results can be extended to two-level Toeplitz matrices which are defined as follows. Let \(f(\theta _1,\theta _2)\) be an integrable function defined on the square \([-\pi ,\pi ]^2\) and extended periodically on \({\mathbb {R}}^2.\) Denoting by
By the construction given in (2)–(4), we can easily deduce that when the generating function is a multiplicatively separable function, i.e., \(f(\theta _1,\theta _2) =s_1(\theta _1) s_2(\theta _2)\), we have
with \(\otimes\) being the standard Kronecker product [7]. The latter and the linearity of the Toeplitz operator imply that for a generic integrable function f
where \(J_{r,1}\) (\(J_{r,-1}\)) denotes the lower (upper) shift matrix of order r.
The last representation suggests the following compact notation in the case of a d-variate generating function and of a d-level Toeplitz matrix. Let \(f({\varvec{\theta }})\), \({\varvec{\theta }}=(\theta _1,\ldots ,\theta _d)\) be an integrable function defined on \([-\pi ,\pi ]^d\) and extended periodically over \(\mathbb {R}^d\). Denoting by
where \({{\varvec{n}}} = (n_1,\ldots ,n_d)\), \({{\varvec{1}}}=(1,\ldots ,1)\), and the ordering considered in \({{\varvec{1}}}-{{\varvec{n}}}\le {{\varvec{j}}} \le {{\varvec{n}}}-{{\varvec{1}}}\) is the lexicographical one employed for \({{\varvec{j}}}\) and with \({{\varvec{s}}}\le {{\varvec{t}}}\) if and only if \(s_j\le t_j\ \forall j=1,\ldots ,d\), \({{\varvec{s}}} = (s_1,\ldots ,s_d),\, {{\varvec{t}}}=(t_1,\ldots ,t_d)\), see [42].
The generating function f provides a description of the spectrum of \(T_{{{\varvec{n}}}}(f)\), for \({{\varvec{n}}}\) large enough in the sense of the following definition.
Definition 3
Let \(f:\varOmega \subset \mathbb {R}^d\rightarrow {\mathbb {C}}\) be a measurable function defined on a set \(\varOmega ,\) measurable in the sense of Lebesgue, with finite measure \({{{\bar{\mu }}}}(\varOmega ).\) Moreover, let us assume that \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\) is a sequence of matrices with eigenvalues \(\lambda _j(A_{{{\varvec{n}}}})\) and singular values \(\sigma _j(A_{{{\varvec{n}}}})\), \(j=1,\ldots ,d_{{{\varvec{n}}}},\) and that \(d_{{{\varvec{n}}}}\) is the size of \(A_{{{\varvec{n}}}}\) with \(d_{{{\varvec{n}}}}\rightarrow \infty\), as \({{\varvec{n}}}\rightarrow \infty\), i.e., \(n_i\rightarrow \infty ,\)\(i=1,\ldots ,d.\)
We say that \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\) is distributed asfover\(\varOmega\)in the sense of the eigenvalues, and we write \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\lambda (f,\varOmega ),\) if
for every continuous function F with compact support. In this case, we say that f is the symbol of \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\).
We say that \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\) is distributed asfover\(\varOmega\)in the sense of the singular values, and we write \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\sigma (f,\varOmega ),\) if
for every continuous function F with compact support. In particular, when \(f \equiv 0\) we say that \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\) is a zero-distributed matrix-sequence.
In the following, for the sake of simplicity we will often write \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\lambda f,\)\(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\sigma f\) in place of \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\lambda (f,\varOmega ),\)\(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\sigma (f,\varOmega )\).
Remark 1
If f is smooth enough, an informal interpretation of the limit relation 6 (resp. 7) is that when \({{\varvec{n}}}\) is sufficiently large, then the eigenvalues (resp. singular values) of \(A_{{{\varvec{n}}}}\) can be approximated by a sampling of f (resp. |f|) on a uniform equispaced grid of the domain \(\varOmega\).
For Toeplitz matrix-sequences, the following theorem (due to Szegö, Tilli, Tyrtyshnikov, Zamarashkin, \(\dots\)) holds, cf. [19, 41, 43].
Theorem 5
Let\(\{T_{{{\varvec{n}}}}(f)\}_{{{\varvec{n}}}}\)be a Toeplitz sequence generated by\(f\in L^1([-\pi ,\pi ]^d).\)Then, \(\left\{ T_{{{\varvec{n}}}}(f)\right\} _{{{\varvec{n}}}}\sim _\sigma (f,[-\pi ,\pi ]^d).\)In addition, if fis real-valued, then \(\left\{ T_{{{\varvec{n}}}}(f)\right\} _{{{\varvec{n}}}}\sim _\lambda (f,[-\pi ,\pi ]^d).\)
2.2 GLT class
The formal definition of GLT matrix-sequences is rather technical and involves somewhat cumbersome notation. Therefore, in this subsection we briefly discuss some properties of the GLT class which are sufficient for our aims and we refer the reader to
[17] for more details. Throughout, we use the following notation
to say that the matrix-sequence \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\) is a GLT matrix-sequence with GLT symbol \(\kappa ({{\varvec{x}}},{\varvec{\theta }})\), where \({{\varvec{x}}}=(x_1,\ldots ,x_d)\) are the physical variables and \({\varvec{\theta }}=(\theta _1,\ldots ,\theta _d)\) are the Fourier variables. First we introduce a certain type of diagonal matrices which, as we shall see, come into play when dealing with differential problems with variable coefficients.
Definition 4
Let \(\mathfrak {a}: [0,1]^d \rightarrow {\mathbb {C}}\) be a Riemann-integrable function. The diagonal sampling matrix of order \(n_1 \cdots n_d\) is given by
where \({{{\varvec{j}}}}/{{{\varvec{n}}}}=\left( j_1/n_1,\ldots ,j_d/n_d\right)\).
We list below key features of GLT matrix-sequences which represent a characterization of GLT matrix-sequences. In other words the \(*\)-algebra of matrix-sequences satisfying items GLT1–GLT6 coincides with the whole class of GLT matrix-sequences. We have chosen this way, not only for the sake of brevity and notational simplicity, but also because items GLT1–GLT6 furnish a constructive way for verifying whether a concrete matrix-sequence belongs to the GLT class.
GLT1
Let \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _{\mathrm{GLT}}\kappa .\) Then \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\sigma (\kappa ,G)\). If the matrices \(A_{{{\varvec{n}}}}\) are Hermitian, then it also holds that \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\lambda (\kappa ,G)\).
GLT2
The set of GLT matrix-sequences forms a \(*\)-algebra that is closed under linear combinations, products, inversion, conjugation. In formulas, let \(\{ A_{{{\varvec{n}}}} \}_{{{\varvec{n}}}} \sim _{\mathrm{GLT}} \kappa _1\) and \(\{ B_{{{\varvec{n}}}} \}_{{{\varvec{n}}}} \sim _{\mathrm{GLT}} \kappa _2\), then
Any sequence \(\{ T_{{{\varvec{n}}}}(f) \}_{{{\varvec{n}}}}\) generated by a function \(f \in L^1([-\pi , \pi ]^d)\) is a GLT matrix-sequence with symbol \(\kappa ({{\varvec{x}}}, {\varvec{\theta }}) = f({\varvec{\theta }}).\)
GLT4
Every diagonal sampling matrix-sequence \(\{\mathscr {D}_{{{\varvec{n}}}}(\mathfrak {a})\}_{{{\varvec{n}}}}\) is a GLT matrix-sequence whose symbol is given by \(\kappa ({{\varvec{x}}}, {\varvec{\theta }}) =\mathfrak {a}({{\varvec{x}}}).\)
GLT5
Every zero-distributed matrix-sequence is a GLT matrix-sequence with symbol 0 and viceversa, i.e., \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _\sigma 0\)\(\iff\)\(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _{\mathrm{GLT}}0\).
GLT6
If \(\{A_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\sim _{\mathrm{GLT}}\kappa\) and \(A_{{{\varvec{n}}}}\) is Hermitian for each \({{\varvec{n}}} \in \mathbb {N}^d,\) then \(\{f(A_{{{\varvec{n}}}})\}_{{{\varvec{n}}}}\sim _{\mathrm{GLT}}f(\kappa )\) for every continuous function \(f:{\mathbb {C}}\rightarrow {\mathbb {C}}\).
According to Definition 3, in the presence of a zero-distributed matrix-sequence the singular values of the \({{\varvec{n}}}\)th matrix (weakly) cluster around 0. This is formalized in the following result.
Proposition 1
(
[17, Theorem 3.2]) Let \(\{ A_{{{\varvec{n}}}} \}_{{{\varvec{n}}}}\)be a matrix-sequence with\(A_{{{\varvec{n}}}}\)of size\(d_{{{\varvec{n}}}}\)with\(d_{{{\varvec{n}}}}\rightarrow \infty\), as \({{\varvec{n}}}\rightarrow \infty\). Then\(\{ A_{{{\varvec{n}}}} \}_{{{\varvec{n}}}} \sim _{\sigma } 0\)if and only if there exist two matrix-sequences\(\{ R_{{{\varvec{n}}}} \}_{{{\varvec{n}}}}\) and \(\{ E_{{{\varvec{n}}}}\}_{{{\varvec{n}}}}\)such that\(A_{{{\varvec{n}}}} = R_{{{\varvec{n}}}} + E_{{{\varvec{n}}}}\), and
In this section we review two different definitions of the fractional Laplacian in one dimension and we report their basic properties useful in the sequel. We shall always assume that the fractional Laplacian is applied to a suitable smooth function, say v (for instance, \(v \in L^1(\mathbb {R})\)). In addition, for simplicity, we denote the space variable by x.
Consider the Riesz potential operator that in the 1D case can be formulated as
cf.
[11, 38]. In
[11, Lemma 2.2], under the hypotheses that \(v \in C^5(\mathbb {R})\) and all derivatives up to order five belong to \(L^1(\mathbb {R}),\) Çelik and Duman proved that
where \(\varDelta _{c_1}^\alpha\) denotes a generalization of the integer-order centered differences to the fractional case proposed by Ortigueira in
[30, Definition 3.5], namely
For this reason, the series in (10) converges absolutely for a bounded function \(v \in L^1(\mathbb {R}).\) By exploiting the decay of the coefficients \(\ell _k,\) a “short memory” version of the scheme proposed by Ortigueira has been implemented in [36]. Finally, using the Fourier definition of the fractional Laplacian, in [31] was proved that
We conclude this section by pointing out that several applications require the solution of fractional differential equations expressed in terms of fractional Laplacian multiplied by a certain non-constant coefficient. In such cases, the spatial operator has the following form
with D a non-negative function. Later we also give spectral insights on this operator under the additional hypothesis that D is Riemann integrable.
4 Matrix forms for Laplace operators
Aiming to discretize the fractional Laplace operator in two (or more) dimensions, in the following we always impose absorbing boundary conditions (see [12] for further details). In the one-dimensional case this is equivalent to applying the fractional Laplace operator to functions of the form
Different boundary conditions can also be imposed and the spectral analysis in terms of distribution is quite simplified using the GLT machinery. In fact, the perturbation induced by a different choice of boundary conditions can be represented as a zero-distributed matrix-sequence and hence GLT5 combined with items GLT1-GLT2 represents the key for the related spectral analysis.
We finally emphasize that from a matrix viewpoint the method in Sect. 4.1 amounts in taking the Toeplitz structure generated by a proper ‘fractionalization’ of the symbol of the discrete Laplacian, while the method in Sect. 4.2 amounts in taking the same fractional power applied to a (possibly Toeplitz) structure. It is evident that the first method is computationally much more convenient: the interesting fact is that the two resulting GLT sequences possess the same symbol (so that they differ for a zero-distributed matrix-sequence), even if they look quite different in terms of entries and of global algebraic structure (for instance in the second form the Toeplitz structure is completely lost).
4.1 Toeplitz matrix form
Consider the uniform mesh of the domain [a, b] with step-size \(h = (b-a)/(n+1),\) i.e.,
the Toeplitz matrix related to \(f_\alpha ,\) and taking into account (11) it is a simple matter to verify that \(-h^{- \alpha } T_n(f_\alpha )\) represents the matrix form for the 1D fractional Laplacian described in Sect. 3, cf.
[11, 46].
Now we turn to the Laplace operator in two dimensions. Discretizing in space with a uniform mesh of step-size h in each domain direction and using the 5-point finite-difference stencil leads to the block tridiagonal matrix having the following form:
with \(I_n\) denoting the identity matrix of size n and \(T_n(f_2)\) defined according to (15). \(T_{n,n}(\varphi _2)\) is a 2-level Toeplitz matrix which corresponds to the bivariate symbol (see (2))
Bearing in mind the idea presented above for approximating the 1D fractional Laplacian, in the two-dimensional case we may approximate the fractional Laplacian by considering the matrix \(T_{n,n}(\varphi _\alpha )\) related to the generating function
Another way for constructing an approximation of the 2D fractional Laplacian is based on the 2-level Toeplitz matrix generated by the separable function
where \(T_{n}(f_\alpha )\) is given by (17). Obviously, \(T_{n,n}(\psi _2) =T_{n,n}(\varphi _2).\)
4.2 MTT matrix form
As already mentioned in the introduction, the Matrix Transfer Technique (MTT) is a strategy for discretizing the fractional Laplace operator. Originally introduced in
[21, 22] for the 1D case, the MTT has been also generalized to the two-dimensional case in
[44]. The approximation provided by this method is given by a fractional power of any reasonable discretization of the standard Laplacian. Here we consider two particular discretizations in the one-dimensional case: the one obtained by using centered finite differences and the one corresponding to a generic finite element approximation. We denote by \({\mathscr {L}}^{\, FD}_{\alpha ,n}\) and \({\mathscr {L}}^{\, FE}_{\alpha ,n},\) the corresponding discrete fractional operators provided by the MTT. In formulas (see Sect. 4.1)
where \(M_n\) and \(K_n\) are the usual finite element mass and stiffness matrices. In particular, \(M_n= hT_n \left( (2+\cos \theta )/3\right)\) and \(K_n= h^{-1}T_n(f_2)\) when piecewise linear basis functions are adopted.
Concerning the 2D case, in this work we will focus our spectral analysis on the following MTT matrix forms:
where \(M_{n,n}\) and \(K_{n,n}\) denote the mass and stiffness matrices in the 2D case.
4.3 Matrix form for the case of non-constant coefficient
Once we have a matrix representation for the 1D fractional Laplacian, say \({\mathscr {L}}_{\alpha ,n}\), obtained as explained in the last two subsections (see (17), (21) and (22)), we can easily recover a discretization for the operator (13) on the uniform mesh (14) just taking
where \(\mathscr {D}_{n,n}\) is the diagonal matrix whose non-zero entries are the values of \(D({{\varvec{x}}})\) at the grid points and \(\mathscr {L}_{\alpha ,n,n}\) denotes a matrix form of the 2D fractional Laplacian.
5 Spectral analysis
In this section, divided into three parts, the spectral analysis is performed following the results reported in Sect. 2 concerning the Toeplitz technology and the quite powerful GLT theory. The interesting message we can give is the following: independently of the used method, despite the substantial difference in the structure of the involved matrices, the smallest eigenvalue scales like \(n^{-\alpha }\) and all the related matrix-sequences present the same global eigenvalue distribution.
5.1 Toeplitz case
First we focus our attention on the spectral properties of \(T_n(f_\alpha ).\) Since its generating function \(f_\alpha\) is an even, real-valued and nonnegative function, the matrix \(T_n(f_\alpha )\) is real, symmetric and positive semidefinite. Consequently,
where \(\varLambda _{n,\alpha } ={\rm{ diag} } (\lambda _{1,\alpha },\lambda _{2,\alpha },\dots , \lambda _{n,\alpha })\) is the diagonal matrix containing the eigenvalues of \(T_n(f_\alpha )\) sorted in nondecreasing order and \(Q_{n,\alpha }\) is the orthogonal matrix whose columns are the eigenvectors associated to the eigenvalues \(\lambda _{j,\alpha },\, j=1,2,\dots ,n.\) In addition, considering that \({\mathrm{ess}}\inf f_\alpha =0, {\mathrm{ess}}\sup f_\alpha >0\) and \(f_\alpha \sim |\theta |^\alpha ,\) from Theorem 3 we deduce that
\(T_n(f_\alpha )\) is positive definite for each \(n \in \mathbb {N};\)
the minimum eigenvalue of \(T_n(f_\alpha )\) behaves as follows: \(\lambda _{1,\alpha } \sim 1/n^\alpha .\)
The matrix \((\varLambda _{n,\alpha } \otimes I_n + I_n \otimes \varLambda _{n,\alpha })\) is block diagonal with diagonal blocks, say \(D_j,\) having the following form:
It is worth to observe that since \(\lambda _{1,\alpha }\) and \(\lambda _{n,\alpha }\) are the minimum and the maximum eigenvalues of \(T_{n}(f_\alpha ),\) the condition number in Euclidean norm of the matrix \(T_{n,n}(\psi _\alpha )\) coincides with the one of the matrix \(T_{n}(f_\alpha ),\) i.e.,
Notice that because of (25) and (26), both \(\varphi _\alpha\) and \(\psi _\alpha\) have a zero at the origin of order \(\alpha\) in the sense of Definition 2.
GLT considerations Thanks to Theorem 5 and item GLT3, we can immediately conclude that \(\{T_{n}(f_\alpha )\}_n\sim _{\mathrm{GLT},\lambda} f_\alpha ,\)\(\{T_{n,n}(\varphi _\alpha )\}_n\sim _{\mathrm{GLT},\lambda} \varphi _\alpha ,\)\(\{T_{n,n}(\psi _\alpha )\}_n\sim _{\mathrm{GLT},\lambda} \psi _\alpha .\)
5.2 MTT case
Finite Differences It is well-known that the discretization \(T_n(f_2)\) given in (15) can be diagonalized by means of the discrete sine transform. In formulas, \(T_n(f_2) =\)\(Q_{n,2} \varLambda _{n,2} Q_{n,2},\) where the entries of the symmetric orthogonal matrix \(Q_{n,2}\) are given by
and, for \(j = 1, \ldots , n,\) the non-zero entries of the diagonal matrix \(\varLambda _{n,2}\) are the eignevalues \(\lambda _{j,2} = 2 - 2 \cos ({j \pi }/{(n+1)}).\) This enables to write directly the spectral decomposition of \({\mathscr {L}}^{\, FD}_{\alpha ,n}\) by means of \(Q_{n,2} \varLambda _{n,2}^{\alpha /2} Q_{n,2}\) and to conclude that
Similarly, in two dimensions the matrix \(T_{n,n}(\varphi _2)=T_n(f_2) \otimes I_n + I_n \otimes T_n(f_2)\) can be diagonalized by means of \(Q_{n,2} \otimes Q_{n,2}\), and its diagonal form is \(I_n \otimes \varLambda _{n,2} + \varLambda _{n,2} \otimes I_n\). Therefore, its eigenvalues are all the possible sums \(\lambda _{i,2} + \lambda _{j,2}\), with \(i,j = 1, \ldots , n\) and we can compute \({\mathscr {L}}^{\, FD}_{\alpha ,n,n}\) by means of the decomposition \((Q_{n,2} \otimes Q_{n,2}) (I_n \otimes \varLambda _{n,2} + \varLambda _{n,2} \otimes I_n)^{ \alpha / 2} (Q_{n,2} \otimes Q_{n,2})\) which implies that
and \(\mu _2({\mathscr {L}}^{\, FD}_{\alpha ,n})=\mu _2({\mathscr {L}}^{\, FD}_{\alpha ,n,n})\).
GLT considerations Since \(T_n(f_2)\) is a symmetric positive definite matrix and \(\{T_n(f_2)\}_n\sim _{\mathrm{GLT}}f_2\) by GLT3, we can use GLT6 to conclude that \(\{-h^\alpha {\mathscr {L}}^{\, FD}_{\alpha ,n}\}_n\sim _{\mathrm{GLT}}f_\alpha\). Moreover, \({\mathscr {L}}^{\, FD}_{\alpha ,n}\) is still real symmetric and by GLT1 we also have \(\{-h^\alpha {\mathscr {L}}^{\, FD}_{\alpha ,n}\}_n\sim _{\lambda }f_\alpha\). In other words, \(\{-h^\alpha {\mathscr {L}}^{\, FD}_{\alpha ,n}\}_n\) is a GLT matrix-sequence that shares the same symbol of the Toeplitz sequence \(\{T_n(f_\alpha )\}_n\) obtained by a direct centered finite difference discretization of the fractional Laplacian. As a consequence, by GLT2
which thanks to GLT5 and Proposition 1 is equivalent to say that the matrix-sequence \(\{- h^{\alpha }{\mathscr {L}}^{\, FD}_{\alpha ,n} - T_n(f_\alpha )\}_n\) is weakly clustered at zero.
A similar reasoning proves that \(\{-h^\alpha {\mathscr {L}}^{\, FD}_{\alpha ,n,n}\}_n\sim _{\mathrm{GLT},\lambda} \varphi _\alpha\) and that \(\{-h^{\alpha }{\mathscr {L}}^{\, FD}_{\alpha ,n,n} - T_{n,n}(\varphi _\alpha )\}_n \sim _{{\mathrm {GLT}},\sigma} 0\).
Finite Elements The matrix representation of the 1D standard Laplacian resulting from the finite element method is given by \(C_n=M_n^{-1}K_n.\) Both \(M_n\) and \(K_n\) are real and symmetric and \(M_n\) is positive definite. Considering that \(\tilde{C}_n=M_n^{-1/2}K_nM_n^{-1/2}\) is a real symmetric matrix and
it follows that \(C_n\) is diagonalizable. In particular, when piecewise linear basis functions are adopted, that is \(M_n=hT_n\left( (2+\cos \theta )/3\right)\) and \(K_n=h^{-1}T_n(f_2),\) then \(C_n\) can be still diagonalized by means of \(Q_{n,2}\) and the eigenvalues of both \(C_n\) and \({\mathscr {L}}^{\, FE}_{\alpha ,n}\) are known exactly. Specifically, we have
Similar considerations can be made in the two-dimensional setting. The general case of high-order finite elements is less trivial. For example, in
[14] it has been shown that the matrices \(M_n\) and \(K_n\) do not belong to the same matrix algebra when considering finite elements with maximum regularity of order greater than or equal to 3. In this context, an approximation of the eigenvalues of \({\mathscr {L}}^{\, FE}_{\alpha ,n}\) and \({\mathscr {L}}^{\, FE}_{\alpha ,n,n}\) can be obtained using the notion of symbol, as outlined in the next paragraph.
GLT considerations Here we discuss the case of high-order finite elements with maximum regularity and we exploit the results in [15] where it has been shown that \(\{h^{-1}M_n\}_n\) and \(\{hK_n\}_n\) are both GLT matrix-sequences. We denote the corresponding symbols as \(\it{m}\) and \(\kappa ,\) respectively. Since both \(M_n\) and \(K_n\) are real symmetric, by GLT1 the matrix-sequences \(\{h^{-1}M_n\}_n\) and \(\{hK_n\}_n\) distribute as \(\it{m},\kappa\) also in the eigenvalue sense. In formulas,
Since \(h^{-1}M_n\) is positive definite with minimal eigenvalue well separated from zero (see again
[15]), the corresponding function m is invertible everywhere. For instance, when using piecewise linear elements, \(h^{-1}M_n=T_n\left( (2+\cos \theta )/3\right)\) and hence
on the whole definition domain. Consequently, item GLT2 implies that \(\{h^{2}C_n\}_n \sim _{\mathrm{GLT}} \it{m}^{-1}\kappa =: \chi .\) In addition, from (27) and by recalling that \(\tilde{C}_n\) is real symmetric, by using items GLT1, GLT2, and GLT6 we get
Furthermore, since \(K_n\) is positive semidefinite, also \(\tilde{C}_n\) is positive semidefinite and then \((\tilde{C}_n)^{{\alpha }/{2}}\) is well-defined. Taking into account that \((\tilde{C}_n)^{{\alpha }/{2}}\) is still real symmetric, by GLT6 we infer that
The last equality in (30) comes directly from the definition of matrix function and from the fact that \({{\tilde{C}}}_n\) is symmetric positive semidefinite. More precisely, if we write the diagonal form of \({\tilde{C}}_n\) as \({\tilde{C}}_n=ZJZ^T\), then
Notice that the above reasoning still works in the two-dimensional setting. When replacing \(M_{n}\) and \(K_{n}\) with \(M_{n,n}\) and \(K_{n,n}\) we have
In the case of high-order finite element with a certain fixed regularity the resulting matrix-sequences are (sequences of submatrices of) block GLTs. Analogous results to (31) and (32) follow using the multilevel block GLT theory
[5, 6, 16].
5.3 Non-constant coefficient case
In this section we review how the GLT theory can be used for studying the spectral behavior of the matrix-sequence \(\{-h^\alpha {\mathscr {M}}_{\alpha ,n}\}_n,\) with \({\mathscr {M}}_{\alpha ,n}\) given by (23). In particular, we focus on the case of the finite differences which has already been analyzed in
[13, Proposition 5] and in
[29, Proposition 3.11] and on the finite element one. Everything works in the two-dimensional setting as well, so we skip the details for this case.
Let \(h_\alpha (x,\theta )=D(x)g_\alpha (\theta )\) be the symbol associated to \(-h^{\alpha }{{\mathscr {M}}}_{\alpha ,n}=-h^{\alpha }\mathscr {D}_n{{\mathscr {L}}}_{\alpha ,n},\) where \({{\mathscr {L}}}_{\alpha ,n}\) is one of the discretizations of the 1D fractional Laplacian discussed in the previous sections whose symbol is denoted by \(g_\alpha\). Noticing that \({\mathscr {D}}_n\) is a positive definite diagonal matrix, then
that is \({{\mathscr {M}}}_{\alpha ,n}\) is similar to a real symmetric matrix. Therefore, all the eigenvalues of \({{\mathscr {M}}}_{\alpha ,n}\) are real and by GLT1 we infer \(\left\{ -h^\alpha {{\mathscr {M}}}_{\alpha ,n}\right\} _{n}\sim _\lambda ({\hat{h}}_\alpha ({\hat{x}},\theta ),[0,1]\times [-\pi ,\pi ]),\) where \({\hat{h}}_\alpha ({\hat{x}},\theta )=h_\alpha (a + (b-a){\hat{x}},\theta ).\) After the affine change of variables \(x=a + (b-a){\hat{x}},\)\(\left\{ -h^\alpha {{\mathscr {M}}}_{\alpha ,n}\right\} _{n}\sim _{\lambda }{\hat{h}}_\alpha ({\hat{x}},\theta )\) is equivalent to \(\left\{ -h^\alpha {{\mathscr {M}}}_{\alpha ,n}\right\} _{n}\sim _{\lambda } h_\alpha (x,\theta ).\) Therefore,
it is clear that the symbol \(h_\alpha\) has a zero of order \(\alpha\) at \(\theta =0\), whenever the diffusion coefficient D is bounded and positive.
Summary of spectral results We now summarize all the spectral results obtained by collecting them in two groups, those relating to the one-dimensional case and those relating to the two-dimensional case. Furthermore, we assign to each operator an acronymous that will be useful in the next section.
In this section we numerically check some of the relations we have listed at the end of the previous section. In all our experiments we used the Matlab function eig to compute the eigenvalues. In addition, when finite elements are involved, we opt for \(C^2\) piecewise cubic basis functions.
We start by verifying the spectral relations 1FD-T and 1FE-MTT. Since the symbols involved are even functions, we can restrict to the interval \([0,\pi ]\) and consider a uniform mesh with step-size \(h=\pi /(n+1).\) As shown in Fig. 1, setting \(\alpha =1.3\) and \(n=100,\) there is a good matching between the eigenvalues of the matrices \(T_n(f_\alpha )\) and \(-h^\alpha {\mathscr {L}}^{\, FE}_{\alpha ,n}\), and a sampling of \(f_\alpha\) on the points grid.
Similar results can be obtained when checking 1FD-NC with \(g_\alpha =f_\alpha\), \(\alpha =1.2,\)\(n=100,\) and \(D(x)=\varGamma (3-\alpha )x^\alpha\) or \(D(x)=\exp (8x)\) (refer to Fig. 2).
Consider now the square domain \([0,\pi ]^2\) and define a uniform mesh with step-size \(h=\pi /(n+1)\) in each domain direction. In Fig. 3 we check the validity of 2FD-T-S and 2FE-MTT comparing the spectrum of the matrices \(T_{n,n}(\psi _\alpha )\), \(-h^\alpha {\mathscr {L}}^{\, FE}_{\alpha ,n,n}\) with a sampling of \(\psi _\alpha\), \(\zeta ^{\alpha /2}\), when \(\alpha =1.7\) and \(n=10.\) Also in this two-dimensional example the symbol is describing quite well the spectrum of the considered discretization matrices.
As a final test, in Fig. 4 we compare the contour plots of all the symbols corresponding to two-dimensional discretization matrices, i.e., \(\psi _\alpha\), \(\zeta ^{\alpha /2}\), and \(\varphi _\alpha\), when \(\alpha =1.4\). What can be immediately noticed is that the symbol \(\psi _\alpha\) shows sharper patterns than \(\varphi _\alpha\) and especially \(\zeta ^{\alpha /2}\), when approaching zero. Moreover, we note that the 2FE-MTT symbol is close to zero on a slightly larger portion of the domain than the other two symbols. This results in a worse ill-conditioning of the corresponding discretization matrices and refers to the degree of the approximation space.
Fig. 1
1D case—comparison between the spectrum of the matrices \(T_n(f_\alpha ),\)\(-h^\alpha {\mathscr {L}}^{\, FE}_{\alpha ,n}\) and a sampling of the related symbols \(f_\alpha\) and \(\chi ^{\alpha /2}\) for \(n=100\) and \(\alpha =1.3\)
Fig. 2
1D non-constant coefficient case—comparison between the spectrum of the matrix \(\mathscr {D}_nT_n(f_\alpha )\) and a sampling of the related symbol \(D(x)f_\alpha (\theta )\) for \(n=100\) and \(\alpha =1.2\)
Fig. 3
2D case—comparison between the spectrum of the matrices \(T_{n,n}(\psi _\alpha )\), \(-h^\alpha {\mathscr {L}}^{\, FE}_{\alpha ,n,n}\) and a sampling of the related symbols \(\psi _\alpha\) and \(\zeta ^{\alpha /2}\) for \(n=10\) and \(\alpha =1.7\)
Fig. 4
Contour plots for \(\psi _\alpha\), \(\zeta ^{\alpha /2}\), and \(\varphi _\alpha\) when \(\alpha =1.4\)
×
×
×
×
7 Conclusions
Starting from two different ways of defining the fractional Laplace operator in more than one dimension we have studied the spectral properties of related finite difference and finite element discretization matrices. Precisely, we have analyzed the spectrum/conditioning of
the Toeplitz matrices whose symbol is a proper fraction of the symbol of the standard Laplacian operator;
the matrices obtained by the MTT as fractional powers of both finite difference and finite element approximations of the standard Laplacian.
Furthermore, we have shown that the corresponding matrix-sequences belong to the GLT class. The characterization of all the aforementioned discretization matrix-sequences as GLT matrix-sequences relates to the solution of the corresponding linear systems. Inspired by the GLT-based algorithmic proposals in
[29] for finite difference discretizations of the 2D fractional Laplacian and due to the ill-conditioning observed when considering the 2FE-MTT symbol, in a future work it could be interesting to exploit the GLT structure for the definition of preconditioners suitable for finite element discretizations.
Acknowledgements
Open access funding provided by Università di Pisa within the CRUI-CARE Agreement.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
