×

Distributed decomposition over hyperspherical domains. (English) Zbl 1183.65060

Bercovier, Michel (ed.) et al., Domain decomposition methods in science and engineering XVIII. Selected papers based on the presentations at the 18th international conference of domain decomposition methods, Jerusalem, Israel, January 12–17, 2008. Berlin: Springer (ISBN 978-3-642-02676-8/hbk; 978-3-642-04466-3/ebook). Lecture Notes in Computational Science and Engineering 70, 251-258 (2009).
Summary: We are motivated by an optimization problem arising in computational scaling for optical lithography that reduces to finding the point of minimum radius that lies outside of the union of a set of diamonds centered at the origin of Euclidean space of arbitrary dimension. A decomposition of the feasible region into convex regions suggests a heuristic sampling approach to finding the global minimum.
We describe a technique for decomposing the surface of a hypersphere of arbitrary dimension, both exactiy and approximately, into a specific number of regions of equal area and small diameter. The decomposition generalizes to any problem posed on a spherical domain where regularity of the decomposition is an important concern. We specifically consider a storage-optimized decomposition and analyze its performance. We also show how the decomposition can parallelize the sampling process by assigning each processor a subset of points on the hypersphere to sample. Finally, we describe a freely available C++ software package that implements the storage-optimized decomposition.
For the entire collection see [Zbl 1178.65001].

MSC:

65K05 Numerical mathematical programming methods
90C05 Linear programming
65Y05 Parallel numerical computation
82D37 Statistical mechanics of semiconductors
PDFBibTeX XMLCite
Full Text: DOI