WorksPhysics and Astronomy
An improvement to the spatial discretisation in the Astrophysical Weighted Particle Hydrodynamics method
Abstract
The discretisation of space in the Astrophysical Weighted Particle Hydrodynamics method is attained through a partition-of-unity-based cubature rule. The node (particle) weights in such rules must in general be obtained using approximations, for which only one has been thus far proposed in the literature. In this work, new approximations for these weights are proposed, their properties are studied, and their impact on the accuracy of the cubature rule and the overall method is assessed. Approximations for node centroids are also proposed and studied, and their possible applications are laid out. Additionally, for schemes in which the kernel-function compact-support size is set to be constant, rather than adaptive, weight and centroid approximations are provided as well. Finally, for the cubature rule arising from the weight approximation previously proposed in the literature, an asymptotic expression for its mean relative error is derived, and its usefulness for understanding the finite-sample properties of the cubature rule is showcased with some simple examples.
Introduction
The Astrophysical Weighted Particle Hydrodynamics (AWPH) method of Gaburov and Nitadori [10] is a meshless numerical scheme conceived to solve the equations of inviscid compressible hydrodynamics and magnetohydrodynamics for applications in Astrophysics. It is based on the scheme developed in Vila [31], which is itself built from the Smoothed Particle Hydrodynamics (SPH) method [e.g. 27 and references therein].
Vila [31] coined the term Weighted Particle Methods (WPM) to refer to meshless numerical methods for conservation laws that share the SPH strategy of using a weighted sum over nodes (i.e., particles, points, tracers, etc.) to approximate the sought-off solution. It then introduced a variant of WPM which aimed at solving two of the major drawbacks of SPH: its shock-capturing properties and its estimation of derivatives. To address the former, the weak form of the conservation law is used as a starting point for the discretisation; while for the latter, a so-called Renormalised Meshless Derivative (RMD) is introduced which computes derivatives of affine functions exactly. This WPM variant was later called the weak RMD scheme in subsequent studies [23, 20], and had its stability, consistency and convergence studied in Lanson and Vila [21]. It is this variant that was used in Gaburov and Nitadori [10] to construct the AWPH method.
Common to all WPM-like methods is the discretisation of the spatial integral appearing in the weak form of a conservation law through the introduction of a cubature rule (i.e., a quadrature rule for a multivariate integral). Hence, at the beginning of a calculation, a weight needs to be assigned to each node such that the resulting cubature rule approximates the spatial integral of the initial state of a problem to some desired degree of accuracy. For the subsequent time evolution, then, it is necessary to prescribe how nodes and weights will evolve, hopefully in such a way that the newly obtained cubature rule maintains its accuracy in approximating the spatial integral of the time-evolved state. Vila [31] advocated to move the nodes with the local fluid velocity and to update their weights with an advection equation (e.g., its Equation 2.2). Gaburov and Nitadori [10], on the other hand, while still moving the nodes with the local fluid velocity, resorted to a partition-of-unity approach to obtain their weights.
In Applied Mathematics, partitions of unity are well known in the field of interpolation. For example, they appear naturally in the construction of a Moving Least Squares (MLS) approximation of a function. Moreover, since interpolation techniques form the basis of meshless numerical methods for solving partial differential equations, partitions of unity have also made their appearance in the latter [e.g. 2]. In the context of numerical integration, the use of partitions of unity to obtain cubature rules seems to have been pioneered by Carpinteri et al. [4] and Duflot and Nguyen-Dang [7]. Its properties for the integration of convex functions were later formalised by Guessab et al. [12].
Due to computational-efficiency considerations, it is common for partitions of unity to be built from functions having a compact support. Moreover, in some applications it is useful to make the size of this compact support adaptive. Such is the _footer: Email address: [email protected] (Alex Massaro Achá) case for the AWPH method. A criterion needs to be defined, then, that prescribes the way in which the compact-support size will adapt, which should be controlled by one or more numerical parameters.
Then, by choosing a particular partition-of-unity function and, if desired, a scheme for the adaptivity of its compact-support size, a cubature rule is completely established and its weights can be calculated given the node positions. An approximation for them for the choices in AWPH was put forward by Gaburov and Nitadori [10], which was thenceforth adopted in all the subsequent work on the method [15, 16, 1, 11] (Kajzer and Pozorski 2024).
The role played by the cubature weights, however, is not limited to the spatial discretisation. They are, in fact, part of the definition of the RMD (e.g. Lanson and Vila, 2008a, Equation 14), through which they play a role in gradient estimation and in establishing the interaction strength between two neighbouring nodes (e.g. Lanson and Vila, 2008a, Equation 23). Furthermore, in fluid-flow calculations, they are directly used to obtain mass-density estimates, which are in turn used to obtain the fluid’s pressure field. As such, they play a role in the dynamics of the flow as well.
In this work, an approach is put forward which allows obtaining higher-order corrections to the weight approximation proposed by Gaburov and Nitadori [10]. Several new approximations are obtained by truncating the expressions at different orders, which then have their accuracy evaluated by comparing them to a computationally expensive exact weight calculation. The approach is also used to obtain several new approximations for node centroids, which are also evaluated following the same method as for the weights. After choosing the most suitable weight approximations arising from the analysis, their impact on the accuracy and convergence of AWPH’s cubature rule is evaluated for some simple cases of numerical integration, and their impact on the full solution of a conservation law is showcased with a specific example.
Additionally, the partition-of-unity-based cubature rule arising from the weight approximation proposed by Gaburov and Nitadori [10] is shown to be equivalent to a Monte Carlo integration scheme, which enables obtaining an asymptotic expression for its mean relative error. An example of the usefulness of this expression to understand the finite-sample properties of such a cubature rule is then given.
Finally, for applications in which the kernel’s compact-support size is set to be a constant, rather than adaptive, a different approach is used to derive new weight and centroid approximations, which are given in Appendix C.
It should be noted that the treatment of boundary conditions is completely disregarded in this work. As such, Cartesian periodic boundary conditions are assumed throughout.
The paper is structured as follows. Section 2 introduces the relevant details of the AWPH method for this work. Section 3 establishes the equivalence between AWPH’s cubature rule, with the weights proposed by Gaburov and Nitadori [10], and Monte Carlo integration. Section 4 outlines the derivation of the new weight and centroid approximations that are the core of this work. Section 5 addresses the accuracy of these weight and centroid approximations. Section 6 provides a simple numerical assessment of the accuracy and convergence of AWPH’s cubature rule. Section 7 showcases the effects of the weight approximations in the solution of a problem in inviscid compressible hydrodynamics. Finally, in Section 8 the results are discussed, and Section 9 lays out the conclusions.
The spatial discretisation in AWPH
The weak form of a general scalar conservation law can be written as
where is the unknown function, are the components of the flux vector, collects the possible source terms, and is an arbitrary test function. The notation means a total time derivative along a trajectory , means a partial derivative with respect to the spatial coordinate, and summation is implied in the term with repeated Greek indices. The integration is done over the entire spatial and temporal domain of the problem. Thus, the first step in WPM, and by extension in AWPH, is to discretise this spatial integral using a cubature rule.
A cubature rule is defined as a set of point-weight pairs such that
to some desired degree of accuracy. More general cubature rules can include point-weight pairs associated to values of the function’s derivatives, besides the ones associated to values of the function itself. However, such rules are not relevant for the present work.
Equation 2 is typically required to be exact for functions belonging to some function space that captures the general properties of the functions that the rule will be applied to in practice. The most general one is the space of polynomials of a given degree. All in all, the most basic requirement is for the rule to be exact for constant functions, which implies that ; i.e., the sum of the weights must equal the size of the domain. The assumption of exactness for polynomials up to a given degree is ubiquitous in mathematical proofs of the accuracy and convergence of quadrature and cubature rules [e.g. 8, 5].
Partitions of unity are sets of functions that satisfy the following (Guessab et al., 2006, Definition 3.3)
,
, and
.
Their usefulness in the present context lies in that, given a set of points , they can be used to divide a given domain into a set of overlapping subdomains such that
,
,
simply by setting
since it immediately follows that . Hence, the combined set defines a cubature rule for numerical integration in that is, at worst, exact for constant functions. Furthermore, it is shown in Guessab et al. [12]1 that if the set has the additional property of
then the cubature rule it defines will be exact for affine functions as well. The vector will here be called the centroid of node . It is also commonly called the centre of mass or barycentre.
In practice, however, Equations 3 and 4 must typically be approximated, either analytically or numerically. As a consequence, the integration of constant and affine functions will not be exact; instead, they will inherit the accuracy of the approximations being used.
In AWPH, the functions composing the partition of unity are given as
where is called the kernel and weight function in the SPH and the MLS literatures, respectively, is the size of its compact support, and
This choice for a partition of unity corresponds to the shape function of an MLS function approximation that is exact for constant functions. They are also called Shepard functions due to the work of Shepard [25]. The spatial adaptivity of the compact-support size is given through the following constraint
where is the space dimensionality and for . Equation 7 implicitly defines the function , whose values must in general be obtained by an iterative procedure, and is the numerical parameter controlling its adaptivity. For monotonically decreasing kernel functions, is a monotonically increasing function of .
Having prescribed , weights can in principle be evaluated by plugging Equation 5 into Equation 3. However, as noted earlier, this can only be done in an approximate way. Gaburov and Nitadori [10] proposed the approximation
Hereafter, for the sake of brevity, the kernel function will be referred to simply as the kernel, and its compact-support size simply as the support. Furthermore, the function will be referred to as the support function.
Relation with kernel density estimation and Monte Carlo integration
As it turns out, the cubature rule that follows from the relations described thus far can be cast into the formalism of Kernel Density Estimation (KDE) and Monte Carlo Integration (MCI). This brings considerable insight into its properties and provides a theoretical basis for interpreting the results obtained with it in the simple numerical-integration examples of Section 6.
It can be seen that the quantity in Equation 6 is proportional to an adaptive KDE of the underlying Probability Density Function (PDF) of node positions. Evidently, denoting by the adaptive KDE of the node-position PDF ,
where is the number of nodes. Furthermore, Equation 7 has its origin in the so-called nearest-neighbour method [26 Chapter 5] used as a so-called balloon estimator Terrell and Scott, [28] in adaptive KDE, in which the support (commonly called the band width in KDE literature) is taken as a function of position, , in order to define its adaptivity. As such, the parameter is related, approximately and statistically, to the number of nodes fulfilling ; that is, to the number of neighbours at position .
The previous observations lead to the conclusion that the cubature rule, with weights computed using Equation 8, is actually an importance-sampling MCI scheme in which the importance-sampling distribution is set to an adaptive KDE of the node-position PDF. Indeed,
As a consequence, it inherits all the properties of such schemes. Most importantly, it will be the most accurate when the importance-sampling distribution is as close as possible to a PDF given by Evans and Swartz, [9]
which implies that node positions should look like samples drawn from the latter as much as possible. Furthermore, even in the ideal case where this condition is fulfilled, the rule’s accuracy will be limited by that with which approximates . In fact, if such a favourable case is indeed assumed, then results from KDE theory can be used to obtain an asymptotic approximation of the mean relative error of the cubature rule.
The details are given in Appendix § 10. The final result is the following
where , and are constants that depend on the kernel and the function being integrated. The terms in the right-hand side come from the bias, squared bias and variance of the KDE, respectively. The first observation to make is that, asymptotically, the mean relative error is not a monotonic function of the parameter. This is a direct consequence of the bias-variance trade-off as manifested in the KDE. The second observation is that, whenever the variance term dominates, no accuracy improvement can be expected by increasing while keeping constant, which is to say that the cubature rule will show no convergence in such cases.
It should be noted, however, that while Equation (12) provides useful insight into the asymptotic (in the sense detailed in Appendix § 10) properties of the cubature rule, it should be used with care when interpreting such properties under finite samples, as the asymptotic assumption is formally never fulfilled. In § 5, for example, it is shown that it can be successfully used as a regression model to understand the observed relative errors of the cubature rule while numerically integrating some simple functions. It should be stressed as well that this result is only valid for cubature weights computed as proposed by Gaburov and Nitadori [10] (that is, Equation (8)). It does not hold for the approximations derived in this work, as the weights then cease to be proportional to a KDE of the node-position PDF.
Weight and centroid approximations
Derivation
In deriving approximations for weights and centroids, it proves convenient to introduce what will here be called the Dimensionless Kernel (DK) as
Furthermore, it will be assumed that the DK can always be written as
Then, in terms of it, Equation (5) can be rewritten, with the help of Equation (7), as
Additionally, for the case of centroids, instead of attempting to evaluate Equation (4) directly, it proves simpler to evaluate the vector
from which, then, .
With these simplifications, the approach followed goes as follows.
i. Expand the support function in a Taylor series around a node position , discarding third- and higher-order terms.
ii. Expand in a Taylor series around the node’s support , discarding fourth- and higher-order terms.
iii. Substitute the support-function expansion into the expansion. This yields an approximation for the latter where the support function has been completely replaced by and its first and second spatial derivatives evaluated at .
iv. Evaluate Equations (3) and (16) using Equation (15) and introducing the approximation of the previous point. As it turns out, this can be done analytically.
The final results can be cast in a concise way as follows
where lower- and upper-case bold-face letters denote column vectors and matrices, respectively, and is the support-function’s gradient vector. The explicit forms of each of the coefficients are given in Appendix § 11 for the one-, two- and three-dimensional cases.
Spatial derivatives of the support function
In order to be able to use the above-derived approximations, the support-function’s gradient vector, , and Hessian matrix, , need to be known. They can be derived analytically by differentiating Equation (7). It proves convenient to rewrite said equation using the DK as follows
Then, by computing the latter’s total differential twice, the following are obtained
where
in which superscripts denote specific entries in vectors and matrices, and
in which , and likewise for (see Equation (14) for the definition of ).
It is important to note that when evaluating Equations (22) to (26) at node positions, , there will be a term in their right-hand-side summations for . Hence, these equations are meaningful provided that their limit when exist. In order for this to be the case, the limit must exist for their term. This can be seen to hold, as
It should be noted that the validity of Equation (34) is actually a requirement the kernel must fulfil in order for the Hessian matrix to be defined at node positions2. Accordingly, it has been verified to hold for all the kernels considered in this work that are used to compute a Hessian matrix.
Properties of the weight and centroid approximations
Having derived new approximations for weights and centroids, this section is devoted to studying their accuracy. Noting that, in fact, several approximations have been derived, as the Taylor-series expansions that were used to obtain them can be truncated at different orders, the goal is to assess the merit of each of these truncation orders in terms of the accuracy and computational cost and complexity of the weight and centroid approximations they lead to, with the expectation of finding the most suitable.
The setup
The procedure followed consists in comparing the different weight and centroid approximations to their corresponding “exact” values. These exact values are taken as those obtained from the evaluation of the integrals in Equations (3) and (4) with an arbitrarily accurate cubature rule. For the latter, the Cuhre routine of the Cuba library3 is used, which is described in Hahn [13] and references therein. This same routine is also used to evaluate Equations (3) and (4) for the case in which only the DK is expanded in a Taylor series, while the support function is used in full. This gives an upper bound on the improvement that can be robustly achieved by Equations (17) and (18), as further improvement must come from error compensation between the two Taylor-series expansions, which would be coincidental and thus not numerically robust. Furthermore, given the high computational cost associated with evaluating integrals with such cubature rules, this process is carried out in two spatial dimensions.
In order to proceed, a labelling scheme must be defined for the relevant truncation orders. The notation is used where and denote the orders of the DK and support-function Taylor-series expansions, respectively. Thus, for example, denotes the weight and centroid approximations resulting from expanding the DK to third order and using the support function in full (this approximation was mentioned in the previous paragraph), while denotes the approximations resulting from first-order expansions for both the DK and the support function. It should be mentioned that, as a consequence of the DK and its derivatives being even functions of , half of the contributions to Equations (17) and (18) from the combination of terms in the Taylor series’ vanish identically. This is why not all possible truncation-order combinations are shown. For instance, the weight approximations and are equivalent, since the integration of the additional term that is present the latter vanishes identically. This is the approximation previously proposed in the literature (Equation (8)). Finally, in the fully expanded forms of Equations (17) and (18), terms corresponding to a given order of the DK expansion can be easily identified, as those that have a combined power in the gradient and Hessian-matrix components that is linear, quadratic or cubic must come from the first-, second- or third-order terms in the DK expansion, respectively.
Discrepancies between approximations and exact values are quantified through measures of dispersion and central tendency (that is, bias). These are taken as the mean of the unsigned and signed errors, respectively, where the latter are defined as
where denotes either the weights or centroid components, being an approximation and the exact value, and is a suitable scale that is chosen to ease interpretation. These choices are always indicated explicitly in all the figures of this section.
Node distributions and numbers
Node positions are randomly sampled from three different distributions. In all cases, each coordinate is sampled independently. The base-line case is a uniform distribution. Then, in an attempt to mimic the conditions found in real-world problems, a piecewise-uniform and a normal distribution are considered. The piecewise-uniform distribution is taken as
which is used to sample one of the coordinates, while the other is sampled from the uniform distribution. This intends to mimic discontinuities, which are ubiquitous in non-linear conservation laws. Finally, the normal distribution has and a mean located at the centre of the domain. This distribution, in turn, intends to mimic node clustering. Node numbers are for the uniform and piecewise-uniform distributions, while the normal distribution has .
The kernel functions
In general, the degree to which the support function can be approximated by its Taylor series will improve if its derivatives can be made smaller in magnitude. The latter, as a consequence of the support-function’s definition through Equation (7), depend not only on the node distribution, but on the magnitude of the kernel derivatives as well. Thus, it is to be expected that kernels with smaller slopes and curvatures (that is, less centrally concentrated) will yield better approximations, provided they meet the requirements to be Taylor expanded up to the relevant orders.
To demonstrate the above, the following kernels, here ordered by increasing central concentration, are considered. The kernel of Cabezón et al. [3], which is written here in DK form (see Cabezón et al. [3], Equation (3)) as
where is the normalisation constant for dimensions, which must be obtained numerically. Additionally, the kernel of Wu (1995), Table 1, and the standard cubic- and quartic-spline kernels (e.g. Dehnen and Aly [6], Table 1) are considered.
With the exception of the kernel, they all have continuous second derivatives, and thus can be used for the approximations at all the relevant truncation orders. The second derivative of the kernel, however, diverges at , thus it can at most be used for the approximations.
Shortlisting the truncation orders
Of all the possible combinations of an up-to third-order DK expansion and an up-to second-order support-function expansion, several do not merit further investigation given the undesired properties or poor accuracy exhibited by their weight and/or centroid approximations.
In the case of the weight approximation, it is seen that any approximation that makes use of the diagonal entries of the support-function’s Hessian matrix has the tendency to yield substantial overestimates. Although the overestimation is reduced by increasing the parameter, these approximations remain far from being competitive with those that do not include these entries. This property is a consequence of the fact that the support function can become strongly concave up inside local clusters of nodes, in which case its second-order Taylor series grossly overestimates it near the boundaries of the region delimited by a node’s support, thus leading to the weight overestimation. Nonetheless, it turns out that approximations in which the diagonal entries of the Hessian matrix are discarded, but the off-diagonal ones are kept, are still competitive. Thus, hereafter, all the weight approximations that are second order in the support function discard the diagonal entries of the Hessian matrix, and keep only the off-diagonal ones. They are denoted by appending the suffix “(nd)” (meaning no diagonal) to their labels.
Furthermore, still in the case of weight approximations, in most applications weights are required to be positive, as their most common physical interpretation is the size (that is, length, area or volume) of a node. This becomes a difficulty for the approximation, since it can indeed yield negative weights. Thus, in this work the choice was made to address this problem by introducing a minimum value that this approximation can take, and setting this minimum to the value given by the approximation. A different approximation could indeed be used in place of the latter; however, given that the approximation is on average a clear underestimate of the true weight (as per the results of this section), it is at the very least a sensible choice for the purpose of limiting the approximation. The resulting approximation is denoted as .
On the other hand, in the case of the centroid approximation, it should first be noted that obtaining a centroid approximation requires a weight approximation to be obtained beforehand (see Equations (4) and (16)). In principle, this gives the freedom to choose different truncation orders for the and approximations from which the centroid is obtained. However, in this work this freedom is not explored, and thus the same truncation orders are always used to obtain and . That being the case, it turns out that centroid approximations that include the third-order term of the DK’s Taylor series (that is, and ) yield poor accuracy when compared to approximations that exclude this term, and thus they will not be considered further. Likewise, even though it performs better than the previous two, the approximation still does not compete with the rest, and thus it is excluded as well.
Results
Figures 1 and 2 show the distributions of the shortlisted weight and centroid approximations with respect to the exact values for the three node distributions described in § 4.2. In the case of weights, Figure 1 shows the distributions of relative errors as a function of the exact weights. In the case of centroids, Figure 2 shows the joint distributions of approximations and exact values, both normalised by node supports.
Figure 1. Weight-approximation relative-error distributions. Nodes are sampled from the uniform (top row), piecewise-uniform (middle row) and normal (bottom row) distributions, as described in § 4.2. Columns correspond to different weight approximations, as indicated at the top of the Figure. Contours enclose roughly 40, 70, 90, 95, 99 and 99.7% of the total number of points. The horizontal axis is normalised by , which denotes the mean weight for each distribution. Note that the horizontal axes have different ranges in each row. The dashed black line marks the locus of vanishing error, while the dashed red line is the median in horizontal-axis bins. These results correspond to the kernel of Wu (1995) with .
Figure 2. Joint distributions of centroid approximations and exact values, both in units of node supports. Nodes are sampled from the uniform (top row), piecewise-uniform (middle row) and normal (bottom row) distributions. Columns correspond to different centroid approximations, as indicated at the top of the Figure. Contours enclose roughly 40, 70, 90, 95, 99 and 99.7% of the total number of points. Centroid components are lumped together in the uniform- and normal-distribution cases, while only the component across the discontinuity is included in the piecewise-uniform case. The dashed black line marks the locus of vanishing error, while the dashed red line is the median in horizontal-axis bins. These results correspond to the kernel of Wu (1995) with .
The first thing to notice in Figure 1 is that the approximation (the one previously proposed in the literature) has a bias towards underestimating the weights in all three node distributions being considered, and that the and approximations have this bias reduced. Furthermore, perhaps unsurprisingly, in all cases the approximation performs much better both in terms of bias and dispersion with respect to the exact values. However, the difference is less stark in the case of normally distributed nodes, particularly for the nodes with the largest weights, where all approximations yield substantial underestimates of the exact weights. These correspond to the nodes sampled at the outskirts of the normal distribution, and the reason behind such poor performance can be understood as follows. The support-function definition guarantees that every point in the domain has at least one node inside its support .
least one node inside its support . Thus, every point in the domain will contribute to the weight and centroid integrals of at least one node. However, when the DK is Taylor expanded with respect to the support, the DK itself and all its derivatives are evaluated only at the support value around which the expansion is made; the latter being in practice the node supports . Due to the compactly supported property of the DKs that are used in practice, this means that points for which for all will fail to contribute to any of the weight and centroid integrals. This effect should be most noticeable in nodes around regions of low node density, where the support function has local maxima. In the case of the normal distribution considered here, this effect is exacerbated since a considerable fraction of the domain is completely devoid of nodes (the value of was purposely chosen in order to illustrate this effect). Naturally, increasing the order of the Taylor expansion should eventually compensate for this effect. However, for the third-order expansion considered here, it still leads to underestimates of both weights and centroid components as well, as discussed next.
In Figure 2, the first thing to notice is that all approximations are somewhat biased towards underestimating the centroids when these are far away from node positions, which is to say that, in such cases and on average, they tend to yield centroids closer to node positions than they truly are. This is especially noticeable in the normal distribution, where nodes sampled at its outskirts have centroids that are considerably far away from their positions4, for which all approximations yield substantial underestimates. The reason behind this is the same as for the weight underestimation in this same distribution, which was described in the previous paragraph. In contrast, in nodes whose centroids are closer to their positions, the approximations, albeit with a fair amount of dispersion, are much less biased and, on average, closely follow the one-to-one line. Finally, it should be mentioned that the approximation is actually bounded in the following sense
where is the constant appearing in Equations (17) and (18), for which values are given in Appendix B, and is the number of dimensions. In the case of Figure 2, in which the kernel of Wu (1995) is used in two dimensions, the right-hand side evaluates to roughly 0.25.
A summary of the error properties of the shortlisted approximations as a function of the parameter is shown in Figure 3, for the case of the kernel of Wu (1995). Looking at the first
Figure 3. Error dispersion and central tendency (bias), as indicated by the labels in the vertical axes, in the weight and centroid approximations as a function of . Columns correspond to different node distributions as described in Section 5.2, which are indicated at the top of the Figure. Note the different vertical-axis range in the bottom-right panel. These results correspond to the kernel of Wu (1995).
and third rows, from top to bottom, it is seen that the dispersions of the approximations around the exact values, for both weight and centroids, are comparable (excluding , of course), and that is slightly favoured, again for both weight and centroids. Furthermore, looking at the bottom row, it is seen that all centroid approximations have similar small overall biases. In fact, such small values are likely affected by the accuracy of the cubature rule that was used to obtain the exact centroids, and thus no further conclusion should be drawn from them. Finally, looking at the second row in Figure 3, it is seen that the weight approximation (the one previously proposed in the literature) consistently shows a noticeable negative bias, which however improves with increasing . All the other weight approximations show smaller biases, falling mostly below the 5% level, with very little dependence on . Of these, the and approximations show negative biases, while the approximation shows positive ones, for all node distributions considered.
The most suitable approximations
As previously mentioned, the goal of this section is to establish the truncation order of the Taylor-series expansions that yields the most accurate weight and centroid approximations with the least amount of computational cost and complexity. With regards to accuracy, interpreting it in terms of error dispersion and bias, there is no clear winner between the and weight approximations. The same is true for all the shortlisted centroid approximations. However, due to the lower expansion order from which they emerge, computational cost and complexity clearly favour the weight and centroid approximations, and thus they should be the preferred choice. In spite of this, in applications and/or numerical schemes that are sensitive to weight underestimation, the weight approximation can be worthy of consideration.
Having selected a preferred weight and centroid approximation, the final figure in this section, Figure 4, shows a comparison of the kernels mentioned in Section 5.3. As expected, kernels that are less centrally concentrated consistently yield better results. Naturally, this holds for all the approximations, not just the one.
Figure 4. Error dispersion and central tendency (bias), as indicated by the labels in the vertical axes, in the weight and centroid approximations, as a function of . Results are shown for the kernels mentioned in Section 5.3 and the node distributions described in Section 5.2, as indicated in the legends.
Properties of the cubature rule
As previously mentioned, the partition-of-unity-based cubature rule of AWPH plays the role of a spatial discretisation in a scheme to solve a conservation law. Naturally, it is but one of several ingredients that need to be put together in order to obtain a practical scheme, and each of these ingredients will make its contribution to the overall error of the scheme. This section aims at establishing empirically the basic properties of the cubature-rule’s contribution to this error budget. Additionally, the tests conducted provide the opportunity to validate the results of Section 3. Consequently, first a likely lower bound on the rule’s error is established by considering the perhaps trivial case of integrating a constant function under a regular node distribution. Then, more general node distributions are considered for the integration of some basic functions. Throughout this section, for the sake of brevity, the weight approximation will be referred to simply as . Lastly, all tests are carried out in three spatial dimensions.
A regular node distribution
Given that the weights in the cubature rule are approximated, the latter will not be exact even for the integration of constant functions, irrespective of the node distribution. Thus, a likely lower bound on its error (or, equivalently, an upper bound on its accuracy) can be placed with the integration of a constant function under a regular node distribution. A cubic lattice is used for the latter; however, conclusions remain unchanged if a face-centred cubic lattice or a so-called glass-like distribution (White, 1996) are used instead.
It should be noted that the support function is not a constant under such node distributions. Nonetheless, it is indeed the case that, due to the node regularity, it evaluates to the same value at all node positions, and furthermore its gradient and the off-diagonal entries of its Hessian matrix all vanish at node positions. The Hessian diagonal entries, however, do not. Thus, all weight approximations that do not depend on the diagonal entries of the support-function’s Hessian matrix will yield the same result under regular node distributions, which is the case for all the approximations considered here, given the results of § 4.
With the above in mind, regular node distributions are a trivial case in the sense that the error in the cubature rule becomes equivalent to the error in the KDE estimate at node positions, which under such distributions is given entirely by the shape of the kernel being used. In fact, given that in this case the correct answer for the node weights is simply the size of the domain divided by the number of nodes, the error in the cubature rule is equivalent to the degree to which a given kernel can yield the “correct” node support, which from Equation (7) is
where is the size of the domain. Thus if the kernel, through Equation (7) and for a given , yields a support that underestimates this “correct” value, then the cubature rule will underestimate the value of the integral, and equivalently for the case of an overestimation. Furthermore, it should be noted that, in this case, altering the number of nodes while keeping constant leads to identical results, as this merely re-scales the problem, leaving relative errors untouched.
The cubature-rule’s relative error as a function of is shown in Figure 5, obtained with a total of nodes distributed as a cubic lattice in a unit cube. It shows that the likely minimum relative error that can be expected from the cubature rule is in the order of for the more common kernels, namely the cubic and quartic splines, at their typical values. However, the kernel of Cabezon et al. [3] and the kernel of Wu (1995) show somewhat higher relative errors at low values (similar to those for the cubic spline, for example), falling mostly in the range. The erratic behaviour observed comes from the weight (or support, as noted above) switching back and forth from under- to overestimating the exact value, which, as noted earlier, is entirely given by the shape of the kernel. Finally, note that Figure 5 is in fact equivalent to Figure 3 in Dehnen and Aly [6], where it is used to assess the accuracy of the SPH density estimate for a regular node distribution.
Figure 5. Relative error as a function of for the integration of a constant function when the nodes are distributed in a cubic lattice. A total of nodes are distributed in a unit cube. Results are shown for four kernel functions, as indicated.
More realistic node distributions
Having studied the trivial case of a constant function under a regular node distribution, the next step is to consider basic functions under more general node distributions. Analysis is restricted to non-negative functions and the nodes are assumed to be samples stochastically drawn from these functions after being normalised. Justification for this is provided for the case in which the conservation law to solve is the system of equations describing inviscid compressible hydrodynamics.
Recalling, the cubature rule in AWPH evolves with time in order to adapt to the evolution of the fields it integrates. In the context of ideal hydrodynamics, these fields are mass density, momentum density and total-energy density. Given that the nodes are prescribed to move with the local fluid velocity in both WPM and AWPH, if equal-mass nodes are assumed and mass exchanges between them are neglected, then they are expected to trace the mass-density field of the problem being solved. Moreover, whereas in SPH some semblance of node order has been argued to be maintained due to the zeroth-order inconsistency in its gradient estimator (e.g. Dehnen and Aly, 2012, Section 5.1.2), no such inconsistency is present in the RMD estimator used in AWPH. Therefore, it can be considered that node positions in AWPH evolve in such a way that they always resemble statistical samples drawn from a distribution given by the normalised mass-density field of the problem being solved, thus justifying the assumptions made for the analysis in this section.
Provided such assumptions hold, there is in fact a nice result that establishes the asymptotic (in the limit of “large” ) equivalence between the bias in weight approximation and the relative error in AWPH’s cubature rule, since in that case each term in the cubature-rule’s summation is asymptotically the probability mass of the corresponding node. If it can be assumed that the sampling procedure draws samples that asymptotically have the same probability mass, then each of these terms should approach that probability mass. This can then be recast into showing that weight-approximation bias and cubature-rule relative error are, under these assumptions, asymptotically equivalent.
With this in mind, and in order to mirror the analysis of § 4, the same distributions considered there are used here; namely, the uniform, piecewise-uniform and normal distributions (see § 4.2). However, results for the piecewise-uniform distribution lie somewhat in between those of the uniform and normal distributions, thus only the latter two will be shown. Finally, the weight approximations being considered, as per the results of § 4, are the and approximations, plus the one previously proposed in the literature [10], namely the approximation (Equation (8)).
The uniform distribution
The relative error as a function of is shown in Figure 6, in which node positions were drawn from the uniform distribution. In it, dotted lines show a least-squares fit of the , and coefficients of (12) to the relative errors corresponding to the weight approximation. It is seen that the best-fit coefficients have values consistent with their theoretical form (see Appendix § 10) for a uniform distribution, as and have vanishing values and only the term remains. Thus, in this case, increasing while keeping constant leads to identical results. This property, however, is seen to hold not only for the weight approximation, but for the others as well.
Figure 6. Relative error as a function of for the integration of the uniform distribution. Positions of nodes are drawn randomly from said distribution and their weights are computed using the kernels and approximations indicated in the legends. Dotted lines show a least-squares fit to Equation 12, for each kernel.
Both the and approximations are seen to perform much better than the approximation, as their relative errors are smaller by a factor of roughly 3.5. This difference, as previously mentioned, is a direct consequence of the latter’s negative bias with which it estimates weights, as seen in Figure 3, which leads directly to an underestimate of the true value of the integral. In the case of the approximation, the negative bias is much smaller, yet still present, thus the much smaller underestimate it yields for the integral. Finally, the approximation, albeit barely noticeable in Figure 3, in fact switches from a negative to a positive bias at low values, thus explaining why the same behaviour is observed in its relative error in Figure 6.
The normal distribution
Moving on to the case of the normal distribution, Figure 7 shows the relative error as a function of for three different numbers of nodes. As in the uniform-distribution case, dotted lines show a least-squares fit to (12). As expected, in this case the best-fit values for the coefficients and are non-negligible; however, compared to the best-fit coefficient, they are still subdominant. This means that the relative error in the approximation for the integration of the normal distribution is dominated by the variance of the KDE, which in turn means that the error will show little dependence on , and furthermore will decrease with increasing up to large values of the latter before the bias and squared-bias terms begin to dominate, as Figure 7 shows.
Figure 7. Relative error as a function of for the integration of the normal distribution with a standard deviation of 0.1. Node positions are drawn randomly from said distribution and their weights are computed using the kernels and approximations indicated in the legends. Dotted lines show a least-squares fit to Equation (12), for each kernel. From top to bottom, the number of nodes are , and .
In contrast, the relative error in the and approximations show a markedly different behaviour with both and . On one hand, for and at large values, both perform very poorly; however, their performance progressively improves with increasing . This poor performance is basically a consequence of nodes having overly broad supports, which renders the Taylor-series-based approach from which these approximations were derived very unfitting. On the other hand, much like the analysis in the uniform-distribution case, the behaviour of their relative errors can again be understood on the basis of the bias of their weight estimates. However, in the present case of a normal distribution, their asymptotic equivalence needs to be taken with care as finite-sample effects are more prominent. Thus, albeit approximately, the error in the integral estimate reflects the bias in the weight approximation, and the behaviour seen for the former in Figure 7 basically showcases the values at which the respective weight approximations switch from negative to positive bias. In other words, at these values the weight approximations are unbiased, and they are seen to depend strongly on in the approximation, yet are roughly constant in the approximation. In fact, in the case of the latter, these values are similar as well in the uniform-distribution case, as seen in Figure 6, and likewise in the piecewise-uniform distribution, although the latter is not shown.
It is thus seen that the weight approximation, in the simple cases here considered, can lead to a very accurate cubature rule in a narrow range of kernel-dependent values of the parameter. However, there is at the moment no reason to expect this nice property to be preserved for a wider class of functions.
An example application
The previous two sections examined the properties of different weight approximations and their impact in AWPH’s cubature rule. As noted earlier, the cubature rule is but one of several ingredients that are required to set up a numerical scheme that fully solves a conservation law, and the scheme’s overall error comes from compounding those of each individual ingredient. Furthermore, thus far node positions were considered to behave as statistical samples drawn from the function whose integral is being discretised; however, this is a pessimistic assumption in cases were nodes are expected to move in a somewhat ordered fashion. Thus, despite the differences that were observed in the cubature rule under different weight approximations, their impact on the final numerical solution will be strongly influenced by the overall numerical scheme and by the particular problem the conservation law is being used to model. With this in mind, this section aims to showcase solving an example conservation law using different weight approximations. This is additionally used to assert the preservation of the numerical-stability and conservation properties of schemes that use the weight approximation previously proposed in the literature [10] when the latter is replaced by the ones introduced in this work. As in the previous section, for the sake of brevity, the weight approximation will be referred to simply as .
The conservation law that is considered is the system describing inviscid compressible hydrodynamics in three spatial dimensions. With it, the particular problem that is solved is the Sedov blast wave [24], which models a point explosion at the origin of a spherically symmetric medium at rest. This problem is set up such that a supersonic shock wave develops and propagates radially through the medium, and for which a self-similar closed-form solution has been shown to exist [24, 19]. As a consequence, the problem probes a scheme’s ability to correctly transform thermal energy to kinetic energy, and vice versa, in a conservative way, while conserving angular momentum and capturing a strong shock. As such, it is deemed a sensible choice for the goals of this section. The setup chosen mirrors that typically used in astrophysical applications. In arbitrary units, the medium is initially of uniform density equal to unity, vanishingly small pressure equal to , and an adiabatic index . A thermal energy is added at to a single node residing at the origin, and the integration is carried out up to . Finally, nodes are initially distributed in a glass-like distribution with .
The numerical scheme that is used closely resembles the AWPH scheme of Gaburov and Nitadori [10] and the subsequent contribution of Hopkins [15]. It is fully described in Alonso Asensio et al. [1], and here only the major details are given. The scheme uses the RMD together with the cubature rule to transform the initial weak form of the system of conservation laws into a system of ordinary differential equations for the temporal evolution of the conserved variables that each node carries. As it turns out, the final form of the latter is identical to that obtained with a finite-volume discretisation, as the temporal evolution is controlled by the exchange of fluxes through an interaction interface between neighbouring nodes. Thus, the Godunov approach is used, whereby numerical fluxes are obtained by evaluating the physical fluxes with the solution of a one-dimensional Riemann problem defined at the interface of each pair of neighbouring nodes. More specifically, the MUSCL-Hancock scheme (van Leer [30]; van Albada et al. [29]) is used, by which the fluid states at each side of an interface are obtained by linearly extrapolating in space and time the fluid states of the corresponding nodes. After accumulating the fluxes exchanged by each node, a simple Euler step updates their conserved variables in time. Finally, Hopkins [15] introduced two versions of the scheme, namely the meshless-finite-volume and meshless-finite-mass schemes. They differ in the characteristic along which the solution to the Riemann problem is sampled at each interface. In the former, a weighted average of the fluid velocities of the corresponding nodes is used, while in the latter the solution is always sampled along the contact discontinuity. Results are shown only for the meshless-finite-mass scheme, however, as the conclusions are the same for either.
Figure 8 shows the results obtained at using the kernel of Wu (1995) with . It can be seen that there are only minor differences between the results obtained with the , and weight approximations. The most notable difference is in the pressure well behind the shock, where the results for the and approximations are somewhat closer to the self-similar solution, when compared to the results for the approximation. Additionally, the lower-left panel shows that the and approximations are consistently yielding lower densities when compared to the approximation. In fact, in this problem it is seen that the node distributions at all stages of the evolution are very similar between all the weight approximations, thus this density underestimation is yet another manifestation of the negative bias in the weight approximation, which leads to nodes having higher densities for a fixed node distribution when compared to the other two approximations. The differences, however, are mostly seen at the shock front, and the reason is the following. Since this problem involves a spherically symmetric flow, there is no shearing component in the motion. As a consequence, the initially regular node distribution is mostly radially expanded around the location of the explosion, without being significantly distorted. Thus, in this problem the differences between weight approximations are mostly due to node clustering, instead of node disorder. The former is, quite naturally, occurring at the shock front, thus the bulk of the differences in density concentrating there. However, this density difference is not large enough to significantly impact the evolution, as obtained by the scheme being used.
Figure 8. Properties of the Sedov-blast-wave solution at for the three weight approximations indicated in the legend. The top row shows the radial profiles of density, pressure and radial velocity, in which the red line corresponds to the self-similar solution. The middle row shows the respective errors, and the bottom row the differences between the and the approximations with respect to the approximation. The kernel of Wu (1995) was used with . All the curves were obtained by smoothing per-node values with a Gaussian filter.
Finally, although not shown, it has been verified that the evolution of the (numerical) conversion of thermal to kinetic energy is virtually the same for all weight approximations, and that the scheme’s conservation properties, which are detailed in Alonso Asensio et al. [1], are unchanged up to floating-point precision.
Discussion
Weight approximations
The results of § 4 show that the weight approximation proposed by Gaburov and Nitadori [10] has a notable negative bias, which is to say that, on average, it clearly underestimates the true weights. This bias is seen to be a strong function of the parameter, and is mostly in the 10-30% range for the values that are commonly used with the cubic-and quartic-spline kernels. These percentages, however, correspond to cases for which node positions can be considered to behave as random samples drawn from the function whose integral is being discretised, and § 5 provides a justification for this assumption for the case of inviscid compressible hydrodynamics. Thus, the actual bias observed in a given application can likely be very different from the 10-30% mentioned above, for better or for worse. For instance, in cases where some node regularity is expected to be maintained, the bias will naturally be smaller. In contrast, in cases where the nodes can get significantly clustered, either due to the characteristics of the problem being solved or due to numerical artefacts, the bias will likely be larger.
Regarding the impact that the above-mentioned bias has on the accuracy of AWPH’s cubature rule, § 5 shows that, under the assumptions made, it directly leads to an underestimate of the true value of an integral. Thus, the cubature rule inherits the 10-30% error that is present in this weight approximation, once again provided that node positions can be considered to be randomly distributed. Furthermore, results from § 2 indicate that the rule’s asymptotic convergence rate goes as , provided that the bias term in Equation (12) is dominant. However, in the simple cases considered in § 5 this is not seen to occur, as the finite-sample convergence properties are in fact very poor, indicating that in those cases the variance term is the one that is dominant.
In contrast, the weight approximation that emerged as the most suitable from the analysis in § 4, the approximation, has notably better properties as compared to the one proposed by Gaburov and Nitadori [10]. Its bias is much reduced, being mostly below the 5% level, which likewise leads to the cubature rule displaying a similar accuracy in the simple cases considered in § 5. Furthermore, the rule’s accuracy becomes a more complicated function of and , as seen in Figure 7, showing that, with this weight approximation, increasing while keeping constant can in fact be beneficial.
The results obtained for the Sedov-blast-wave problem in § 6 reinforce the previous points, in the sense that the difference between weight approximations is most evident in regions of node disorder and/or node clustering. Given that the Sedov blast wave involves a spherically symmetric flow, thus with no shearing component, node clustering is the most impactful in this case and, naturally, the latter occurs at the shock front. However, the dynamical impact of this difference is seen to be minor in this case, as the most notable effect is a small difference in the pressure profile in the region way behind the shock front. This highlights, once again, that the better properties displayed by the weight approximations derived in this work will not necessarily translate into improvements on the final solution of a conservation law. This will depend, on the one hand, on the problem being solved (more specifically, on the node disorder and clustering that are expected during its evolution) and, on the other hand, on the remaining details of the numerical scheme being used.
Centroid approximations
Even though centroid approximations are derived and compared to their exact calculation, putting them to test in a practical set up is beyond the scope of the present work. Notwithstanding, their practical significance and applicability is briefly discussed in the following.
In the present context, centroids are mainly indicators of the first-order errors in the numerical estimation of an integral. Indeed, as it was mentioned previously, centroidal node distributions lead to second-order-accurate cubature rules (that is, rules that are exact for affine functions). In schemes like AWPH, however, centroids can only be approximated, thus their usage will be profitable only if approximations of the required accuracy are available. In the case of the approximations derived in this work, § 4 shows that, when the nodes can be considered to be randomly distributed, they have a fair amount of scatter. As such, it is perhaps unlikely that their use will lead to more accurate results. However, in cases where nodes can be expected to maintain some degree of regularity, these approximations can prove to be useful.
It should be mentioned that the use of arbitrarily accurate cubature rules, such as those in the Cuba library5, is an alternative worthy of consideration in cases of modest computational load and for which there are no centroid approximations of sufficient accuracy. Such could be the case, for example, when the issue at hand is generating optimal initial conditions (in the form of a centroidal node distribution) for a given problem.
The parameter and the kernel function
The results of § 4 consistently show that, to varying degrees, the bias and dispersion in weight and centroid approximations, with respect to their exact values, improve for increasing values. The same is true, overall, regarding the accuracy of the cubature rule, as per § 5. However, when considering the full solution of a conservation law, there is of course an upper limit for increasing , which is given by spatial-resolution and computational-cost considerations. Indeed, increasing will progressively smear out the spatial features of the solution, as the “region of influence” of the nodes will get progressively larger. Computational cost increases for the same reason. Thus, despite the properties displayed by the spatial discretisation, the optimal choice must be a compromise between all these considerations, and as such must unavoidably be determined in a case-by-case manner.
A similar conclusion can be drawn regarding the choice of kernel function. As with the parameter, § 4 and § 5 clearly show that less centrally concentrated kernels perform better both in terms of weight- and centroid-approximation bias and dispersion, and in terms of accuracy of the cubature rule. The reason for this, as mentioned in § 4.3, is that such kernels have derivatives that are smaller in magnitude, which directly lead to a support function with the same properties, thus making a Taylor-series approximation more profitable. The impact on spatial resolution and computational cost, however, is not as straightforward, since for a given value, more centrally concentrated kernels yield, compared to their counterparts, smaller supports in regions of high node density and larger supports in regions of low node density. Thus, it is difficult to make a general a-priori argument regarding their spatial-resolution and computational-cost properties, and as such the kernel choice should again be made in a case-by-case manner. For instance, in applications where a large number of neighbours is required, due to numerical-stability considerations for example, using a more centrally concentrated kernel provides a mechanism to increase spatial resolution while accounting for this constraint.
The computational cost of the approximations
Computing the analytical derivatives of the support function (Equations (20) and (21)) requires no additional loop over the nodes. They can be obtained in the same loop in which the node supports are calculated, and thus the same is true for all the weight and centroid approximations here proposed. Furthermore, throughout said loop’s execution, the gradient and Hessian-matrix entries can be stored in a single temporary memory buffer. As such, the main penalty introduced by the weight and centroid approximations is an increased amount of floating-point operations required while looping over the neighbours of each node. Naturally, in the case of the approximations, only the gradient needs to be computed, in which case the increment is minor compared to the operations that are already being carried out, especially those required for the RMD.
Summary and conclusions
The present work introduces new weight and centroid approximations for the partition-of-unity-based cubature rule of the AWPH method. Together with the weight approximation previously proposed in the literature, they are then evaluated by comparing them to a computationally expensive exact calculation of weights and centroids. As a result, optimal weight and centroid approximations are selected on the basis of their accuracy and computational cost and complexity. These turn out to be the approximations arising from a second-order Taylor-series expansion of the kernel function and a first-order Taylor-series expansion of the support function; namely, the ones labelled as throughout this work.
This evaluation process revealed that the weight approximation previously proposed in the literature is, on average, a clear underestimate of the exact weights. This underestimation is seen to be a strong function of the parameter, such that it is reduced with increasing ; nonetheless, it lies mostly in the 10-30% range for the values of the latter that are commonly used with the cubic- and quartic-spline kernels. In contrast, the approximation, while still on average underestimating the exact weights, does so at mostly below the 5% level, and with a smaller dependence on the parameter.
Additionally, the accuracy and convergence of AWPH’s cubature rule is studied both theoretically and numerically. On the theoretical side, it is established that the cubature rule, with weights computed as previously proposed in the literature, is equivalent to an importance-sampling Monte Carlo integration scheme in which a kernel density estimate of the node-position distribution is used as the importance-sampling distribution. With this, an asymptotic expression for the mean relative error of the cubature rule is derived, which has contributions coming from the bias, squared bias and variance of the kernel density estimate. It indicates that the cubature rule inherits the bias-variance trade-off from the kernel density estimate, as this asymptotic mean-relative-error expression is not a monotonic function of the parameter. It also predicts that the rule can have very poor convergence properties in situations where the variance term dominates the overall error. Furthermore, it is shown that this asymptotic expression can be used to interpret the finite-sample properties of the cubature rule, as it is successfully used in § 5 as a regression model for the relative errors obtained numerically in the integration of some simple functions.
Extending the analysis of the cubature rule to weight approximations different from the one proposed by Gaburov and Nitadori [10], however, requires a numerical approach. Such an approach shows that the weight approximations derived in this work can have a significant impact in the accuracy of the cubature rule. Due to the assumptions made, this impact is seen to be asymptotically equivalent to the bias in the weight approximations. As a consequence, the improvements in the accuracy of the cubature rule are very similar (up to the validity of such asymptotic equivalence for a finite sample) to those in the bias of weight estimation. As such, the weight approximation previously proposed in the literature leads to a cubature rule that consistently underestimates the value of an integral, with a factor that is mostly in the range of 10-30%. Similarly, the weight approximation leads to a cubature rule with an error that is mostly below the 5% level.
It is important to mention that the validity of these results depends crucially on that of the assumptions made. The most important is that node positions in AWPH can be considered to behave as random samples drawn from the function whose integral is being discretised, and § 5 provides a justification for it for the case of inviscid compressible hydrodynamics. Furthermore, given that the spatial discretisation is but one of the ingredients needed to obtain a scheme that fully solves a conservation law, and that each of them makes its own contribution to the overall error, the impact of the approximations here proposed will additionally depend on all of these other factors. § 6 showcases this by solving the Sedov-blast-wave problem of inviscid compressible hydrodynamics using different weight approximations. In it, for the numerical scheme that is used, it is seen that there are only minor differences in the solutions obtained with each weight approximation. This is the case because, in this problem, a spherically symmetric flow develops, which mostly radially expands the initially regular node distribution, yet not significantly distorting it. As such, the differences between the weight approximations are mostly due to node clustering, which in this problem occurs at the shock front. However, the differences there are not large enough to significantly disrupt the numerical solution as obtained by the scheme that is used, and thus the minor changes that are observed.
Evidently, then, whether or not the better properties displayed by the weight approximations derived in this work will translate into improvements on the final solution of a conservation law depends on the problem being solved (more specifically, on the presence of node clustering and/or disorder) and the numerical scheme being used. Regarding the former, in the context of fluid-flow problems, this is expected to be the case in the presence of large density gradients and/or strong shocks, in low-Mach-number flows (in which the dynamics is dominated by density variations), and in flows with a strong shearing component. Regarding the latter, it is to be expected that higher-order schemes, given their smaller truncation errors, are more likely to exhibit a stronger response.
In conclusion, while introducing new approximations for node weights and centroids for AWPH, this work attempts to lay the groundwork for their consideration in the different applications that the method has. It is hoped that enough information is provided such that the users of the method can make an informed decision regarding their relevance for a given application.
Acknowledgements
To the anonymous referee, whose comments and suggestions contributed to the improvement of the manuscript.
This work is part of grant CEX2025-001609-S, awarded to the Instituto de Astrofísica de Canarias under the Severo Ochoa Centre of Excellence program and funded by MICIU/AEI/10.13039/501100011033. It has been further supported by the Spanish Ministry of Science, Innovation and Universities (Ministerio de Ciencia, Innovación y Universidades, MICIU) through the research grants PGC2018-094975-B-C22 with reference PRE2019-088629 and PID2021-122603NB-C22.
The authors wish to further acknowledge the contribution of Teide High-Performance Computing facilities and Instituto de Astrofísica de Canarias (IAC) High-Performance Computing support team and hardware facilities to the results of this research. TeideHPC facilities are provided by the Instituto Tecnológico y de Energías Renovables (ITER, SA). URL: https://teidehpc.iter.es.
Finally, extensive use was made of the following Python packages: NumPy Harris et al., [14], SciPy Virtanen et al., [32] and Matplotlib Hunter, [17].
The asymptotic relative error of AWPH’s cubature rule
As seen in § 2, AWPH’s cubature rule, with weights computed using the approximation proposed by Gaburov and Nitadori [10], is equivalent to an importance-sampling MCI scheme with a KDE as the importance-sampling distribution. An asymptotic expression (in the sense described in the following) for the mean relative error of such a scheme can be obtained by resorting to results from KDE theory.
The scheme aims to approximate the integral with the random variable
It is assumed that the function is non-negative and that node positions are samples of . The KDE, which is a random variable as well, is given by
where is the kernel function and the random vectors are again the node positions. The use of both and to denote node positions is needed to separate the two stochastic measurements being made, namely those of and . In general, and follow different distributions; however, in the case at hand they are the same sample drawn from .
With a Taylor-series expansion, Equation A.1 can be written as
where and likewise for . Taking the expectation with respect to gives
The numerators in the terms under the summation are the (negative) bias and the mean squared error of the KDE, respectively. KDE theory provides a result for the leading terms of an asymptotic expansion of such quantities (e.g. [26], Equations 4.9 and 4.10)
where and are constants that depend on the kernel function. It should be noted, however, that these asymptotic expressions are valid for a support function, , that is not a function of the data; the latter in the case at hand being the . In AWPH, of course, this is not fulfilled, as Equation (7) is equivalent to
One way to be able to proceed, due to Terrell and Scott [28], is to use the KDE result that if , and simultaneously , then . Thus,
Using this asymptotic value instead makes the results of Equations A.5 usable. Then, substituting these in Equation A.4 and taking the expectation with respect to leads to
in which
Equation A.8 is the sought-out result. It gives the asymptotic scaling with and of the scheme’s mean relative error. Due to the assumptions made, however, care should be taken when using it to understand the finite-sample properties of AWPH’s cubature rule (once again, when its weights are computed as proposed by Gaburov and Nitadori [10]). For instance, in § 5 it is successfully used as a regression model to fit the observed relative errors while numerically integrating some simple functions.
The coefficients in the approximations for weights and centroids
In this appendix, the explicit form taken by the coefficients in the weight and centroid approximations derived in § 3.1 are given. Recalling that the centroid is given by , the approximations are written as
where lower- and upper-case bold-face letters denote column vectors and matrices, respectively. For the sake of conciseness, the expressions that follow are compacted using matrix operations, even though in the one-dimensional case all quantities reduce to scalars. The support function, its gradient vector and its Hessian matrix, evaluated at , are denoted as , and , respectively, while is the identity matrix, and and denote the trace and determinant operations. Evaluations of the kernel-dependent constants , and are given in Tables B.1, B.2 and B.3 for the one-, two- and three-dimensional cases, respectively. Kernel definitions can be found in Cabezón et al. [3], Wu (1995, Table 1) and Dehnen and Aly [6].
| Kernel | |||
| 0.20420308 | 0.11211008 | - | |
| 3/20 | 9/140 | 1/24 | |
| Cubic spline | 1/8 | 3/64 | 85/3072 |
| Quartic spline | 1/10 | 23/750 | 227/15000 |
| Wendland C2 | 1/7 | 5/84 | 5/132 |
| Wendland C4 | 1/10 | 1/33 | 25/1716 |
| Wendland C6 | 1/13 | 5/273 | 25/3536 |
Table B.1. Values of the constants , and for the one-dimensional case. The kernel is defined in Equation (39) (cf. Cabezón et al. [3] and the kernel in Wu (1995, Table 1). The rest are defined in Dehnen and Aly [6].
In order to identify the order of the DK Taylor-series expansion a given term in the expressions that follow comes from, the latter’s combined power in the gradient and Hessian-matrix components must be looked at. This power is linear, quadratic or cubic if the term comes from the first-, second- or third-order Taylor-series-expansion terms, respectively. It should be noted that a gradient factor has been factored out in the centroid (that is, the vector) approximation above, thus the real power of the terms in the , and coefficients is one plus that determined by looking at those terms alone. For example, the is linear for the weight approximation, but quadratic for the centroid. Furthermore, the weight term is cubic, and so is the centroid term .
One spatial dimension
Weight approximation
Centroid approximation
Kernel-dependent constants
Two spatial dimensions
Weight approximation
| Kernel | |||
| 0.24343215 | 0.045573520 | - | |
| Cubic spline | |||
| Quartic spline | |||
| Wendland C2 | |||
| Wendland C4 | |||
| Wendland C6 |
Table B.2. Equivalent of Table B.1 for the two-dimensional case.
Centroid approximation
Kernel-dependent constants
Three spatial dimensions
Weight approximation
where
in which denotes the -th entry of the support’s Hessian matrix.
Centroid approximation
| Kernel | |||
| 0.27450634 | 0.052708747 | - | |
| Cubic spline | |||
| Quartic spline | |||
| Wendland C2 | |||
| Wendland C4 | |||
| Wendland C6 |
Table B.3. Equivalent of Table B.1 for the three-dimensional case.
Kernel-dependent constants
The case of a constant compact-support size
The approach followed to derive weight and centroid approximations in § 3.1 assumes the kernel’s compact-support size is spatially adaptive through the implicit constraint given by Equation (7). Naturally, for problems in which the compact-support size can be set to be a constant, a different approach has to be followed. This appendix details the approximations that can be obtained from one such approach.
The partition-of-unity functions given in Equation (5) can be rewritten using the DK (Equation (13)) as
Since is now a constant, a possibility is to expand the latter’s denominator in a Taylor series around the point , discard third- and higher-order terms, and proceed to evaluate Equation (3). This leads to the following
where and
in which is the number of dimensions, , and likewise for (see Equation (14) for the definition of ). As with the case of the support’s spatial derivatives in § 3.2, care should be taken when evaluating and , since the summations in their right-hand sides contain a term for . Such terms must be evaluated by taking the limit when , which leads to
where . Finally, the constant is the same as that appearing in the variable-support case, and values for it are given in Appendix § 11.
References
- [1]Alonso Asensio, I., Dalla Vecchia, C., Potter, D., Stadel, J., 2023. Mesh-free hydrodynamics in PKDGRAV3 for galaxy formation simulations. Mon. Notices Royal Astron. Soc. 519, 300–317. doi:https://doi.org/10.1093/mnras/stac3447.
- [2]Belytschko, T., 1996. Meshless methods: An overview and recent developments. Comput. Methods Appl. Mech. Eng. 139, 3–47. doi:https://doi.org/10.1016/S0045-7825(96)01078-X.
- [3]Cabezón, R.M., García-Senz, D., Relaño, A., 2008. A one-parameter family of interpolating kernels for smoothed particle hydrodynamics studies. J. Comput. Phys. 227, 8523–8540. doi:https://doi.org/10.1016/j.jcp.2008.06.014.
- [4]Carpinteri, A., Ferro, G., Ventura, G., 2002. The partition of unity quadrature in meshless methods. Int. J. Numer. Methods Eng. 54, 987–1006. doi:https://doi.org/10.1002/nme.455.
- [5]Davis, P.J., Rabinowitz, P., 1984. Methods of Numerical Integration. 2nd ed., Academic Press. doi:https://doi.org/10.1016/C2013-0-10566-1.
- [6]Dehnen, W., Aly, H., 2012. Improving convergence in smoothed particle hydrodynamics simulations without pairing instability. Mon. Notices Royal Astron. Soc. 425, 1068–1082. doi:https://doi.org/10.1111/j.1365-2966.2012.21439.x.
- [7]Duflot, M., Nguyen-Dang, H., 2002. A truly meshless galerkin method based on a moving least squares quadrature. Commun. Numer. Methods Eng. 18, 441–449. doi:https://doi.org/10.1002/cnm.503.
- [8]Engels, H., 1980. Numerical quadrature and cubature. Academic Press.
- [9]Evans, M., Swartz, T., 2000. Approximating Integrals via Monte Carlo and Deterministic Methods. Oxford University Press. doi:https://doi.org/10.1093/oso/9780198502784.001.0001.
- [10]Gaburov, E., Nitadori, K., 2011. Astrophysical weighted particle magnetohydrodynamics. Mon. Notices Royal Astron. Soc. 414, 129–154. doi:https://doi.org/10.1111/j.1365-2966.2011.18313.x.
- [11]Groth, F., Steinwandel, U.P., Valentini, M., Dolag, K., 2023. The cosmological simulation code OPENGADGET3 - implementation of meshless finite mass. Mon. Notices Royal Astron. Soc. 526, 616–644. doi:https://doi.org/10.1093/mnras/stad2717.
- [12]Guessab, A., Nouisser, O., Schmeisser, G., 2006. A Definiteness Theory for Cubature Formulae of Order Two. Constr. Approx. 24, 263–288. doi:https://doi.org/10.1007/s00365-005-0619-4.
- [13]Hahn, T.R., 2005. Cuba - a library for multidimensional numerical integration. Comput. Phys. Commun. 168, 78–95. doi:https://doi.org/10.1016/j.cpc.2005.01.010.
- [14]Harris, C.R., Millman, K.J., van der Walt, S.J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N.J., Kern, R., Picus, M., Hoyer, S., van Kerk-wijk, M.H., Brett, M., Haldane, A., del Río, J.F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., Oliphant, T.E., 2020. Array programming with NumPy. Nat. 585, 357–362. doi:https://doi.org/10.1038/s41586-020-2649-2.
- [15]Hopkins, P.F., 2015. A new class of accurate, mesh-free hydrodynamic simulation methods. Mon. Notices Royal Astron. Soc. 450, 53–110. doi:https://doi.org/10.1093/mnras/stv195.
- [16]Hubber, D.A., Rossoti, G.P., Booth, R.A., 2018. GANDALF - Graphical Astrophysics code for N-body Dynamics And Lagrangian Fluids. Mon. Notices Royal Astron. Soc. 473, 1603–1632. doi:https://doi.org/10.1093/mnras/stx2405.
- [17]Hunter, J.D., 2007. Matplotlib: A 2d graphics environment. Comput. Sci. Eng. 9, 90–95. doi:https://doi.org/10.1109/MCSE.2007.55.
- [19]Kamm, J.R., 2000. Evaluation of the Sedov-von Neumann-Taylor Blast Wave Solution. Technical Report. Los Alamos Natl. Lab.
- [20]Lanson, N., Vila, J.P., 2001. Meshless methods for conservation laws. Math. Comput. Simul. 55, 493–501. doi:https://doi.org/10.1016/S0378-4754(00)00285-8.
- [21]Lanson, N., Vila, J.P., 2008a. Renormalized Meshfree Schemes I: Consistency, Stability, and Hybrid Methods for Conservation Laws. SIAM J. Numer. Anal. 46, 1912–1934. doi:https://doi.org/10.1137/S0036142903427718.
- [23]Moussa, B.B., Lanson, N., Vila, J.P., 1999. Convergence of meshless methods for conservation laws applications to euler equations, in: Hyperbolic Problems: Theory, Numerics, Applications, Birkhäuser Basel. pp. 31–40.DOI
- [24]Sedov, L.I., 1946. Propagation of strong shock waves. J. Appl. Math. Mech. 10, 241–250.
- [25]Shepard, D., 1968. A two-dimensional interpolation function for irregularly-spaced data, in: Proceedings of the 1968 23rd ACM National Conference, Association for Computing Machinery. p. 517–524. doi:https://doi.org/10.1145/800186.810616.
- [26]Silverman, B.W., 1986. Density Estimation for Statistics and Data Analysis. Chapman and Hall. doi:https://doi.org/10.1201/9781315490419.
- [27]Springel, V., 2010. Smoothed Particle Hydrodynamics in Astrophysics. Annu. Rev. Astron. Astrophys. 48, 391–430. doi:https://doi.org/10.1146/annurev-astro-081309-130914.
- [28]Terrell, G.R., Scott, D.W., 1992. Variable kernel density estimation. Ann. Stat. 20, 1236–1265. doi:https://doi.org/10.1214/aos/1176348768.
- [29]van Albada, G.D., van Leer, B., Roberts, Jr., W.W., 1982. A comparative study of computational methods in cosmic gas dynamics. Astron. Astrophys. 108, 76–84.
- [30]van Leer, B., 1979. Towards the Ultimate Conservative Difference Scheme. V. A Second-Order Sequel to Godunov’s Method. J. Comput. Phys. 32, 101–136. doi:https://doi.org/10.1016/0021-9991(79)90145-1.
- [31]Vila, J.P., 1999. On particle weighted methods and smooth particle hydrodynamics. Math. Models Methods Appl. Sci. 09, 161–209. doi:https://doi.org/10.1142/S0218202599000117.
- [32]Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S.J., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A.R.J., Jones, E., Kern, R., Larson, E., Carey, C.J., Polat, İ., Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P., SciPy 1.0 Contributors, 2020. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nat. Methods 17, 261–272. doi:https://doi.org/10.1038/s41592-019-0686-2.







