Source-linked AI summary
Methods for Rapidly Processing Angular Masks of Next-Generation Galaxy Surveys
Molly E. C. Swanson, Max Tegmark, Andrew J. S. Hamilton, J. Colin Hill
TL;DR
As galaxy surveys grow, processing increasingly complex angular masks becomes computationally challenging, threatening efficient analysis of their large data volumes. The paper introduces pixelization-based algorithms and new MANGLE tools, reducing processing complexity and achieving major speedups while preserving exactness.
Problem
Increasingly large and complex galaxy surveys make accurate, efficient angular-mask processing computationally challenging.
Method
The method partitions angular masks into pixels so polygons are compared only with nearby polygons, using new algorithms implemented in MANGLE.
Results
Processing is exact, accelerates the SDSS mask by about 1200×, and could reduce LSST mask processing time by about 24,000×.
Takeaways & Limitations
The algorithms provide dramatically faster tools for processing current and future survey masks without discrete approximation.
Takeaways & Limitations
The approximate pixels preserve HEALPix hierarchy and latitude structure but not equal area, with average area differences of about 0.08% at Nside = 1.
Abstract
from arXiv · showhide
As galaxy surveys become larger and more complex, keeping track of the completeness, magnitude limit, and other survey parameters as a function of direction on the sky becomes an increasingly challenging computational task. For example, typical angular masks of the Sloan Digital Sky Survey contain about N=300,000 distinct spherical polygons. Managing masks with such large numbers of polygons becomes intractably slow, particularly for tasks that run in time O(N^2) with a naive algorithm, such as finding which polygons overlap each other. Here we present a "divide-and-conquer" solution to this challenge: we first split the angular mask into predefined regions called "pixels," such that each polygon is in only one pixel, and then perform further computations, such as checking for overlap, on the polygons within each pixel separately. This reduces O(N^2) tasks to O(N), and also reduces the important task of determining in which polygon(s) a point on the sky lies from O(N) to O(1), resulting in significant computational speedup. Additionally, we present a method to efficiently convert any angular mask to and from the popular HEALPix format. This method can be generically applied to convert to and from any desired spherical pixelization. We have implemented these techniques in a new version of the mangle software package, which is freely available at http://space.mit.edu/home/tegmark/mangle/, along with complete documentation and example applications. These new methods should prove quite useful to the astronomical community, and since mangle is a generic tool for managing angular masks on a sphere, it has the potential to benefit terrestrial mapmaking applications as well.
1 INTRODUCTION
Galaxy surveys produce increasingly complex angular masks, creating computational challenges for existing mask-processing methods. This paper introduces faster, exact algorithms based on pixelization and integrates MANGLE with HEALPix for efficient cross-format use.
- Motivation: Next-generation surveys require faster and more accurate angular-mask processing to keep systematic uncertainties controlled as statistical uncertainties shrink.Angular masks encode direction-dependent survey parameters such as completeness, magnitude limit, seeing, and dust extinction.
- Motivation: SDSS DR5 contains 340,351 polygons, making computations involving its mask computationally challenging and potentially requiring several months of CPU time.The SDSS mask is more complex than the 2dFGRS mask because of its scanning pattern and numerous masked holes.
- Method: Pixelization splits the mask into regions so each polygon is compared only with nearby polygons, reducing processing from O(N^2) to O(N) after O(N log N) preprocessing.The approach applies a divide-and-conquer strategy previously used in computational geometry but not previously applied to astronomical angular masks.
- Results: For an estimated LSST mask, the new method reduces projected processing time from over 6000 years to ten days, a factor of ∼24,000.The estimate assumes roughly 8 × 10^7 polygons for the LSST large-scale structure mask.
- HEALPix integration: The authors also integrate MANGLE with HEALPix, enabling rapid conversion between piecewise-constant angular masks and continuously varying spherical maps.This supports comparisons between survey masks and data such as CMB or Galactic-dust maps without unnecessary discretization approximation.
- Availability: The new MANGLE tools and algorithms are made publicly available with documentation and example applications for community use.The techniques had already been used in analyses of SDSS data before being released more broadly.
2 MANGLE TERMINOLOGY
MANGLE represents angular masks as weighted spherical polygons and processes them through snapping, balkanization, weighting, and unification. These operations create non-overlapping regions that support mask evaluation and related survey calculations.
- Angular-mask terminology: An angular mask is a union of weighted angular regions bounded by circular edges, with constant weight within each subregion.The formal definition excludes some theoretical spherical piecewise-constant functions but is broad enough for essentially any galaxy survey.
- Angular-mask terminology: A spherical polygon is a region bounded by edges that are parts of circles on the sphere, and an angular mask is a union of weighted non-overlapping polygons.These polygons are the fundamental building blocks used to represent survey selection functions.
- Processing steps: MANGLE processing consists of snapping, balkanizing, weighting, and unifying an angular mask.The steps are designed to prepare the mask for subsequent function evaluation and calculations.
- Processing steps: Snapping aligns nearly coincident polygon edges exactly, preventing numerical issues caused by roundoff or imprecision in the mask definition.The operation addresses boundaries intended to abut perfectly but represented with small numerical discrepancies.
- Processing steps: Balkanization resolves overlaps and disconnected geometries into non-overlapping connected polygons representing distinct regions with potentially different weights.It fragments overlapping polygons and subdivides polygons with disconnected geometry.
- Processing steps: After balkanization, weights encode survey completeness or another desired parameter, while unification removes zero-weight polygons and combines neighboring polygons with equal weights.The unified representation reduces clutter and makes subsequent calculations more efficient.
- Applications: Processed masks support pointwise function evaluation, random sampling with the survey selection function, angular integrals, and spherical-harmonic calculations.MANGLE provides utilities for these downstream tasks.
3 SPEEDUP: PIXELIZATION
Pixelization replaces expensive all-pairs polygon comparisons with localized processing inside hierarchical sky regions, while preserving the mask exactly. The resulting algorithms substantially accelerate mask processing and point-in-polygon identification for SDSS and larger surveys.
- Pixelization algorithm: Pixelization splits polygons along predefined pixel boundaries so subsequent comparisons occur only among polygons within the same pixel.This divide-and-conquer step is applied before snapping, balkanization, and unification.
- Pixelization algorithm: O(N) processing is achieved after an O(N log M) pixelization preprocessing step when the number of pixels M scales with the polygon count N.The recursive algorithm exploits the hierarchical structure of the pixelization scheme.
- Speed trials: ∼1200: pixelization reduces processing time for the full SDSS DR5 mask containing about 300,000 polygons.For a possible co-added LSST mask with ∼10^8 polygons, the projected reduction reaches ∼24,000.
- Pixelization algorithm: O(N/M) point identification replaces testing every polygon, because the appropriate pixel can be found in O(1) time before checking polygons inside it.With pixels chosen roughly proportional to the number of polygons, identification time becomes independent of the total polygon count.
- Pixelization algorithm: The method introduces no approximation: pixelization only organizes nearby polygons, and post-balkanization masks retain the original information.Pixelization increases intermediate polygon complexity in the illustrative example but preserves the final mask content.
- Pixelization schemes: The simple scheme uses hierarchical equal-area quadtree pixels, while SDSSPix aligns hierarchical equal-area pixels with SDSS survey coordinates.The simple scheme uses celestial coordinates; SDSSPix is based on the rotated λ and η coordinate system.
- Speed trials: Nearly 500: pixelization reduces the time to identify the polygons containing all SDSS galaxies.The fastest SDSS configuration uses SDSSPix with adaptive resolution; its optimum Nmax is 46, compared with 40 for the simple scheme.
4 UNIFICATION WITH HEALPIX AND OTHER PIXELIZED TOOLS
The paper integrates MANGLE with HEALPix by importing and exporting spherical maps through polygon-based approximations and rasterization. The resulting two-way conversion supports comparisons between piecewise-constant survey masks and continuously varying sky maps, with area errors becoming negligible at typical resolutions.
- HEALPix: HEALPix is a hierarchical, equal-area, isolatitudinal spherical pixelization scheme with 12N_side^2 pixels at resolution Nside.Higher resolutions are formed by recursively subdividing each pixel into four children.
- Applications: The conversion framework applies to comparisons between piecewise-constant spherical functions and continuously sampled functions, including survey masks and CMB maps.It also enables approximate spherical-harmonic computations using existing HEALPix tools.
- Importing HEALPix maps: MANGLE adds a HEALPix polygon format and a rasterize utility for converting between HEALPix weights and angular-mask polygons.The implementation accepts weights indexed by HEALPix pixels and constructs approximately equivalent spherical polygons.
- Approximation: The approximate HEALPix polygons preserve hierarchical and isolatitudinal structure but not exact equal areas.At Nside = 1, their areas differ from actual HEALPix pixels by about 0.08% on average.
- Exporting polygon files: Rasterization intersects mask polygons with user-defined pixels and assigns each output pixel the input mask’s area-averaged weight.The resulting polygon file can be converted into a FITS file readable by HEALPix software.
5 SUMMARY
The paper presents hierarchical pixelization algorithms that accelerate angular-mask processing without discretely approximating the mask. They reduce processing and point-location complexity and provide especially large speedups for SDSS and projected LSST masks, while also adding HEALPix interoperability.
- Algorithms: Pixelization divides the sky into hierarchical regions so key operations compare polygons only within the same pixel.The quadtree preprocessing costs O(N log N), while subsequent mask processing scales as O(N).
- Algorithms: Point-location complexity falls from O(N) to O(1) after pixelization.This accelerates determining which polygon contains a given sky position.
- Speed improvements: The method is exact and accelerates SDSS-mask processing by about 1200×, while reducing SDSS galaxy point-location time by nearly 500×.The reported gains do not rely on a discrete approximation to the mask.
- Speed improvements: Processing time for the LSST large-scale-structure mask could be reduced by about 24,000×.This is presented as a projected gain for future surveys.
- HEALPix integration: The new MANGLE features convert between spherical-polygon masks and HEALPix sky maps for joint use with survey and CMB analyses.The updated software is freely available and intended for next-generation surveys.