<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Feb 3, 2022 at 12:46 PM Forest Simmons <<a href="mailto:forest.simmons21@gmail.com">forest.simmons21@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">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.<div dir="auto"><br></div><div dir="auto">There is historical precedence for this idea ... ... the    <b style="margin:0px;padding:0px;border:0px;line-height:inherit;font-family:-apple-system,blinkmacsystemfont,"segoe ui",roboto,lato,helvetica,arial,sans-serif;font-size:16px;vertical-align:baseline;background:none rgb(255,255,255);color:rgb(32,33,34)">Gragg–Bulirsch–Stoer (GBS) </b> 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."</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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!</div><div dir="auto"><br></div><div dir="auto">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.]</div><div dir="auto"><br></div><div dir="auto">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.</div></div></blockquote><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">1) Let S = some simplex. S has N+1 points in an N-dimensional space.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">2) Compute b = Barycenter(S)</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">3) Add 'b' to the list of points:  S -> {S, b}</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">4) Select a random set of N+1 points from S</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">5) Compute their barycenter and add that to S.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">6) GOTO (4)</div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">The same algorithm can work for a convex hull.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">1) Let C = some convex hull with > N+1 points in an N-dimensional space.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">2) Select a random set of N+1 points from C.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">3) Compute the barycenter of those points and add that to C.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">4) GOTO (2)</div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Does this sound right or did I just misunderstand your algorithm?<br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Cheers,</div></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="trebuchet ms, sans-serif">Dr. Daniel Carrera</font></div><div dir="ltr"><font face="trebuchet ms, sans-serif">Postdoctoral Research Associate</font></div><div><font face="trebuchet ms, sans-serif">Iowa State University</font></div></div></div></div></div></div></div></div></div></div></div>