Fast Methods For Non-local Diffusion Model

Solid mechanics is the branch of continuum mechanics that studies the behavior of solid materials, and is fundamental for civil and mechanical en-gineering, for geology, and for many branches of physics such as materials science. The classical theory has been demonstrated to provide a good ap-proximation to the response of real materials down to small length scales. However, the partial differential equations of classical theory do not apply directly on a crack or dislocation, because the classical theory of solid me-chanics is based on the assumption of a continuous distribution of mass within a body, it further assumes that all internal forces are contact forces that act across zero distance. The mathematical description of a solid that follows these assumptions relies on partial differential equations that additionally as-sume sufficient smoothness of the deformation for the PDEs to make sense in either their strong or weak forms. In many cases, such desire for smoothness can not be satisfied, for example, when we deal with fracture or cracks.To overcome this problem, in2000, a non-local diffusion model named Peridynamics proposed by Silling [53] unites the mathematical modeling of continuous media, cracks, and particles within a single framework. In this new framework, the internal forces are no longer contact forces, but long range forces. In fact, these forces deceased sharply with the distance, so to describe the forces at one point, people often choose a finite domain around this point, named horizon. In fact, non-local theories describing the effects of long-range interactions in elastic materials have been known for a long time,[10,28,27,29,30,43,44,50]. However, during the last few years, the non-local diffusion model named "peridynamics" has become topical as a non-local theory. The effectiveness of PD models has already been demonstrated in several sophisticated applications, including the frac-ture and failure of composites, crack instability, the fracture of polycrystal, and nanofiber networks. We refer to [3,6,7,14,18,24,26,31,32,39,41,46,47,53,51,54,59,55,57,56,52,58,60,62] for reviews of recent appli-cations and theoretical development of the peridynamic framework. More recently, rigorous mathematical analysis of the new model is also receiv-ing much attention[39,23,20,21,65]. For a discussion of non-local theo-ries in solid mechanics and their application to problems of damaging, see also [2,9,19,1,42,45,61,64]. Other recent works on non-local theories and their application in elasticity and fracture mechanics can be found in [16,22,25,35,33,36,34,37,49].Peridynamic theory provides an appropriate description of the defor-mation of a continuous body involving discontinuities or other singularities, which cannot be described properly by classical theory of solid mechanics. Many numerical methods have been proposed to solve this new model. In par-ticular, finite element methods have been developed for peridynamic models [15,24,47] with proved quasi-optimal order error estimates [23,65]. How-ever, the operators in the peridynamic models are nonlocal, so the resulting numerical methods generate dense or full stiffness matrices. Gaussian types of direct solvers were traditionally used solve these problems, which requires O(N3) of operations and O(N2) of memory where N is the number of spa-tial nodes. This imposes significant computational and memory challenge for a peridynamic model, especially for problems in multiple space dimensions. Comparing with the classic theory, the new nonlocal model does have kinds of advantages, however it has to pay the price of its nonlocal property.A simplified model, which assumes that the horizon of the material ε=O(N-1), was proposed to reduce the computational cost and memory requirement to O(N). However, the drawback is that the corresponding error estimate becomes one-order suboptimal. Furthermore, the assumption of ε=O(N-1) does not seem to be physically reasonable since the horizon ε represents a physical property of the material that should not depend on computational mesh size.In this paper we propose a series of fast method to reduce the computa-tional efficiency and storage efficiency without any loss of accuracy. Firstly study a fast Galerkin method for the (non-simplified) steady linear micro-elastic whole-field diffusion model. By fully utilizing the symmetric quasi-Toeplitz structure of the stiffness matrix and the fast Fourier transform, the new method reduces the computational in each iteration of conjugate gradi-ent method from O(N2) to O(N log N) and memory requirement from O(N2) to O(N). Considering that each entry in the stiffness matrix involves2N-folds of integration in N dimensional case, which makes the evaluation of the stiffness matrix more expensive, we propose a fast collocation method which reduce the2N-folds of integration to N-folds of integration, while still re-main the quasi-Toeplitz structure so that we can apply the fast matrix-vector computation in each iteration.Also we consider the fast collocation method on a special non-uniform mesh grid, i.e., a geometric decreasing grid, and we find that the stiffness matrix still have the quasi-Toeplitz matrix structure, the stiff matrix can be split into a nonsymmetric toeplitz matrix and a sparse matrix, so we can develop a fast Generalized minimal residual method(GMRES). Moreover, we generalize this fast collocation method to the high dimension case and the model with a general form kernel function. We have proved that in these cases the stiff matrices have the block-Toeplitz-Toeplitz-block or block-Toeplitz-block-Toeplitz-Toeplitz-block structure, which can be utilized to get the corresponding high dimension fast collocation method, combining the fast two-dimension or three-dimension Fourier transform.This article is based on the fast method for nonlocal diffusion model. We mainly discussed the fast finite element method for whole-field micro-elastic linear diffusion model on one dimension, and also proposed a fast-collocation method in one dimension, two dimension and three dimension for nonlocal models with general kernel functions. Also we give a series of numerical experiment to show that these new fast method greatly improve the computing efficiency and storage efficiency.In Chapter1, we give the mathematical model which is discussed in this paper and introduce the physical background of the nonlocal diffusion model. Also we discuss the nonlocal property of this model, and show the motivation for developing these fast methods. Then we introduce the theoretical work which has been done, including the error estimates and the equivalence with Soblev space for different kernel function.In Chapter2, we discuss the fast finite element method with uniform grid for full-field diffusion model, by fully utilizing the structure of the stiffness matrix, the fast finite element method reduces the computational cost from O(N3) to O(N log2N) and memory requirement from O(N2) to O(N), com-paring with direct Gaussion type solver. The numerical experiment shows that the fast method works well and greatly improves the computational efficiency and storage efficiency, without any loss of accuracy.In Chapter3, Considering that each entry in the stiffness matrix involves two-folds of integration in finite element method, which makes the evaluation of the stiffness matrix very expensive, we proposed a fast collocation method in this part. Further, we develop a fast collocation method on geometry decreasing grids, thus show that a fast method can also be applied on a non-uniform grid.In Chapter4, we generalize the fast collocation method to two dimension model whose kernel function are of general form and whose horizon’s shape is circle or rectangle. And we prove that the stiff matrix always keep the block-Toeplitz-Toeplitz-block structure even for non-local model with general kernel function. The numerical experiment verifies our conclusion.In Chapter5, we generalize the fast collocation method to three dimen-sion model, which is the model of real material. We prove that the stiff matrix of three dimension model is a block-Toeplitz-block-Toeplitz-Toeplitz-block matrix, and by utilizing the structure of the stiffness matrix and three dimension fast Fourier transform, we reduce the computation in each itera-tion from O(N2) to O(N log N), here N is the number of unknown.