Distributed decomposition over hyperspherical domains

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

*Corresponding author for this work

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

Abstract

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
Pages251-258
Number of pages8
DOIs
StatePublished - Oct 12 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

Other

Other18th International Conference of Domain Decomposition Methods
CountryIsrael
CityJerusalem
Period01/12/0801/17/08

ASJC Scopus subject areas

  • Modeling and Simulation
  • Engineering(all)
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Mathematics

Fingerprint

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

Cite this