An official website of the United States government
Numerical integration of the stiffness matrix in higher-order finite element (FE) methods is recognized as one of the heaviest computational tasks in an FE solver. The problem becomes even more relevant when computing the Gram matrix in the algorithm of the Discontinuous Petrov Galerkin (DPG) FE methodology. Making use of 3D tensor-product shape functions, and the concept of sum factorization, known from standard high-order FE and spectral methods, here we take advantage of this idea for the entire exact sequence of FE spaces defined on the hexahedron. The key piece to the presented algorithms is the exact sequence for the one-dimensional element, and use of hierarchical shape functions. Consistent with existing results, the presented algorithms for the integration of H1, H(curl), H(div), and L2 inner products, have the O(p7) computational complexity in contrast to the O(p9) cost of conventional integration routines. Use of Legendre polynomials for shape functions is critical in this implementation. Three boundary value problems under different variational formulations, requiring combinations of H1, H(div) and H(curl) test shape functions, were chosen to experimentally assess the computation time for constructing DPG element matrices, showing good correspondence with the expected rates.
more »
« less
Sum factorization for fast integration of DPG matrices on prismatic elements
Higher order finite element (FE) methods provide significant advantages in a number of applications such as wave propagation, where high order shape functions help to mitigate pollution (dispersion) error. However, classical assembly of higher order systems is computationally burdensome, requiring the evaluation of many point quadrature schemes. When the Discontinuous Petrov-Galerkin (DPG) FE methodology is employed, the use of an enriched test space further increases the computational burden of system assembly, increasing the relevance of improved assembly techniques. Sum factorization—a technique that exploits the tensorproduct structure of shape functions to accelerate numerical integration—was proposed in Ref. [10] for the assembly of DPG matrices on hexahedral elements that reduced the computational complexity from order (p9) to (p7) (where p denotes polynomial order). In this work we extend the concept of sum factorization to the construction of DPG matrices on prismatic elements by expressing prism shape functions as tensor products of 2D simplex and 1D interval shape functions. Unexpectedly, the resulting sum factorization routines on partially-tensorized prism shape functions achieve the same (p7) complexity as sum factorization on fully-tensorized hexahedra shape functions (as products of 1D interval shape functions) presented in Ref. [10]. Throughout this work we adhere to the theory of exact sequence energy spaces, proposing sum factorization routines for each of the 3D FE exact sequence energy spaces—H1, H(curl), H(div), and L2. Computational results for construction of the DPG Gram matrix on a prismatic element in each exact sequence energy space are presented, corroborating the expected (p7) complexity. Additionally, construction of the DPG system for an ultraweak Maxwell problem on a prismatic element is considered and a partially-tensorized sum factorization for hexahedral elements is proposed to improve implementational compatibility between hexahedral and prismatic elements.
more »
« less
- Award ID(s):
- 1819101
- PAR ID:
- 10233835
- Date Published:
- Journal Name:
- Finite elements in analysis and design
- Volume:
- 172
- ISSN:
- 0168-874X
- Page Range / eLocation ID:
- 12
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The Discontinuous Petrov-Galerkin (DPG) method and the exponential integrators are two well establishednumerical methods for solving Partial Differential Equations (PDEs) and stiff systems of Ordinary Differential Equations (ODEs), respectively. In this work, we apply the DPG method in the time variable for linear parabolic problems and we calculate the optimal test functions analytically. We show that the DPG method in time is equivalent to exponential integrators for the trace variables, which are decoupled from the interior variables. In addition, the DPG optimal test functions allow us to compute the approximated solutions in the time element interiors. This DPG method in time allows to construct a posteriori error estimations in order to perform adaptivity. We generalize this novel DPG-based time-marching scheme to general first order linear systems of ODEs. We show the performance of the proposed method for 1D and 2D +time linear parabolic PDEs after discretizing in space by the finite element method.more » « less
-
In this article, we present a three-dimensional anisotropic hp-mesh refinement strategy for ultraweak discontinuous Petrov-Galerkin (DPG) formulations with optimal test functions. The refinement strategy utilizes the built-in residual-based error estimator accompanying the DPG discretization. The refinement strategy is a two-step process: (a) use the built-in error estimator to mark and isotropically hp-refine elements of the (coarse) mesh to generate a finer mesh; (b) use the reference solution on the finer mesh to compute optimal ℎ-and 𝑝-refinements of the selected elements in the coarse mesh. The process is repeated with coarse and fine mesh being generated in every adaptation cycle, until a prescribed error tolerance is achieved. We demonstrate the performance of the proposed refinement strategy using several numerical examples on hexahedral meshes.more » « less
-
The discontinuous Petrov–Galerkin (DPG) method is a Petrov–Galerkin finite element method with test functions designed for obtaining stability. These test functions are computable locally, element by element, and are motivated by optimal test functions which attain the supremum in an inf-sup condition. A profound consequence of the use of nearly optimal test functions is that the DPG method can inherit the stability of the (undiscretized) variational formulation, be it coercive or not. This paper combines a presentation of the fundamentals of the DPG ideas with a review of the ongoing research on theory and applications of the DPG methodology. The scope of the presented theory is restricted to linear problems on Hilbert spaces, but pointers to extensions are provided. Multiple viewpoints to the basic theory are provided. They show that the DPG method is equivalent to a method which minimizes a residual in a dual norm, as well as to a mixed method where one solution component is an approximate error representation function. Being a residual minimization method, the DPG method yields Hermitian positive definite stiffness matrix systems even for non-self-adjoint boundary value problems. Having a built-in error representation, the method has the out-of-the-box feature that it can immediately be used in automatic adaptive algorithms. Contrary to standard Galerkin methods, which are uninformed about test and trial norms, the DPG method must be equipped with a concrete test norm which enters the computations. Of particular interest are variational formulations in which one can tailor the norm to obtain robust stability. Key techniques to rigorously prove convergence of DPG schemes, including construction of Fortin operators, which in the DPG case can be done element by element, are discussed in detail. Pointers to open frontiers are presented.more » « less
-
The Finite Element Method (FEM) is widely used to solve discrete Partial Differential Equations (PDEs) in engineering and graphics applications. The popularity of FEM led to the development of a large family of variants, most of which require a tetrahedral or hexahedral mesh to construct the basis. While the theoretical properties of FEM basis (such as convergence rate, stability, etc.) are well understood under specific assumptions on the mesh quality, their practical performance, influenced both by the choice of the basis construction and quality of mesh generation, have not been systematically documented for large collections of automatically meshed 3D geometries. We introduce a set of benchmark problems involving most commonly solved elliptic PDEs, starting from simple cases with an analytical solution, moving to commonly used test problem setups, and using manufactured solutions for thousands of real-world, automatically meshed geometries. For all these cases, we use state-of-the-art meshing tools to create both tetrahedral and hexahedral meshes, and compare the performance of different element types for common elliptic PDEs. The goal of this benchmark is to enable comparison of complete FEM pipelines, from mesh generation to algebraic solver, and exploration of relative impact of different factors on the overall system performance. As a specific application of our geometry and benchmark dataset, we explore the question of relative advantages of unstructured (triangular/ tetrahedral) and structured (quadrilateral/hexahedral) discretizations. We observe that for Lagrange-type elements, while linear tetrahedral elements perform poorly, quadratic tetrahedral elements perform equally well or outperform hexahedral elements for our set of problems and currently available mesh generation algorithms. This observation suggests that for common problems in structural analysis, thermal analysis, and low Reynolds number flows, high-quality results can be obtained with unstructured tetrahedral meshes, which can be created robustly and automatically. We release the description of the benchmark problems, meshes, and reference implementation of our testing infrastructure to enable statistically significant comparisons between different FE methods, which we hope will be helpful in the development of new meshing and FEA techniques.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1016/j.finel.2020.103385
