[EM] High Order Numerical Cubature (Clean and Simple)

[Daniel Carrera]

On Thu, Feb 3, 2022 at 12:46 PM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> Forget every article I sent you about numerical quadrature/cubature ...
> last night,  in the night, vast simplification came to me ... it is much
> easier to generalize the midpoint rule than the trapezoid rule for cubature
> in arbitrarily many dimensions.
>
> There is historical precedence for this idea ... ... the    *Gragg–Bulirsch–Stoer
> (GBS) * numerical solution method for ODE's uses a combination of the
> midpoint rule and Richardson extrapolation for high order accuracy. We are
> going to generalize this to multivariate quadrature or "cubature."
>
> Given a simplex (the convex hull of a finite set of points having affine
> independence) we form a tree (more of a dendrite, really) whose root node
> is the average of the vertices of the simplex (i.e. the "barycenter" of the
> simplex), and whose descendants become denser in the interior of the
> simplex with each successive generation.
>
> This "space filling" has to be done with sufficient fractal self
> symmetrical regularity to ensure that our method can be highly accurate and
> efficient. Don't worry ... it turned out to be way simpler than I could
> have possibly hoped for!
>
> As we said, the first node of the tree is the baryceenter of the simplex.
> The immediate children of that node are the points precisely half way from
> the baryceenter to the respective vertices of the simplex. [The simplex is
> the convex hull of these vertices.]
>
> The respective arrows (or "vectors") from the barycenter to the vertices
> serve as the only directions needed for finding all of the children of
> every node.
>

I think you are onto something. The exact way you phrased the algorithm
seems to only create points along the lines joining a vertex and the
barycenter. If I understood that correctly, then it is not "space filling".
But we can easily resolve that. Your key insight is that the simplex is
convex and a sum of vertices and/or points interior to the simplex will
give you a point that is also interior to the simplex.

One way to create points that are guaranteed to be inside the simplex is to
grab the vertices and do any weighted sum, as long as the weights add up to
1. You could just pick those points randomly, but that wouldn't generalize
the midpoint rule the way that the barycenter does. Finally, everything
that we've said up to this point applies to any convex hull; not just
simplices. In an N-dimensional space you can grab any set of N+1 vertices
from your convex hull and their barycenter will be somewhere inside the
convex hull as well.

This last comment about taking N+1 vertices does not fundamentally resolve
anything. That's still a small number of points. To truly get a series of
space-filling points that generalizes the midpoint rule, we can keep
computing barycenters:

1) Let S = some simplex. S has N+1 points in an N-dimensional space.
2) Compute b = Barycenter(S)
3) Add 'b' to the list of points:  S -> {S, b}
4) Select a random set of N+1 points from S
5) Compute their barycenter and add that to S.
6) GOTO (4)


The same algorithm can work for a convex hull.

1) Let C = some convex hull with > N+1 points in an N-dimensional space.
2) Select a random set of N+1 points from C.
3) Compute the barycenter of those points and add that to C.
4) GOTO (2)

Does this sound right or did I just misunderstand your algorithm?

Cheers,
-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220203/3e700390/attachment.html>