We present a simple solver of the fractional Laplacian based on the hypersingular integral representation. Through singularity subtraction, we obtain a regularized integrand that is amenable to the trapezoidal rule with equispaced nodes. The resulting quadrature scheme gives a discrete operator on a regular grid that is translation-invariant and thus can be applied quickly with the fast Fourier transform. For discretizations of problems related to space-fractional diffusion on bounded domains, we observe that the underlying linear system can be efficiently solved via preconditioned Krylov methods with a preconditioner based on the finite-difference (non-fractional) Laplacian. We show numerical results illustrating the error of our simple scheme as well the efficiency of our preconditioning approach, both for the elliptic (steady-state) fractional diffusion problem and the time-dependent problem.
Notable schemes for discretizing the fractional Laplacian based on different ideas include work based on the Caffarelli-Silvestre extension @cite_15 @cite_41 @cite_13 , finite-element-based approaches @cite_48 @cite_17 @cite_8 @cite_43 @cite_30 , and work on spectral approaches @cite_19 @cite_11 @cite_14 . General references for fractional Laplacians on bounded domains include, e.g., Ros-Oton @cite_10 , D'Elia and Gunzburger @cite_38 , Felsinger @cite_4 , and @cite_0 .
@cite_30 @cite_38 @cite_11 @cite_14 @cite_4 @cite_8 @cite_41 @cite_48 @cite_10 @cite_0 @cite_43 @cite_19 @cite_15 @cite_13 @cite_17
2785762403 2511053218 2172034033 2734896008 2463117017 1861554096 2148070710 2963110350 2073656615 1994393928 857387926 2964122166 2080219236 2065254635 2061754404
The fractional Laplacian in R^d has multiple equivalent characterizations. Moreover, in bounded domains, boundary conditions must be incorporated in these characterizations in mathematically distinct ways, and there is currently no consensus in the literature as to which definition of the fractional Laplacian in bounded domains is most appropriate for a given application. The Riesz (or integral) definition, for example, admits a nonlocal boundary condition, where the value of a function u(x) must be prescribed on the entire exterior of the domain in order to compute its fractional Laplacian. In contrast, the spectral definition requires only the standard local boundary condition. These differences, among others, lead us to ask the question: "What is the fractional Laplacian?" We compare several commonly used definitions of the fractional Laplacian (the Riesz, spectral, directional, and horizon-based nonlocal definitions), and we use a quantitative approach to identify their practical differences. In this work, we provide a quantitative assessment of new numerical methods as well as available state-of-the-art methods for discretizing the fractional Laplacian, and we present new results on the differences in features, regularity, and boundary behaviors of solutions to equations posed with these different definitions. We present stochastic interpretations and demonstrate the equivalence between some recent formulations. Through our efforts, we aim to further engage the research community in open problems and assist practitioners in identifying the most appropriate definition and computational approach to use for their mathematical models in addressing anomalous transport in diverse applications. This paper presents regularity results and associated high order numerical methods for one-dimensional fractional-Laplacian boundary-value problems. On the basis of a factorization of solutions as a product of a certain edge-singular weight ω times a "regular" unknown, a characterization of the regularity of solutions is obtained in terms of the smoothness of the corresponding right-hand sides. In particular, for right-hand sides which are analytic in a Bernstein ellipse, analyticity in the same Bernstein ellipse is obtained for the regular'' unknown. Moreover, a sharp Sobolev regularity result is presented which completely characterizes the co-domain of the fractional-Laplacian operator in terms of certain weighted Sobolev spaces introduced in (Babuska and Guo, SIAM J. Numer. Anal. 2002). The present theoretical treatment relies on a full eigendecomposition for a certain weighted integral operator in terms of the Gegenbauer polynomial basis. The proposed Gegenbauer-based Nystrom numerical method for the fractional-Laplacian Dirichlet problem, further, is significantly more accurate and efficient than other algorithms considered previously. The sharp error estimates presented in this paper indicate that the proposed algorithm is spectrally accurate, with convergence rates that only depend on the smoothness of the right-hand side. In particular, convergence is exponentially fast (resp. faster than any power of the mesh-size) for analytic (resp. infinitely smooth) right-hand sides. The properties of the algorithm are illustrated with a variety of numerical results. The operator square root of the Laplacian (−△) 1 2 can be obtained from the harmonic extension problem to the upper half space as the operator that maps the Dirichlet boundary condition to the Neumann condition. In this paper we obtain similar characterizations for general fractional powers of the Laplacian and other integro-differential operators. From those characterizations we derive some properties of these integro-differential equations from purely local arguments in the extension problems. We propose a new nonconforming finite element algorithm to approximate the solution to the elliptic problem involving the fractional Laplacian. We first derive an integral representation of the bilinear form corresponding to the variational problem. The numerical approximation of the action of the corresponding stiffness matrix consists of three steps: (i) apply a sinc quadrature scheme to approximate the integral representation by a finite sum where each term involves the solution of an elliptic partial differential equation defined on the entire space, (ii) truncate each elliptic problem to a bounded domain, (iii) use the finite element method for the space approximation on each truncated domain. The consistency error analysis for the three steps is discussed together with the numerical implementation of the entire algorithm. The results of computations are given illustrating the error behavior in terms of the mesh size of the physical domain, the domain truncation parameter and the quadrature spacing parameter. Approximations of solutions of fractional Laplacian equations on bounded domains are considered. Such equations allow global interactions between points separated by arbitrarily large distances. Two approximations are introduced. First, interactions are localized so that only points less than some specified distance, referred to as the interaction radius, are allowed to interact. The resulting truncated problem is a special case of a more general nonlocal diffusion problem. The second approximation is the spatial discretization of the related nonlocal diffusion problem. A recently developed abstract framework for asymptotically compatible schemes is applied to prove convergence results for solutions of the truncated and discretized problem to the solutions of the fractional Laplacian problems. Intermediate results also provide new convergence results for the nonlocal diffusion problem. Special attention is paid to limiting behaviors as the interaction radius increases and the spatial grid size decreases, regardless of how these parameters may or may not be dependent. In particular, we show that conforming Galerkin finite element approximations of the nonlocal diffusion equation are always asymptotically compatible schemes for the corresponding fractional Laplacian model as the interaction radius increases and the grid size decreases. The results are developed with minimal regularity assumptions on the solution and are applicable to general domains and general geometric meshes with no restriction on the space dimension and with data that are only required to be square integrable. Furthermore, our results also solve an open conjecture given in the literature about the convergence of numerical solutions on a fixed mesh as the interaction radius increases. We show the analytic continuation of the resolvent of the Laplacian on asymptotically hyperbolic spaces on differential forms, including high energy estimates in strips. This is achieved by placing the spectral family of the Laplacian within the framework developed, and applied to scalar problems, by the author recently, roughly by extending the problem across the boundary of the compactification of the asymptotically hyperbolic space in a suitable manner. The main novelty is that the non-scalar nature of the operator is dealt with by relating it to a problem on an asymptotically Minkowski space to motivate the choice of the extension across the conformal boundary. This paper presents a new spectral partitioning formulation which directly incorporates vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with arbitrary vertex size improve by 22 when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with arbitrary-size and unit-size vertices; average improvements of 17 and 18 are observed for graphs with arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently. Abstract Scalings in which the graph Laplacian approaches a differential operator in the large graph limit are used to develop understanding of a number of algorithms for semi-supervised learning; in particular, the probit algorithm, level set and kriging methods. Both optimization and Bayesian approaches are considered, based around a regularizing quadratic form found from an affine transformation of the Laplacian, raised to a possibly fractional, exponent. Conditions on the parameters defining this quadratic form are identified under which well-defined limiting continuum analogues of the optimization and Bayesian semi-supervised learning problems may be found, thereby shedding light on the design of algorithms in the large graph setting. The large graph limits of the optimization formulations are tackled through Γ-convergence, using the recently introduced T L p metric. The small labeling noise limits of the Bayesian formulations are also identified, and contrasted with pre-existing harmonic function approaches to the problem. In the present paper we analyze a class of tensor-structured preconditioners for the multidimensional second-order elliptic operators in ℝ d , d≥2. For equations in a bounded domain, the construction is based on the rank-R tensor-product approximation of the elliptic resolvent ℬ R ≈(ℒ−λ I)−1, where ℒ is the sum of univariate elliptic operators. We prove the explicit estimate on the tensor rank R that ensures the spectral equivalence. For equations in an unbounded domain, one can utilize the tensor-structured approximation of Green’s kernel for the shifted Laplacian in ℝ d , which is well developed in the case of nonoscillatory potentials. For the oscillating kernels e −i κ‖x‖ ‖x‖, x∈ℝ d , κ∈ℝ+, we give constructive proof of the rank-O(κ) separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on an n×n×n grid that requires only O(κ |log e|2 n) reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost O(n 2), even in the case κ=O(n). We present a new method to convert the geometry of a mesh into frequency space. The eigenfunctions of the Laplace-Beltrami operator are used to define Fourier-like function basis and transform. Since this generalizes the classical Spherical Harmonics to arbitrary manifolds, the basis functions will be called Manifold Harmonics. It is well known that the eigenvectors of the discrete Laplacian define such a function basis. However, important theoretical and practical problems hinder us from using this idea directly. From the theoretical point of view, the combinatorial graph Laplacian does not take the geometry into account. The discrete Laplacian (cotan weights) does not have this limitation, but its eigenvectors are not orthogonal. From the practical point of view, computing even just a few eigenvectors is currently impossible for meshes with more than a few thousand vertices. In this paper, we address both issues. On the theoretical side, we show how the FEM (Finite Element Modeling) formulation defines a function basis which is both geometry-aware and orthogonal. On the practical side, we propose a band-by-band spectrum computation algorithm and an out-of-core implementation that can compute thousands of eigenvectors for meshes with up to a million vertices. Finally, we demonstrate some applications of our method to interactive convolution geometry filtering and interactive shading design. In this paper, we examine a spectral clustering algorithm for similarity graphs drawn from a simple random graph model, where nodes are allowed to have varying degrees, and we provide theoretical bounds on its performance. The random graph model we study is the Extended Planted Partition (EPP) model, a variant of the classical planted partition model. The standard approach to spectral clustering of graphs is to compute the bottom k singular vectors or eigenvectors of a suitable graph Laplacian, project the nodes of the graph onto these vectors, and then use an iterative clustering algorithm on the projected nodes. However a challenge with applying this approach to graphs generated from the EPP model is that unnormalized Laplacians do not work, and normalized Laplacians do not concentrate well when the graph has a number of low degree nodes. We resolve this issue by introducing the notion of a degree-corrected graph Laplacian. For graphs with many low degree nodes, degree correction has a regularizing eect on the Laplacian. Our spectral clustering algorithm projects the nodes in the graph onto the bottom k right singular vectors of the degree-corrected random-walk Laplacian, and clusters the nodes in this subspace. We show guarantees on the performance of this algorithm, demonstrating that it outputs the correct partition under a wide range of parameter values. Unlike some previous work, our algorithm does not require access to any generative parameters of the model. The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs) of a graph Laplacian matrix have been widely used for spectral clustering and community detection. However, in real-life applications, the number of clusters or communities (say, K) is generally unknown a priori. Consequently, the majority of the existing methods either choose K heuristically or they repeat the clustering method with different choices of K and accept the best clustering result. The first option, more often, yields suboptimal result, while the second option is computationally expensive. In this work, we propose an incremental method for constructing the eigenspectrum of the graph Laplacian matrix. This method leverages the eigenstructure of graph Laplacian matrix to obtain the Kth smallest eigenpair of the Laplacian matrix given a collection of all previously computed (K-1 ) smallest eigenpairs. Our proposed method adapts the Laplacian matrix such that the batch eigenvalue decomposition problem transforms into an efficient sequential leading eigenpair computation problem. As a practical application, we consider user-guided spectral clustering. Specifically, we demonstrate that users can utilize the proposed incremental method for effective eigenpair computation and for determining the desired number of clusters based on multiple clustering metrics. We introduce a new methodology for the numerical solution of Partial Differential Equations in general spatial domains: our algorithms are based on the use of the well-known Alternating Direction Implicit (ADI) approach in conjunction with a certain "Fourier continuation" (FC) method for the resolution of the Gibbs phenomenon. Unlike previous alternating direction methods of order higher than one, which can only deliver unconditional stability for rectangular domains, the present high-order algorithms possess the desirable property of unconditional stability for general domains; the computational time required by our algorithms to advance a solution by one time-step, in turn, grows in an essentially linear manner with the number of spatial discretization points used. In this paper we demonstrate the FC-AD methodology through a variety of examples concerning the Heat and Laplace Equations in two and three-dimensional domains with smooth boundaries. Applications of the FC-AD methodology to Hyperbolic PDEs together with a theoretical discussion of the method will be put forth in a subsequent contribution. The numerical examples presented in this text demonstrate the unconditional stability and high-order convergence of the proposed algorithms, as well the very significant improvements they can provide (in one of our examples we demonstrate a one thousand improvement factor) over the computing times required by some of the most efficient alternative general-domain solvers. We develop an exponentially accurate fractional spectral collocation method for solving steady-state and time-dependent fractional PDEs (FPDEs). We first introduce a new family of interpolants, called fractional Lagrange interpolants, which satisfy the Kronecker delta property at collocation points. We perform such a construction following a spectral theory recently developed in [M. Zayernouri and G. E. Karniadakis, J. Comput. Phys., 47 (2013), pp. 2108--2131] for fractional Sturm--Liouville eigenproblems. Subsequently, we obtain the corresponding fractional differentiation matrices, and we solve a number of linear FODEs in addition to linear and nonlinear FPDEs to investigate the numerical performance of the fractional collocation method. We first examine space-fractional advection-diffusion problem and generalized space-fractional multiterm FODEs. Next, we solve FPDEs, including the time- and space-fractional advection-diffusion equation, time- and space-fractional multiterm FPDEs, and finally the space... Abstract Let M be a finite graph in the plane and let Me be a domain that looks like the e-fattened graph M (exact conditions on the domain are given). It is shown that the spectrum of the Neumann Laplacian on Me converges when e → 0 to the spectrum of an ODE problem on M. The presence of an electromagnetic field is also allowed. Considerations of this kind arise naturally in mesoscopic physics and other areas of physics and chemistry. The results of the paper extend the ones previously obtained by J. Rubinstein and M. Schatzman.