pith. sign in

arxiv: 2507.00617 · v2 · pith:DGHWRQMXnew · submitted 2025-07-01 · 🧮 math.NA · cs.NA· math.OC

Accelerating MPGP-type Methods Through Preconditioning

Jakub Kru\v{z}\'ik , David Hor\'ak This is my paper

Pith reviewed 2026-05-22 00:14 UTC · model grok-4.3

classification 🧮 math.NA cs.NAmath.OC
keywords quadratic programmingpreconditioningMPGPactive-set methodscondition-number boundsfree set
0
0 comments X

The pith

An approximate preconditioning-in-face variant for MPGP methods computes the inner preconditioner only once while admitting a sharp bound on the condition number of the preconditioned operator.

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

This paper develops an approximate preconditioning technique for MPGP-type methods that solve quadratic programming problems with inequality constraints. The approach restricts preconditioning to the free set and investigates a version that computes the inner preconditioner once on the initial free set rather than recomputing or updating it at every change. Analysis establishes that the resulting approximation error stays controlled and yields a sharp bound on the condition number of the overall preconditioned operator. Numerical tests on representative problems show that the method produces very large speedups while keeping outer-iteration convergence rates comparable to the exact recomputation version.

Core claim

The paper shows that an approximate preconditioning-in-face operator, obtained by computing the inner preconditioner only once after the starting free set is identified, produces a preconditioned system whose condition number satisfies a sharp explicit bound and that this construction accelerates MPGP iterations by large factors in practice without requiring updates at subsequent free-set changes.

What carries the argument

The approximate preconditioning-in-face operator that freezes the inner preconditioner after its single initial computation on the starting free set.

If this is right

  • The approximation error introduced by a single initial computation of the inner preconditioner stays bounded.
  • The condition number of the resulting preconditioned operator admits a sharp, explicit upper bound.
  • Numerical experiments on quadratic programs exhibit very large speedups relative to the version that recomputes the inner preconditioner at every free-set change.
  • Outer iteration counts remain comparable to those of the exact preconditioning-in-face method for the tested problem classes.

Where Pith is reading between the lines

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

  • The same one-time freezing idea could be applied inside other active-set quadratic-programming algorithms that rely on repeated free-set identification.
  • An adaptive rule that triggers a fresh preconditioner computation only when the free set has changed by more than a chosen fraction might combine the speed of the approximate version with better worst-case robustness.
  • The bounded-condition-number guarantee suggests the method could scale to larger constrained problems arising in engineering design and machine-learning training where repeated preconditioner assembly is the dominant cost.

Load-bearing premise

The error introduced by freezing the inner preconditioner after the initial free set remains small enough that the outer MPGP iteration still converges at a rate comparable to the exact preconditioning-in-face version.

What would settle it

A test problem in which the free set changes substantially after the first iteration and the approximate method requires many more outer iterations than the exact recomputation version would show that the approximation degrades convergence too severely for practical use.

Figures

Figures reproduced from arXiv: 2507.00617 by David Hor\'ak, Jakub Kru\v{z}\'ik.

Figure 1
Figure 1. Figure 1: Eigenvalues of the journal bearing problem with 50x50 grid points (2,500 DOFs) [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Condition number, free set size, and rank of the off-diagonal block for the journal [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
read the original abstract

This work investigates the acceleration of MPGP-type algorithms using preconditioning for the solution of quadratic programming problems. The preconditioning needs to be done only on the free set so as not to change the constraints. A variant of preconditioning restricted to the free set is the preconditioning in face. The inner preconditioner in preconditioning in face needs to be recomputed or updated every time the free set changes. Here, we investigate an approximate variant of preconditioning in face that computes the inner preconditioner only once. We analyze the error of the approximate variant, give a sharp bound on the condition number of the preconditioned operator, and provide numerical experiments demonstrating that very large speedups can be achieved by the approximate variant.

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

1 major / 1 minor

Summary. The manuscript proposes an approximate variant of preconditioning-in-face for MPGP-type algorithms solving quadratic programming problems. In contrast to the standard approach that recomputes the inner preconditioner whenever the free set changes, the approximate variant computes this inner preconditioner only once on the initial free set. The authors supply an error analysis for the approximation, a sharp bound on the condition number of the resulting preconditioned operator, and numerical experiments that report very large speedups relative to the exact variant.

Significance. If the error analysis and condition-number bound remain valid under the dynamic free-set updates that occur in MPGP iterations, the work would supply a practical acceleration technique that reduces the cost of repeated inner-preconditioner construction while preserving acceptable convergence behavior. The reported numerical speedups suggest meaningful efficiency gains for large-scale problems, but the practical value depends on whether the theoretical guarantees extend beyond the fixed-free-set setting used in the derivations.

major comments (1)
  1. [Error analysis section] The sharp bound on the condition number of the preconditioned operator is derived under the assumption of a fixed free set (see the error analysis section and the associated theorem). MPGP-type methods, however, update the free set at every iteration when a variable hits a bound. No explicit propagation of the approximation error across successive free-set changes is provided, leaving open whether the outer iteration count stays comparable to the exact (recomputed) variant when active-set changes are frequent or large.
minor comments (1)
  1. [Introduction and numerical experiments] The notation distinguishing the exact and approximate preconditioned operators could be introduced earlier and used consistently in the numerical section to improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and valuable feedback on our manuscript. The central concern is whether the error analysis and condition-number bound, derived for a fixed free set, extend to the dynamic free-set updates inherent in MPGP iterations. We address this point directly below.

read point-by-point responses

  1. Referee: [Error analysis section] The sharp bound on the condition number of the preconditioned operator is derived under the assumption of a fixed free set (see the error analysis section and the associated theorem). MPGP-type methods, however, update the free set at every iteration when a variable hits a bound. No explicit propagation of the approximation error across successive free-set changes is provided, leaving open whether the outer iteration count stays comparable to the exact (recomputed) variant when active-set changes are frequent or large.

    Authors: We agree that the sharp condition-number bound and associated error analysis are derived under the assumption of a fixed free set, as the approximate inner preconditioner is computed once on the initial free set and held fixed thereafter. The manuscript does not supply a rigorous propagation analysis of the approximation error through successive free-set changes. Nevertheless, the numerical experiments section reports results on quadratic programs that exhibit frequent active-set changes during the MPGP iterations. In these tests the approximate variant produces outer iteration counts comparable to the exact (recomputed) variant while delivering substantial speedups. We will revise the manuscript to state the fixed-free-set assumption explicitly in the theorem and to add a short discussion of the empirical behavior under dynamic updates. revision: partial

Circularity Check

0 steps flagged

No significant circularity; theoretical bounds derived independently of fitted data or self-referential definitions

full rationale

The paper derives an error analysis and sharp bound on the condition number of the preconditioned operator for the approximate (once-computed) inner preconditioner via direct mathematical arguments on the fixed free-set operator. These steps rely on standard linear-algebraic estimates rather than re-using fitted parameters, renaming empirical patterns, or load-bearing self-citations whose validity depends on the present work. Numerical experiments are presented separately as validation and do not enter the derivation of the bound or error estimate. The central claims therefore remain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard mathematical framework of MPGP active-set methods and free-set preconditioning for quadratic programs; the principal addition is the one-time approximation strategy rather than new entities or many fitted constants.

axioms (1)
  • domain assumption The quadratic program is convex or the reduced Hessian on the free set is positive definite, ensuring well-posedness of the inner systems.
    Required for convergence of MPGP iterations and for the preconditioner to be valid.

pith-pipeline@v0.9.0 · 5649 in / 1262 out tokens · 69394 ms · 2026-05-22T00:14:12.512084+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

32 extracted references · 32 canonical work pages

  1. [1]

    Dost´ al,Optimal Quadratic Programming Algorithms, with Applications to Variational Inequalities

    Z. Dost´ al,Optimal Quadratic Programming Algorithms, with Applications to Variational Inequalities. SOIA, Springer, New York, US, 2009, vol. 23, isbn: 0387848053

    work page 2009

  2. [2]

    Stebel, J

    J. Stebel, J. Kruˇ z´ ık, D. Hor´ ak, J. Bˇ rezina and M. B´ ereˇ s, ‘On the parallel solution of hydro-mechanical problems with fracture networks and contact conditions,’ Computers & Structures, vol. 298, p. 107 339, 2024, issn: 0045-7949. doi: 10.1016/j.compstruc.2024. 107339

    work page doi:10.1016/j.compstruc.2024 2024

  3. [3]

    Claret, N

    F. Claret, N. I. Prasianakis, A. Baksay, D. Lukin, G. Pepin, E. Ahusborde, B. Amaziane, G. B´ ator, D. Becker, A. Bedn´ ar, M. B´ ereˇ s, S. B´ ereˇ sov´ a, Z. B¨ othi, V. Brendler, K. Brenner, J. Bˇ rezina, F. Chave, S. V. Churakov, M. Hokr, D. Hor´ ak, D. Jacques, F. Jankovsk´ y, C. Kazymyrenko, T. Koudelka, T. Kov´ acs, T. Krejˇ c´ ı, J. Kruis, E. Lalo...

    work page doi:10.3389/fnuen.2024.1437714 2024

  4. [4]

    M. Pecha, ‘Solvers and their implementations for machine learning problems and applic- ations,’ Available at http://hdl.handle.net/10084/155603, PhD thesis, VSB - Technical University of Ostrava, 2024

    work page 2024

  5. [5]

    Kruˇ z´ ık, M

    J. Kruˇ z´ ık, M. Pecha, V. Hapla, D. Hor´ ak and M.ˇCerm´ ak, ‘Investigating convergence of linear SVM implemented in PermonSVM employing MPRGP algorithm,’ in High Performance Computing in Science and Engineering , T. Kozubek, M. ˇCerm´ ak, P. Tich´ y, R. Blaheta, J. ˇS´ ıstek, D. Luk´ aˇ s and J. Jaroˇ s, Eds., Cham: Springer International Publishing, 2...

    work page doi:10.1007/978-3-319-97136-0 2018

  6. [6]

    A. K. Turner, K. J. Peterson and D. Bolintineanu, ‘Geometric remapping of particle distributions in the discrete element model for sea ice (DEMSI v0.0),’ Geoscientific Model Development, vol. 15, no. 5, pp. 1953–1970, 2022, issn: 1991-9603. doi: 10.5194/gmd-15- 1953-2022

    work page doi:10.5194/gmd-15- 1953

  7. [7]

    Liesen and Z

    J. Liesen and Z. Strakos, Krylov subspace methods (Numerical Mathematics and Scientific Computation). London, England: Oxford University Press, 2012, isbn: 9780199655410

    work page 2012

  8. [8]

    Dost´ al and J

    Z. Dost´ al and J. Sch¨ oberl, ‘Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination,’ Computational Optimization and Applications, vol. 30, no. 1, pp. 23–43, 2005. doi: 10.1007/s10589-005-4557-7

    work page doi:10.1007/s10589-005-4557-7 2005

  9. [9]

    Bouchala, Z

    J. Bouchala, Z. Dost´ al, T. Kozubek, L. Posp´ ıˇ sil and P. Vodstrˇ cil, ‘On the solution of convex QPQC problems with elliptic and other separable constraints with strong curvature,’Applied Mathematics and Computation, vol. 247, pp. 848–864, 2014. doi: 10.1016/j.amc.2014.09.044

    work page doi:10.1016/j.amc.2014.09.044 2014

  10. [10]

    Posp´ ıˇ sil, ‘Development of algorithms for solving minimizing problems with convex quadratic function on special convex sets and applications,’ Available at http://hdl.handle

    L. Posp´ ıˇ sil, ‘Development of algorithms for solving minimizing problems with convex quadratic function on special convex sets and applications,’ Available at http://hdl.handle. net/10084/110918, PhD thesis, VSB - Technical University of Ostrava, 2015

    work page 2015

  11. [11]

    Polyak, ‘The conjugate gradient method in extremal problems,’ USSR Computational Mathematics and Mathematical Physics , vol

    B. Polyak, ‘The conjugate gradient method in extremal problems,’ USSR Computational Mathematics and Mathematical Physics , vol. 9, no. 4, pp. 94–112, 1969. doi: 10.1016/0041- 5553(69)90035-4

    work page doi:10.1016/0041- 1969

  12. [12]

    Bouchala, Z

    J. Bouchala, Z. Dost´ al and P. Vodstrˇ cil, ‘Separable spherical constraints and the decrease of a quadratic function in the gradient projection step,’ Journal of Optimization Theory and Applications, vol. 157, no. 1, pp. 132–140, 2012, issn: 1573-2878. doi: 10.1007/s10957- 012-0178-3

    work page doi:10.1007/s10957- 2012

  13. [13]

    Kruˇ z´ ık, D

    J. Kruˇ z´ ık, D. Hor´ ak, M.ˇCerm´ ak, L. Posp´ ıˇ sil and M. Pecha, ‘Active set expansion strategies in MPRGP algorithm,’ Advances in Engineering Software, vol. 149, 2020, issn: 0965-9978. doi: 10.1016/j.advengsoft.2020.102895

    work page doi:10.1016/j.advengsoft.2020.102895 2020

  14. [14]

    Kruˇ z´ ık, ‘Improving quadratic programming algorithms,’ Available at http://hdl.handle

    J. Kruˇ z´ ık, ‘Improving quadratic programming algorithms,’ Available at http://hdl.handle. net/10084/155609, PhD thesis, VSB - Technical University of Ostrava, 2024

    work page 2024

  15. [15]

    G. H. Golub and C. F. van Loan, Matrix Computations , 4th. JHU Press, 2013, isbn: 1421407949

    work page 2013

  16. [16]

    D. P. O’Leary, ‘A generalized conjugate gradient algorithm for solving a class of quadratic programming problems,’Linear Algebra and its Applications , vol. 34, pp. 371–399, 1980. doi: 10.1016/0024-3795(80)90173-1

    work page doi:10.1016/0024-3795(80)90173-1 1980

  17. [17]

    Domor´ adov´ a and Z

    M. Domor´ adov´ a and Z. Dost´ al, ‘Projector preconditioning for partially bound-constrained quadratic optimization,’ Numerical Linear Algebra with Applications , vol. 14, no. 10, pp. 791–806, 2007. doi: 10.1002/nla.555

    work page doi:10.1002/nla.555 2007

  18. [18]

    Jaroˇ sov´ a, A

    M. Jaroˇ sov´ a, A. Klawonn and O. Rheinbach, ‘Projector preconditioning and transformation of basis in FETI-DP algorithms for contact problems,’ Mathematics and Computers in Simulation, vol. 82, no. 10, pp. 1894–1907, 2012. doi: 10.1016/j.matcom.2010.10.031. 15

    work page doi:10.1016/j.matcom.2010.10.031 1907

  19. [19]

    Narain, A

    R. Narain, A. Golas and M. C. Lin, ‘Free-flowing granular materials with two-way solid coup- ling,’ in ACM SIGGRAPH Asia 2010 papers on - SIGGRAPH ASIA ’10 , ser. SIGGRAPH ASIA ’10, ACM Press, 2010, p. 1. doi: 10.1145/1882262.1866195

    work page doi:10.1145/1882262.1866195 2010

  20. [20]

    Gerszewski and A

    D. Gerszewski and A. W. Bargteil, ‘Physics-based animation of large-scale splashing liquids,’ACM Transactions on Graphics, vol. 32, no. 6, pp. 1–6, 2013, issn: 1557-7368. doi: 10.1145/2508363.2508430

    work page doi:10.1145/2508363.2508430 2013

  21. [21]

    Takahashi and C

    T. Takahashi and C. Batty, ‘A multilevel active-set preconditioner for box-constrained pressure poisson solvers,’ Proceedings of the ACM on Computer Graphics and Interactive Techniques, vol. 6, no. 3, pp. 1–22, 2023, issn: 2577-6193. doi: 10.1145/3606939

    work page doi:10.1145/3606939 2023

  22. [22]

    [Online]

    PERMON web page , https://permon.vsb.cz, 2016. [Online]. Available: https://permon.vsb. cz (visited on 01/07/2025)

    work page 2016

  23. [23]

    [Online]

    PERMON project repository , https://github.com/permon. [Online]. Available: https: //github.com/permon (visited on 01/07/2025)

    work page 2025

  24. [24]

    Balay, S

    S. Balay, S. Abhyankar, M. F. Adams, S. Benson, J. Brown, P. Brune, K. Buschelman, E. M. Constantinescu, L. Dalcin, A. Dener, V. Eijkhout, J. Faibussowitsch, W. D. Gropp, V. Hapla, T. Isaac, P. Jolivet, D. Karpeev, D. Kaushik, M. G. Knepley, F. Kong, S. Kruger, D. A. May, L. C. McInnes, R. T. Mills, L. Mitchell, T. Munson, J. E. Roman, K. Rupp, P. Sanan, ...

    work page 2025

  25. [25]

    Balay, S

    S. Balay, S. Abhyankar, M. F. Adams, S. Benson, J. Brown, P. Brune, K. Buschelman, E. Constantinescu, L. Dalcin, A. Dener, V. Eijkhout, J. Faibussowitsch, W. D. Gropp, V. Hapla, T. Isaac, P. Jolivet, D. Karpeev, D. Kaushik, M. G. Knepley, F. Kong, S. Kruger, D. A. May, L. C. McInnes, R. T. Mills, L. Mitchell, T. Munson, J. E. Roman, K. Rupp, P. Sanan, J. ...

    work page doi:10.2172/2476320 2025

  26. [26]

    Balay, W

    S. Balay, W. D. Gropp, L. C. McInnes and B. F. Smith, ‘Efficient management of parallelism in object oriented numerical software libraries,’ in Modern Software Tools in Scientific Computing, E. Arge, A. M. Bruaset and H. P. Langtangen, Eds., Birkh¨ auser Press, 1997, pp. 163–202

    work page 1997

  27. [27]

    P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent and J. Koster, ‘A fully asynchronous multifrontal solver using distributed dynamic scheduling,’SIAM Journal on Matrix Analysis and Applic- ations, vol. 23, no. 1, pp. 15–41, 2001, issn: 1095-7162. doi: 10.1137/s0895479899358194

    work page doi:10.1137/s0895479899358194 2001

  28. [28]

    P. R. Amestoy, A. Buttari, J. -Y. L’Excellent and T. Mary, ‘Performance and scalability of the block low-rank multifrontal factorization on multicore architectures,’ACM Transactions on Mathematical Software, vol. 45, no. 1, pp. 1–26, 2019, issn: 1557-7295. doi: 10.1145/ 3242094

    work page 2019

  29. [29]

    T. F. Chan and H. A. Van der Vorst, ‘Approximate and incomplete factorizations,’ inParallel Numerical Algorithms, D. E. Keyes, A. Sameh and V. Venkatakrishnan, Eds. Dordrecht: Springer Netherlands, 1997, pp. 167–202, isbn: 978-94-011-5412-3. doi: 10.1007/978-94- 011-5412-3 6

    work page doi:10.1007/978-94- 1997

  30. [30]

    D. M. Young, Iterative Solution of Large Linear Systems . Academic Press, 1971, isbn: 9780127730509

    work page 1971

  31. [31]

    [Online]

    LUMI web page , https://lumi- supercomputer.eu. [Online]. Available: https://lumi- supercomputer.eu (visited on 01/07/2025). 16

    work page 2025

  32. [32]

    Averick, R

    B. Averick, R. Carter, G.-L. Xue and J. More, ‘The MINPACK-2 test problem collection,’ Office of Scientific and Technical Information (OSTI), Tech. Rep., 1992.doi: 10.2172/79972. 17

    work page doi:10.2172/79972 1992