Scandalously Parallelizable Mesh Generation

David Bortz, Andrew Christlieb
Applied Mathematics, University of Colorado, Boulder, CO 80309-0526
arXiv:1103.5268 [math.NA] (28 Mar 2011)


   author={Bortz}, D. and {Christlieb}, A.},

   title={“{Scandalously Parallelizable Mesh Generation}”},

   journal={ArXiv e-prints},




   keywords={Mathematics – Numerical Analysis, Statistics – Applications, 65N50},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



We propose a novel approach which employs random sampling to generate an accurate non-uniform mesh for numerically solving Partial Differential Equation Boundary Value Problems (PDE-BVP’s). From a uniform probability distribution U over a 1D domain, we sample M discretizations of size N where M>>N. The statistical moments of the solutions to a given BVP on each of the M ultra-sparse meshes provide insight into identifying highly accurate non-uniform meshes. Essentially, we use the pointwise mean and variance of the coarse-grid solutions to construct a mapping Q(x) from uniformly to non-uniformly spaced mesh-points. The error convergence properties of the approximate solution to the PDE-BVP on the non-uniform mesh are superior to a uniform mesh for a certain class of BVP’s. In particular, the method works well for BVP’s with locally non-smooth solutions. We present a framework for studying the sampled sparse-mesh solutions and provide numerical evidence for the utility of this approach as applied to a set of example BVP’s. We conclude with a discussion of how the near-perfect paralellizability of our approach suggests that these strategies have the potential for highly efficient utilization of massively parallel multi-core technologies such as General Purpose Graphics Processing Units (GPGPU’s). We believe that the proposed algorithm is beyond embarrassingly parallel; implementing it on anything but a massively multi-core architecture would be scandalous.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: