More Like this

1. The discontinuous Petrov–Galerkin method

   https://doi.org/10.1017/S0962492924000102  

   Demkowicz, Leszek; Gopalakrishnan, Jay (July 2025, Acta Numerica)

   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
2. Sum factorization for fast integration of DPG matrices on prismatic elements

   https://doi.org/10.1016/j.finel.2020.103385  

   Badger, J; Henneking, S; Demkowicz, L (May 2020, Finite elements in analysis and design)

   null (Ed.)

   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
3. Fast Integration of DPG Matrices Based on Sum Factorization for all the Energy Spaces

   https://doi.org/10.1515/cmam-2018-0205  

   Mora, Jaime; Demkowicz, Leszek (January 2019, Computational methods in applied mathematics)

   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
4. Equivalence between the DPG method and the exponential integrators for linear parabolic problems

   https://doi.org/10.1016/j.jcp.2020.110016  

   Munoz-Matute, J.; Pardo, D.; Demkowicz, L. (July 2021, Journal of computational physics)

   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
5. Rényi Differentially Private ADMM for Non-Smooth Regularized Optimization

   https://doi.org/10.1145/3374664.3375733  

   Chen, Chen; Lee, Jaewoo (March 2020, CODASPY '20: Proceedings of the Tenth ACM Conference on Data and Application Security and Privacy)

   null (Ed.)

   In this paper we consider the problem of minimizing composite objective functions consisting of a convex differentiable loss function plus a non-smooth regularization term, such as $$L_1$$ norm or nuclear norm, under Rényi differential privacy (RDP). To solve the problem, we propose two stochastic alternating direction method of multipliers (ADMM) algorithms: ssADMM based on gradient perturbation and mpADMM based on output perturbation. Both algorithms decompose the original problem into sub-problems that have closed-form solutions. The first algorithm, ssADMM, applies the recent privacy amplification result for RDP to reduce the amount of noise to add. The second algorithm, mpADMM, numerically computes the sensitivity of ADMM variable updates and releases the updated parameter vector at the end of each epoch. We compare the performance of our algorithms with several baseline algorithms on both real and simulated datasets. Experimental results show that, in high privacy regimes (small ε), ssADMM and mpADMM outperform baseline algorithms in terms of classification and feature selection performance, respectively. 

   more » « less