We develop a method for generating degree-of-freedom maps for arbitrary order finite element spaces for any cell shape. The approach is based on the composition of permutations and transformations by cell sub-entity. Current approaches to generating degree-of-freedom maps for arbitrary order problems typically rely on a consistent orientation of cell entities that permits the definition of a common local coordinate system on shared edges and faces. However, while orientation of a mesh is straightforward for simplex cells and is a local operation, it is not a strictly local operation for quadrilateral cells and in the case of hexahedral cells not all meshes are orientable. The permutation and transformation approach is developed for a range of element types, including Lagrange, and divergence- and curl-conforming elements, and for a range of cell shapes. The approach is local and can be applied to cells of any shape, including general polytopes and meshes with mixed cell types. A number of examples are presented and the developed approach has been implemented in an open-source finite element library.
相關內容
In the Geometric Median problem with outliers, we are given a finite set of points in d-dimensional real space and an integer m, the goal is to locate a new point in space (center) and choose m of the input points to minimize the sum of the Euclidean distances from the center to the chosen points. This problem can be solved "almost exactly" in polynomial time if d is fixed and admits an approximation scheme PTAS in high dimensions. However, the complexity of the problem was an open question. We prove that, if the dimension of space is not fixed, Geometric Median with outliers is strongly NP-hard, does not admit approximation schemes FPTAS unless P=NP, and is W[1]-hard with respect to the parameter m. The proof is done by a reduction from the Independent Set problem. Based on a similar reduction, we also get the NP-hardness of closely related geometric 2-clustering problems in which it is required to partition a given set of points into two balanced clusters minimizing the cost of median clustering. Finally, we study Geometric Median with outliers in $\ell_\infty$ space and prove the same complexity results as for the Euclidean problem.
Given two points A,B in the plane, the locus of all points P for which the angles at A and B in the triangle A,B,P have a constant sum is a circular arc, by Thales' theorem. We show that the difference of these angles is kept a constant by points P on a hyperbola (albeit with foci different from A and B). Whereas hyperbolae are well-known to maintain a constant difference between the distances to their foci, the above angle property seems not to be widely known. The question was motivated by recent work by Alegr\'ia et al. and De Berg et al. on Voronoi diagrams of turning rays.
The favored phase field method (PFM) has encountered challenges in the finite strain fracture modeling of nearly or truly incompressible hyperelastic materials. We identified that the underlying cause lies in the innate contradiction between incompressibility and smeared crack opening. Drawing on the stiffness-degradation idea in PFM, we resolved this contradiction through loosening incompressible constraint of the damaged phase without affecting the incompressibility of intact material. By modifying the perturbed Lagrangian approach, we derived a novel mixed formulation. In numerical aspects, the finite element discretization uses the classical Q1/P0 and high-order P2/P1 schemes, respectively. To ease the mesh distortion at large strains, an adaptive mesh deletion technology is also developed. The validity and robustness of the proposed mixed framework are corroborated by four representative numerical examples. By comparing the performance of Q1/P0 and P2/P1, we conclude that the Q1/P0 formulation is a better choice for finite strain fracture in nearly incompressible cases. Moreover, the numerical examples also show that the combination of the proposed framework and methodology has vast potential in simulating complex peeling and tearing problems
We introduce and analyse a fully discrete approximation for a mathematical model for the solidification and liquidation of materials of negligible specific heat. The model is a two-sided Mullins--Sekerka problem. The discretization uses finite elements in space and an independent parameterization of the moving free boundary. We prove unconditional stability and exact volume conservation for the introduced scheme. Several numerical simulations, including for nearly crystalline surface energies, demonstrate the practicality and accuracy of the presented numerical method.
In this paper, we present a communication-efficient federated learning framework inspired by quantized compressed sensing. The presented framework consists of gradient compression for wireless devices and gradient reconstruction for a parameter server (PS). Our strategy for gradient compression is to sequentially perform block sparsification, dimensional reduction, and quantization. Thanks to gradient sparsification and quantization, our strategy can achieve a higher compression ratio than one-bit gradient compression. For accurate aggregation of the local gradients from the compressed signals at the PS, we put forth an approximate minimum mean square error (MMSE) approach for gradient reconstruction using the expectation-maximization generalized-approximate-message-passing (EM-GAMP) algorithm. Assuming Bernoulli Gaussian-mixture prior, this algorithm iteratively updates the posterior mean and variance of local gradients from the compressed signals. We also present a low-complexity approach for the gradient reconstruction. In this approach, we use the Bussgang theorem to aggregate local gradients from the compressed signals, then compute an approximate MMSE estimate of the aggregated gradient using the EM-GAMP algorithm. We also provide a convergence rate analysis of the presented framework. Using the MNIST dataset, we demonstrate that the presented framework achieves almost identical performance with the case that performs no compression, while significantly reducing communication overhead for federated learning.
We examine the following problem: given a collection of Clifford gates, describe the set of unitaries generated by circuits composed of those gates. Specifically, we allow the standard circuit operations of composition and tensor product, as well as ancillary workspace qubits as long as they start and end in states uncorrelated with the input, which rule out common "magic state injection" techniques that make Clifford circuits universal. We show that there are exactly 57 classes of Clifford unitaries and present a full classification characterizing the gate sets which generate them. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets. The classification uses, at its center, a reinterpretation of the tableau representation of Clifford gates to give circuit decompositions, from which elementary generators can easily be extracted. The 57 different classes are generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.
We analyse the interpolation properties of 2D and 3D low order virtual element face and edge spaces, which generalize N\'ed\'elec and Raviart-Thomas polynomials to polygonal-polyhedral meshes. Moreover, we investigate the stability properties of the associated $L^2$ discrete bilinear forms, which typically appear in the virtual element discretization of problems in electromagnetism.
We propose and analyse an augmented mixed finite element method for the Navier--Stokes equations written in terms of velocity, vorticity, and pressure with non-constant viscosity and no-slip boundary conditions. The weak formulation includes least-squares terms arising from the constitutive equation and from the incompressibility condition, and we use a fixed point strategies to show the existence and uniqueness of continuous and discrete solutions under the assumption of sufficiently small data. The method is constructed using any compatible finite element pair (conforming or non-conforming) for velocity and pressure as dictated by Stokes inf-sup stability, while for vorticity any generic discrete space (of arbitrary order) can be used. We establish optimal a priori error estimates. Finally, we provide a set of numerical tests in 2D and 3D illustrating the behaviour of the scheme as well as verifying the theoretical convergence rates.
Diffuse Optical Tomography (DOT) is an emerging technology in medical imaging which employs near-infra-red light to estimate the distribution of optical coefficients in biological tissues for diagnostic purposes. The DOT approach involves the solution of a severely ill-posed inverse problem, for which regularization techniques are mandatory in order to achieve reasonable results. Traditionally, regularization techniques put a variance prior on the desired solution/gradient via regularization parameters, whose choice requires a fine tuning. In this work we explore deep learning techniques in a fully data-driven approach, able of reconstructing the generating signal (absorption coefficient) in an automated way. We base our approach on the so-called learned Singular Value Decomposition, which has been proposed for general inverse problems, and we tailor it to the DOT application. We test our approach on a 2D synthetic dataset, with increasing levels of noise on the measure.
We study timed systems in which some timing features are unknown parameters. Parametric timed automata (PTAs) are a classical formalism for such systems but for which most interesting problems are undecidable. Notably, the parametric reachability emptiness problem, i.e., the emptiness of the parameter valuations set allowing to reach some given discrete state, is undecidable. Lower-bound/upper-bound parametric timed automata (L/U-PTAs) achieve decidability for reachability properties by enforcing a separation of parameters used as upper bounds in the automaton constraints, and those used as lower bounds. In this paper, we first study reachability. We exhibit a subclass of PTAs (namely integer-points PTAs) with bounded rational-valued parameters for which the parametric reachability emptiness problem is decidable. Using this class, we present further results improving the boundary between decidability and undecidability for PTAs and their subclasses such as L/U-PTAs. We then study liveness. We prove that: (1) the existence of at least one parameter valuation for which there exists an infinite run in an L/U-PTA is PSPACE-complete; (2) the existence of a parameter valuation such that the system has a deadlock is however undecidable; (3) the problem of the existence of a valuation for which a run remains in a given set of locations exhibits a very thin border between decidability and undecidability.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191