## Scandalously Parallelizable Mesh Generation

Applied Mathematics, University of Colorado, Boulder, CO 80309-0526

arXiv:1103.5268 [math.NA] (28 Mar 2011)

@article{2011arXiv1103.5268B,

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

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

journal={ArXiv e-prints},

archivePrefix={“arXiv”},

eprint={1103.5268},

primaryClass={“math.NA”},

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

year={2011},

month={mar},

adsurl={http://adsabs.harvard.edu/abs/2011arXiv1103.5268B},

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

}

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.

March 29, 2011 by hgpu