Distributed decomposition over hyperspherical domains

Aron Ahmadia*, David Keyes, David Melville, Alan Rosenbluth, Kehan Tian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.

Original languageEnglish (US)
Title of host publicationDomain Decomposition Methods in Science and Engineering XVIII
Number of pages8
StatePublished - 2009
Event18th International Conference of Domain Decomposition Methods - Jerusalem, Israel
Duration: Jan 12 2008Jan 17 2008

Publication series

NameLecture Notes in Computational Science and Engineering
Volume70 LNCSE
ISSN (Print)1439-7358


Other18th International Conference of Domain Decomposition Methods

ASJC Scopus subject areas

  • Modeling and Simulation
  • General Engineering
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Mathematics


Dive into the research topics of 'Distributed decomposition over hyperspherical domains'. Together they form a unique fingerprint.

Cite this