Mixed-Precision GPU Acceleration for Large-Scale Minimum Enclosing Ball Problems
Abstract
A mixed-precision GPU-oriented optimization framework is developed for computing the minimum enclosing ball of a collection of balls. The approach is built on an equivalent second-order cone programming reformulation and a relative-type inexact proximal augmented Lagrangian method (ripALM), which provides a high-accuracy optimization backbone while solving the inner subproblems only to a progress-dependent relative accuracy. The proximal augmented Lagrangian inherits a constraint-wise separable structure: its objective, gradient, generalized Hessian, and multiplier updates can be efficiently evaluated on GPUs as parallel maps over the input balls followed by reductions. To further improve efficiency, a mixed-precision reduction strategy is introduced. A low-precision ripALM run identifies balls near the approximate boundary, a high-precision ripALM run refines the reduced problem, and a full a posteriori feasibility check detects and reintroduces any violated discarded balls. Thus, low precision is used only for screening and warm starting, while the final feasibility is enforced against the original problem. Experiments on synthetic and real-data instances show that the proposed methods can compute accurate solutions, with GPU execution providing substantial speedups and mixed-precision reduction further reducing running times on most tested instances.
Related
- Minimum-Area Enclosing Rectangles and the First Neumann Eigenvalue of Planar Convex Domains
- A nonmonotone globalization framework for Anderson acceleration for contractive and nonexpansive fixed point problems
- Acceleration for Affine-coupling problems
- Minimum-Norm Interpolation in Weighted Variation Spaces: Direct and Inverse Problems
- Multi-GPU Acceleration of Interface Problems in FEniCS, with Application to Cardiac Modeling
BibTeX
@misc{liang2026mixedprecision,
title = {{Mixed-Precision GPU Acceleration for Large-Scale Minimum Enclosing Ball Problems}},
author = {Ling Liang and Lei Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.31425},
eprint = {2605.31425},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.31425},
}
RIS
TY - UNPB
TI - Mixed-Precision GPU Acceleration for Large-Scale Minimum Enclosing Ball Problems
AU - Ling Liang
AU - Lei Yang
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2605.31425
UR - https://arxiv.org/abs/2605.31425
AB - A mixed-precision GPU-oriented optimization framework is developed for computing the minimum enclosing ball of a collection of balls. The approach is built on an equivalent second-order cone programming reformulation and a relative-type inexact proximal augmented Lagrangian method (ripALM), which provides a high-accuracy optimization backbone while solving the inner subproblems only to a progress-dependent relative accuracy. The proximal augmented Lagrangian inherits a constraint-wise separable structure: its objective, gradient, generalized Hessian, and multiplier updates can be efficiently evaluated on GPUs as parallel maps over the input balls followed by reductions. To further improve efficiency, a mixed-precision reduction strategy is introduced. A low-precision ripALM run identifies balls near the approximate boundary, a high-precision ripALM run refines the reduced problem, and a full a posteriori feasibility check detects and reintroduces any violated discarded balls. Thus, low precision is used only for screening and warm starting, while the final feasibility is enforced against the original problem. Experiments on synthetic and real-data instances show that the proposed methods can compute accurate solutions, with GPU execution providing substantial speedups and mixed-precision reduction further reducing running times on most tested instances.
ER -