The quadrature-based method of moments (QMOM) offers a promising class of approximation techniques for reducing kinetic equations to fluid equations that are valid beyond thermodynamic equilibrium. In this work, we study a particular five-moment variant of QMOM known as HyQMOM and establish that this system is moment-invertible over a convex region in solution space. We then develop a high-order discontinuous Galerkin (DG) scheme for solving the resulting fluid system. The scheme is based on a predictor-corrector approach, where the prediction is a localized space-time DG scheme. The nonlinear algebraic system in this prediction is solved using a Picard iteration. The correction is a straightforward explicit update based on the time-integral of the evolution equation, where the space-time prediction replaces all instances of the exact solution. In the absence of limiters, the high-order scheme does not guarantee that solutions remain in the convex set over which HyQMOM is moment-realizable. To overcome this, we introduce novel limiters that rigorously guarantee that the computed solution does not leave the convex set of realizable solutions, thus guaranteeing the hyperbolicity of the system. We develop positivity-preserving limiters in both the prediction and correction steps and an oscillation limiter that damps unphysical oscillations near shocks. We also develop a novel extension of this scheme to include a BGK collision operator; the proposed method is shown to be asymptotic-preserving in the high-collision limit. The HyQMOM and the HyQMOM-BGK solvers are verified on several test cases, demonstrating high-order accuracy on smooth problems and shock-capturing capability on problems with shocks. The asymptotic-preserving property of the HyQMOM-BGK solver is also numerically verified.
相關內容
Graph neural networks (GNNs) are widely used for modeling complex interactions between entities represented as vertices of a graph. Despite recent efforts to theoretically analyze the expressive power of GNNs, a formal characterization of their ability to model interactions is lacking. The current paper aims to address this gap. Formalizing strength of interactions through an established measure known as separation rank, we quantify the ability of certain GNNs to model interaction between a given subset of vertices and its complement, i.e. between sides of a given partition of input vertices. Our results reveal that the ability to model interaction is primarily determined by the partition's walk index -- a graph-theoretical characteristic that we define by the number of walks originating from the boundary of the partition. Experiments with common GNN architectures corroborate this finding. As a practical application of our theory, we design an edge sparsification algorithm named Walk Index Sparsification (WIS), which preserves the ability of a GNN to model interactions when input edges are removed. WIS is simple, computationally efficient, and markedly outperforms alternative methods in terms of induced prediction accuracy. More broadly, it showcases the potential of improving GNNs by theoretically analyzing the interactions they can model.
This paper presents the first systematic study on the fundamental problem of seeking optimal cell average decomposition (OCAD), which arises from constructing efficient high-order bound-preserving (BP) numerical methods within Zhang--Shu framework. Since proposed in 2010, Zhang--Shu framework has attracted extensive attention and been applied to developing many high-order BP discontinuous Galerkin and finite volume schemes for various hyperbolic equations. An essential ingredient in the framework is the decomposition of the cell averages of the numerical solution into a convex combination of the solution values at certain quadrature points. The classic CAD originally proposed by Zhang and Shu has been widely used in the past decade. However, the feasible CADs are not unique, and different CAD would affect the theoretical BP CFL condition and thus the computational costs. Zhang and Shu only checked, for the 1D $\mathbb P^2$ and $\mathbb P^3$ spaces, that their classic CAD based on the Gauss--Lobatto quadrature is optimal in the sense of achieving the mildest BP CFL conditions. In this paper, we establish the general theory for studying the OCAD problem on Cartesian meshes in 1D and 2D. We rigorously prove that the classic CAD is optimal for general 1D $\mathbb P^k$ spaces and general 2D $\mathbb Q^k$ spaces of arbitrary $k$. For the widely used 2D $\mathbb P^k$ spaces, the classic CAD is not optimal, and we establish the general approach to find out the genuine OCAD and propose a more practical quasi-optimal CAD, both of which provide much milder BP CFL conditions than the classic CAD. As a result, our OCAD and quasi-optimal CAD notably improve the efficiency of high-order BP schemes for a large class of hyperbolic or convection-dominated equations, at little cost of only a slight and local modification to the implementation code.
In a mixed generalized linear model, the objective is to learn multiple signals from unlabeled observations: each sample comes from exactly one signal, but it is not known which one. We consider the prototypical problem of estimating two statistically independent signals in a mixed generalized linear model with Gaussian covariates. Spectral methods are a popular class of estimators which output the top two eigenvectors of a suitable data-dependent matrix. However, despite the wide applicability, their design is still obtained via heuristic considerations, and the number of samples $n$ needed to guarantee recovery is super-linear in the signal dimension $d$. In this paper, we develop exact asymptotics on spectral methods in the challenging proportional regime in which $n, d$ grow large and their ratio converges to a finite constant. By doing so, we are able to optimize the design of the spectral method, and combine it with a simple linear estimator, in order to minimize the estimation error. Our characterization exploits a mix of tools from random matrices, free probability and the theory of approximate message passing algorithms. Numerical simulations for mixed linear regression and phase retrieval display the advantage enabled by our analysis over existing designs of spectral methods.
We study geometric variations of the discriminating code problem. In the \emph{discrete version} of the problem, a finite set of points $P$ and a finite set of objects $S$ are given in $\mathbb{R}^d$. The objective is to choose a subset $S^* \subseteq S$ of minimum cardinality such that for each point $p_i \in P$, the subset $S_i^* \subseteq S^*$ covering $p_i$ satisfies $S_i^*\neq \emptyset$, and each pair $p_i,p_j \in P$, $i \neq j$, we have $S_i^* \neq S_j^*$. In the \emph{continuous version} of the problem, the solution set $S^*$ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ($d=1$), the points in $P$ are placed on a horizontal line $L$, and the objects in $S$ are finite-length line segments aligned with $L$ (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. Still, for the 1-dimensional discrete version, we design a polynomial-time $2$-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ($d=2$) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce $(16\cdot OPT+1)$-approximate and $(64\cdot OPT+1)$-approximate solutions respectively, using rounding of suitably defined integer linear programming problems. We show that the identifying code problem for axis-parallel unit square intersection graphs (in $d=2$) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects.
The selection of smoothing parameter is central to the estimation of penalized splines. The best value of the smoothing parameter is often the one that optimizes a smoothness selection criterion, such as generalized cross-validation error (GCV) and restricted likelihood (REML). To correctly identify the global optimum rather than being trapped in an undesired local optimum, grid search is recommended for optimization. Unfortunately, the grid search method requires a pre-specified search interval that contains the unknown global optimum, yet no guideline is available for providing this interval. As a result, practitioners have to find it by trial and error. To overcome such difficulty, we develop novel algorithms to automatically find this interval. Our automatic search interval has four advantages. (i) It specifies a smoothing parameter range where the associated penalized least squares problem is numerically solvable. (ii) It is criterion-independent so that different criteria, such as GCV and REML, can be explored on the same parameter range. (iii) It is sufficiently wide to contain the global optimum of any criterion, so that for example, the global minimum of GCV and the global maximum of REML can both be identified. (iv) It is computationally cheap compared with the grid search itself, carrying no extra computational burden in practice. Our method is ready to use through our recently developed R package gps (>= version 1.1). It may be embedded in more advanced statistical modeling methods that rely on penalized splines.
Charge dynamics play essential role in many practical applications such as semiconductors, electrochemical devices and transmembrane ion channels. A Maxwell-Amp\`{e}re Nernst-Planck (MANP) model that describes charge dynamics via concentrations and the electric displacement is able to take effects beyond mean-field approximations into account. To obtain physically faithful numerical solutions, we develop a structure-preserving numerical method for the MANP model whose solution has several physical properties of importance. By the Slotboom transform with entropic-mean approximations, a positivity preserving scheme with Scharfetter-Gummel fluxes is derived for the generalized Nernst-Planck equations. To deal with the curl-free constraint, the dielectric displacement from the Maxwell-Amp\`{e}re equation is further updated with a local relaxation algorithm of linear computational complexity. We prove that the proposed numerical method unconditionally preserves the mass conservation and the solution positivity at the discrete level, and satisfies the discrete energy dissipation law with a time-step restriction. Numerical experiments verify that our numerical method has expected accuracy and structure-preserving properties. Applications to ion transport with large convection, arising from boundary-layer electric field and Born solvation interactions, further demonstrate that the MANP formulation with the proposed numerical scheme has attractive performance and can effectively describe charge dynamics with large convection of high numerical cell P\'{e}clet numbers.
We introduce a novel approach to inference on parameters that take values in a Riemannian manifold embedded in a Euclidean space. Parameter spaces of this form are ubiquitous across many fields, including chemistry, physics, computer graphics, and geology. This new approach uses generalized fiducial inference to obtain a posterior-like distribution on the manifold, without needing to know a parameterization that maps the constrained space to an unconstrained Euclidean space. The proposed methodology, called the constrained generalized fiducial distribution (CGFD), is obtained by using mathematical tools from Riemannian geometry. A Bernstein-von Mises-type result for the CGFD, which provides intuition for how the desirable asymptotic qualities of the unconstrained generalized fiducial distribution are inherited by the CGFD, is provided. To demonstrate the practical use of the CGFD, we provide three proof-of-concept examples: inference for data from a multivariate normal density with the mean parameters on a sphere, a linear logspline density estimation problem, and a reimagined approach to the AR(1) model, all of which exhibit desirable coverages via simulation. We discuss two Markov chain Monte Carlo algorithms for the exploration of these constrained parameter spaces and adapt them for the CGFD.
The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for larger numbers of objectives. In this work, we use mathematical runtime analyses to rigorously demonstrate and quantify this phenomenon. We show that even on the simple OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also with large population sizes cannot compute the full Pareto front (objective vectors of all Pareto optima) in sub-exponential time when the number of objectives is at least three. Our proofs suggest that the reason for this unexpected behavior lies in the fact that in the computation of the crowding distance, the different objectives are regarded independently. This is not a problem for two objectives, where any sorting of a pair-wise incomparable set of solutions according to one objective is also such a sorting according to the other objective (in the inverse order).
To control humanoid robots, the reference pose of end effector(s) is planned in task space, then mapped into the reference joints by IK. By viewing that problem as approximate quadratic programming (QP), recent QP solvers can be applied to solve it precisely, but iterative numerical IK solvers based on Jacobian are still in high demand due to their low computational cost. However, the conventional Jacobian-based IK usually clamps the obtained joints during iteration according to the constraints in practice, causing numerical instability due to non-smoothed objective function. To alleviate the clamping problem, this study explicitly considers the joint constraints, especially the box constraints in this paper, inside the new IK solver. Specifically, instead of clamping, a mirror descent (MD) method with box-constrained real joint space and no-constrained mirror space is integrated with the Jacobian-based IK, so-called MD-IK. In addition, to escape local optima nearly on the boundaries of constraints, a heuristic technique, called $\epsilon$-clamping, is implemented as margin in software level. Finally, to increase convergence speed, the acceleration method for MD is integrated assuming continuity of solutions at each time. As a result, the accelerated MD-IK achieved more stable and enough fast tracking performance compared to the conventional IK solvers. The low computational cost of the proposed method mitigated the time delay until the solution is obtained in real-time humanoid gait control, achieving a more stable gait.
In two and three dimension we analyze discontinuous Galerkin methods for the acoustic problem. The acoustic fluid that we consider on this paper is inviscid, leading to a linear eigenvalue problem. The acoustic problem is written, in first place, in terms of the displacement. Under the approach of the non-compact operators theory, we prove convergence and error estimates for the method when the displacement formulation is considered. We analyze the influence of the stabilization parameter on the computation of the spectrum, where spurious eigenmodes arise when this parameter is not correctly chosen. Alternatively we present the formulation depending only on the pressure, comparing the performance of the DG methods with the pure displacement formulation. Computationally, we study the influence of the stabilization parameter on the arising of spurious eigenvalues when the spectrum is computed. Also, we report tests in two and three dimensions where convergence rates are reported, together with a comparison between the displacement and pressure formulations for the proposed DG methods.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191