TY - GEN

T1 - Distributed decomposition over hyperspherical domains

AU - Ahmadia, Aron

AU - Keyes, David

AU - Melville, David

AU - Rosenbluth, Alan

AU - Tian, Kehan

PY - 2009

Y1 - 2009

N2 - 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 exactly 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.

AB - 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 exactly 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.

UR - http://www.scopus.com/inward/record.url?scp=78651590823&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02677-5_27

DO - 10.1007/978-3-642-02677-5_27

M3 - Conference contribution

AN - SCOPUS:78651590823

SN - 9783642026768

T3 - Lecture Notes in Computational Science and Engineering

SP - 251

EP - 258

BT - Domain Decomposition Methods in Science and Engineering XVIII

T2 - 18th International Conference of Domain Decomposition Methods

Y2 - 12 January 2008 through 17 January 2008

ER -