pith. sign in

arxiv: 2605.31425 · v1 · pith:2ZMM4ETGnew · submitted 2026-05-29 · 🧮 math.OC

Mixed-Precision GPU Acceleration for Large-Scale Minimum Enclosing Ball Problems

Ling Liang , Lei Yang This is my paper

Pith reviewed 2026-06-28 21:36 UTC · model grok-4.3

classification 🧮 math.OC
keywords minimum enclosing ballmixed precisionGPU accelerationsecond-order cone programmingproximal augmented Lagrangianlarge-scale optimizationinexact methods
0
0 comments X

The pith

A mixed-precision GPU framework solves large minimum enclosing ball problems faster than CPU solvers while keeping high accuracy.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a GPU-oriented method for the minimum enclosing ball of a collection of balls by first rewriting the task as an equivalent second-order cone program. It then applies a relative inexact proximal augmented Lagrangian method whose updates separate across balls, allowing direct parallel evaluation and reduction on the GPU. A mixed-precision tactic runs a cheap low-precision pass to screen for balls near the boundary, solves the smaller problem at high precision, and finally checks feasibility against the full original set to reintroduce any missed balls. Numerical tests indicate the resulting ripALM and mixed-precision versions reach the target accuracy yet run substantially quicker than existing CPU geometric codes and general conic solvers on large instances. If the screening step works as intended, the approach lets users tackle bigger enclosing-ball problems without needing full high-precision work on every ball.

Core claim

The central claim is that ripALM and mixed-precision ripALM achieve high accuracy and are substantially faster than the tested CPU-based geometric software and general-purpose conic solvers on large-scale instances.

What carries the argument

A relative-type inexact proximal augmented Lagrangian method (ripALM) equipped with a mixed-precision reduction that screens with low precision, refines the reduced problem at high precision, and applies an a-posteriori feasibility check on the original data.

If this is right

  • The separable structure of the proximal augmented Lagrangian permits efficient parallel GPU maps followed by reductions.
  • Low precision is used only for screening and warm-starting while final feasibility is enforced on the original problem.
  • The method reaches high accuracy on large instances.
  • It runs substantially faster than CPU geometric software and general conic solvers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same screening-plus-refinement pattern could be tried on other large convex problems whose constraints separate across data points.
  • Memory savings from discarding most balls early may become useful when the input set exceeds GPU memory limits.
  • One could test whether the number of reintroduced balls stays small across different distributions of input ball radii and centers.

Load-bearing premise

The low-precision screening step can reliably identify balls near the approximate boundary so that the subsequent high-precision solve on the reduced set plus a posteriori feasibility check recovers a valid solution to the original problem without excessive reintroductions.

What would settle it

On a large test instance the mixed-precision run produces a final ball that leaves many originally discarded balls outside after the feasibility check, or the reported accuracy drops below the claimed level.

Figures

Figures reproduced from arXiv: 2605.31425 by Lei Yang, Ling Liang.

Figure 1
Figure 1. Figure 1: Toy two-dimensional example illustrating the mixed-precision reduction strategy. Left: [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of different solvers on the generated MEB instances. Each row corresponds [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: High-dimensional performance of ripALM and mp-ripALM. Left: computational time. [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
read the original 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. Numerical experiments show that ripALM and mixed-precision ripALM achieve high accuracy and are substantially faster than the tested CPU-based geometric software and general-purpose conic solvers on large-scale instances.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript develops a mixed-precision GPU-oriented optimization framework for the minimum enclosing ball problem over a collection of balls. It reformulates the problem as an equivalent second-order cone program and solves it via a relative inexact proximal augmented Lagrangian method (ripALM) whose inner subproblems are solved only to a progress-dependent relative accuracy. The proximal augmented Lagrangian admits a constraint-wise separable structure that permits efficient parallel GPU evaluation of the objective, gradient, generalized Hessian, and multiplier updates. A mixed-precision reduction strategy is introduced in which a low-precision ripALM run screens for balls near the approximate boundary, a high-precision ripALM run refines the reduced problem, and an a-posteriori feasibility check on the original instance detects and reintroduces any violated discarded balls. Numerical experiments are reported to show that both ripALM and its mixed-precision variant attain high accuracy while delivering substantial speedups relative to CPU-based geometric software and general-purpose conic solvers on large-scale instances.

Significance. If the reported performance and accuracy claims are substantiated by detailed, reproducible experiments, the work would constitute a meaningful practical advance for large-scale minimum-enclosing-ball computations. The combination of an SOCP reformulation, relative inexact proximal ALM, GPU-friendly separability, and a controlled mixed-precision screening strategy offers a concrete route to scaling beyond the reach of existing CPU geometric and conic solvers. The absence of free parameters or self-referential definitions in the algorithmic construction is a positive feature.

major comments (2)
  1. [Abstract and Numerical Experiments] Abstract and Numerical Experiments section: the central claim that ripALM and mixed-precision ripALM achieve high accuracy and are substantially faster than the tested baselines rests on numerical experiments, yet the manuscript supplies no information on the dimensions and cardinalities of the test instances, the precise error metrics employed, the implementation details or versions of the CPU-based geometric software and conic solvers used as baselines, or any statistical controls (multiple runs, variance, or timing methodology). This omission leaves the performance assertions with limited verifiable support.
  2. [Mixed-precision reduction strategy] Mixed-precision reduction strategy (described in the abstract and the algorithmic development): the reliability of the low-precision screening step in correctly identifying balls near the approximate boundary, such that the subsequent high-precision solve plus a-posteriori feasibility check recovers a valid solution without excessive reintroductions, is load-bearing for the claimed efficiency gains. The manuscript provides no quantitative characterization of how often or under what conditions the check triggers reintroductions, nor any worst-case or probabilistic guarantee on the screening quality.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and positive overall assessment. We address the two major comments below and will revise the manuscript accordingly to improve clarity and verifiability.

read point-by-point responses

  1. Referee: [Abstract and Numerical Experiments] Abstract and Numerical Experiments section: the central claim that ripALM and mixed-precision ripALM achieve high accuracy and are substantially faster than the tested baselines rests on numerical experiments, yet the manuscript supplies no information on the dimensions and cardinalities of the test instances, the precise error metrics employed, the implementation details or versions of the CPU-based geometric software and conic solvers used as baselines, or any statistical controls (multiple runs, variance, or timing methodology). This omission leaves the performance assertions with limited verifiable support.

    Authors: We agree that the manuscript currently lacks these experimental details, which limits the ability to fully verify the claims. In the revised version we will expand the Numerical Experiments section (and update the abstract if needed) to explicitly report: the dimensions and cardinalities of all test instances; the precise error metrics (e.g., relative duality gap, feasibility violation, and accuracy tolerances); the exact versions, configurations, and implementation details of all baseline solvers; and the statistical protocol including number of runs, variance reporting, and timing methodology. revision: yes

  2. Referee: [Mixed-precision reduction strategy] Mixed-precision reduction strategy (described in the abstract and the algorithmic development): the reliability of the low-precision screening step in correctly identifying balls near the approximate boundary, such that the subsequent high-precision solve plus a-posteriori feasibility check recovers a valid solution without excessive reintroductions, is load-bearing for the claimed efficiency gains. The manuscript provides no quantitative characterization of how often or under what conditions the check triggers reintroductions, nor any worst-case or probabilistic guarantee on the screening quality.

    Authors: The a-posteriori feasibility check on the original instance is intended to guarantee that any discarded balls violating the approximate solution are reintroduced, thereby ensuring correctness independent of screening quality. We acknowledge that the current manuscript does not provide quantitative data on reintroduction frequency or conditions. In the revision we will add empirical statistics from the reported experiments (e.g., average and maximum number of reintroductions per instance class) and discuss observed conditions under which the screening performs well. We do not provide worst-case or probabilistic guarantees, as the screening step is a practical heuristic; the check serves as the correctness safeguard. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained algorithmic construction

full rationale

The paper describes an optimization algorithm built on a standard SOCP reformulation of the minimum enclosing ball problem, an inexact proximal augmented Lagrangian method (ripALM) with separable structure for GPU parallelism, and a mixed-precision screening/refinement strategy with a posteriori feasibility check. No equations or claims reduce a 'prediction' or central result to a fitted parameter, self-definition, or self-citation chain by construction. Performance claims rest on external numerical comparisons to CPU solvers and conic solvers rather than internal tautologies. The derivation chain is independent of the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review is based solely on the abstract; no explicit free parameters, ad-hoc axioms, or invented entities are detailed beyond the standard assumption that the problem admits an SOCP reformulation.

axioms (1)
  • domain assumption The minimum enclosing ball problem admits an equivalent second-order cone programming reformulation
    Invoked in the abstract as the foundation for applying ripALM.

pith-pipeline@v0.9.1-grok · 5722 in / 1294 out tokens · 29418 ms · 2026-06-28T21:36:04.337720+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points.Journal of the ACM, 51(4):606–635, 2004

    2004

  2. [2]

    P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Geometric approximation via coresets. InCombinatorial and Computational Geometry, volume 52 ofMSRI Publications, pages 1–30. Cambridge University Press, Cambridge, 2005

    2005

  3. [3]

    B˘ adoiu and K

    M. B˘ adoiu and K. L. Clarkson. Smaller core-sets for balls. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 801–802, Baltimore, MD, 2003. SIAM

    2003

  4. [4]

    Beck.First-Order Methods in Optimization

    A. Beck.First-Order Methods in Optimization. SIAM, Philadelphia, PA, 2017

    2017

  5. [5]

    Boyd and L

    S. Boyd and L. Vandenberghe.Convex Optimization. Cambridge University Press, Cambridge, 2004

    2004

  6. [6]

    X. D. Chen, D. F. Sun, and J. Sun. Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems.Com- putational Optimization and Applications, 25(1–3):39–56, 2003. 16

    2003

  7. [7]

    F. H. Clarke.Optimization and Nonsmooth Analysis. SIAM, Philadelphia, PA, 1990

    1990

  8. [8]

    K. L. Clarkson. Coresets, sparse greedy approximation, and the Frank–Wolfe algorithm.ACM Transactions on Algorithms, 6(4), 2010

    2010

  9. [9]

    Domahidi, E

    A. Domahidi, E. Chu, and S. Boyd. ECOS: An SOCP solver for embedded systems. In European Control Conference, pages 3071–3076, 2013

    2013

  10. [10]

    Drezner and H

    Z. Drezner and H. W. Hamacher, editors.Facility Location: Applications and Theory. Springer, Berlin, Heidelberg, 2002

    2002

  11. [11]

    Feldman and M

    D. Feldman and M. Langberg. A unified framework for approximating and clustering data. InProceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 569–578, San Jose, CA, 2011. ACM

    2011

  12. [12]

    Fischer, B

    K. Fischer, B. G¨ artner, and M. Kutz. Fast smallest-enclosing-ball computation in high dimen- sions. InAlgorithms – ESA 2003, volume 2832 ofLecture Notes in Computer Science, pages 630–641. Springer, Berlin, Heidelberg, 2003

    2003

  13. [13]

    G¨ artner

    B. G¨ artner. Fast and robust smallest enclosing balls. InAlgorithms – ESA 1999, volume 1643 ofLecture Notes in Computer Science, pages 325–338. Springer, Berlin, Heidelberg, 1999

    1999

  14. [14]

    P. J. Goulart and Y. Chen. Clarabel: An interior-point solver for conic programs with quadratic objectives.arXiv preprint arXiv:2405.12762, 2024

    work page arXiv 2024

  15. [15]

    K¨ allberg and T

    L. K¨ allberg and T. Larsson. Accelerated computation of minimum enclosing balls by GPU parallelization and distance filtering. InProceedings of SIGRAD 2014: Visual Computing, volume 106 ofLink¨ oping Electronic Conference Proceedings, pages 57–65, Link¨ oping, Sweden,

    2014

  16. [16]

    Link¨ oping University Electronic Press

  17. [17]

    Kumar, J

    P. Kumar, J. S. B. Mitchell, and E. A. Yildirim. Approximate minimum enclosing balls in high dimensions using core-sets.ACM Journal of Experimental Algorithmics, 8:1.1 – es, 2003

    2003

  18. [18]

    Liang, D

    L. Liang, D. F. Sun, and K.-C. Toh. An inexact augmented Lagrangian method for second- order cone programming with applications.SIAM Journal on Optimization, 31(3):1748–1773, 2021

    2021

  19. [19]

    N. Megiddo. Linear-time algorithms for linear programming inR 3 and related problems.SIAM Journal on Computing, 12(4):759–776, 1983

    1983

  20. [20]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii.Interior-Point Polynomial Algorithms in Convex Program- ming. SIAM, Philadelphia, PA, 1994

    1994

  21. [21]

    O’Donoghue, E

    B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications, 169 (3):1042–1068, 2016

    2016

  22. [22]

    R. T. Rockafellar and R. J.-B. Wets.Variational Analysis. Springer, Berlin, Heidelberg, 1998

    1998

  23. [23]

    J. F. Sturm. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11(1–4):625–653, 1999

    1999

  24. [24]

    D. M. J. Tax and R. P. W. Duin. Support vector data description.Machine Learning, 54: 45–66, 2004. 17

    2004

  25. [25]

    CGAL Editorial Board, 6.1.1 edition,

    The CGAL Project.CGAL User and Reference Manual. CGAL Editorial Board, 6.1.1 edition,

  26. [26]

    URLhttps://doc.cgal.org/6.1.1/Manual/packages.html

  27. [27]

    K.-C. Toh, M. J. Todd, and R. H. T¨ ut¨ unc¨ u. SDPT3: A MATLAB software package for semidefinite programming, version 1.3.Optimization Methods and Software, 11(1–4):545–581, 1999

    1999

  28. [28]

    I. W. Tsang, J. T. Kwok, and P.-M. Cheung. Core vector machines: Fast SVM training on very large data sets.Journal of Machine Learning Research, 6:363–392, 2005

    2005

  29. [29]

    Y. Wang, Y. Li, and K.-L. Tan. Coresets for minimum enclosing balls over sliding windows. InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 314–323, Anchorage, AK, 2019. ACM

    2019

  30. [30]

    E. Welzl. Smallest enclosing disks (balls and ellipsoids). InNew Results and New Trends in Computer Science, volume 555 ofLecture Notes in Computer Science, pages 359–370. Springer, Berlin, Heidelberg, 1991

    1991

  31. [31]

    L. Yang, J. Zhu, L. Liang, and K.-C. Toh. Convergence of a relative-type inexact proximal ALM for convex nonlinear programming.arXiv preprint arXiv:2510.25261, 2025

    work page arXiv 2025

  32. [32]

    E. A. Yildirim. Two algorithms for the minimum enclosing ball problem.SIAM Journal on Optimization, 19(3):1368–1391, 2008

    2008

  33. [33]

    X.-Y. Zhao, D. F. Sun, and K.-C. Toh. A Newton–CG augmented Lagrangian method for semidefinite programming.SIAM Journal on Optimization, 20(4):1737–1765, 2010

    2010

  34. [34]

    Zhou, K.-C

    G. Zhou, K.-C. Toh, and J. Sun. Efficient algorithms for the smallest enclosing ball problem. Computational Optimization and Applications, 30(2):147–160, 2005

    2005

  35. [35]

    J. Zhu, L. Liang, L. Yang, and K.-C. Toh. ripALM: A relative-type inexact proximal aug- mented Lagrangian method for linearly constrained convex optimization.arXiv preprint arXiv:2411.13267, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  36. [36]

    J. Zhu, H. Wang, L. Liang, and L. Yang. D-ripALM: A tuning-friendly decentralized relative- type inexact proximal augmented Lagrangian method.arXiv preprint arXiv:2602.06398, 2026. 18

    work page arXiv 2026