Pay-as-You-Go Preconditioner Refresh: A Wall-Clock Rule for When to Rebuild

Many iterative solvers speed up by using a preconditioner, an approximate inverse of the problem's matrix that reshapes a badly scaled problem into one that converges in far fewer steps. When the problem changes during the run, the preconditioner goes stale. This happens when a circuit's transistors switch operating regions, when the set of active constraints shifts in a non-smooth optimization, or when a nonlinear PDE's Jacobian moves with the state. Rebuilding the preconditioner costs time. Not rebuilding it costs extra iterations. Every adaptive-preconditioning paper we found settles this trade-off with a hand-set threshold or a fixed interval, and the authors themselves name the choice of refresh frequency as open. The theory that does exist states its guarantees in iteration counts or asymptotic rates. That is exactly the kind of guarantee that fails to predict running time on real hardware.

We propose to treat "when do I rebuild?" as an online rent-or-buy decision measured in seconds. While the current preconditioner is used, the solver tracks how much extra time each step costs compared with the step right after the last rebuild. It rebuilds once that accumulated waste equals the measured cost of the last rebuild. The rule needs no condition number, Lipschitz constant, or tuned interval. It reads only timers the solver already has. We expect that under one stated assumption it is within a factor of two of the best refresh schedule chosen in hindsight. The claim to test is that this single rule, with no tuning, matches or beats per-instance-tuned refresh intervals on three structurally different solvers. Its guarantee is stated in the quantity practitioners actually care about.

Core Claim

The existing work splits into two camps, and neither answers the scheduling question. Systems papers adapt preconditioners well empirically but schedule refreshes by heuristic. Zhao and Feng's support-circuit preconditioners rebuild a sparsified circuit approximation when an empirical threshold says the GMRES iteration penalty outweighs refactorization, and the threshold has no formal backing. Ye et al.'s Inactively Nested Forests rebuild tree preconditioners from the current active set at fixed intervals and list the right frequency as an open problem. Theory papers, on the other hand, give guarantees that either avoid discrete refreshes or depend on unknowable constants. Chen, Guo and Wei's transformed primal-dual method lets the preconditioner drift continuously along a flow and proves global linear convergence, but only for smooth saddle-point problems and only in iteration counts. Zhang et al.'s EMGD sets epoch lengths from the exact condition number, which is never available in practice. This "prior-knowledge dilemma" is the core of the empirical-validation gap.

Our rule sits between the two camps. Let $C_t$ be the measured wall-clock cost of solver step $t$. Let $c_0$ be the cost of the first step after the most recent rebuild, used as a stand-in for what a fresh preconditioner would cost now. Let $R$ be the measured cost of that rebuild. The solver rebuilds at the first step $T$ where

$$\sum_{t=t_0}^{T} \max(C_t - c_0,\, 0) \;\ge\; \beta R,$$

with $t_0$ the index of the last rebuild and $\beta = 1$ by default. The factor-of-two expectation comes from the classical ski-rental argument. If the extra per-step cost of a stale preconditioner never decreases between rebuilds, then any schedule pays at least about $R$ per refresh window, either in rebuild time or in accumulated waste. The balance rule pays at most $2R$ per window. Proving this carefully, including the error from estimating fresh cost by $c_0$, is part of the work. The monotonicity assumption is the hinge, and we will measure directly how often it is violated.

Research Program

The first strand is analysis. We will formalize the refresh problem as an online cost-minimization problem over a sequence of steps. We will prove the competitive bound under monotone degradation and quantify how much it loosens when $c_0$ is a noisy estimate of fresh cost. We will also characterize what happens when degradation is not monotone, for example when an active set flips back. A randomized variant that draws the threshold from the standard ski-rental distribution is the natural candidate for a tighter expected bound, and we will test whether it helps in practice or only on paper.

The second strand is a solver-agnostic implementation. It is a thin wrapper that accepts a "rebuild" callback and per-step timings, so the same code drives three solvers. The wrapper adds negligible bookkeeping cost by design.

The third strand addresses the empirical-validation gap directly. One of our three testbeds is a method that has never been run. Maréchal and Rondepierre's proximal pseudo-inversion repeatedly solves systems with $(I + \mu_k M^\top M)$ and proves linear convergence to the pseudo-inverse. It reports no experiments, and it notes that comparison with standard factorizations is future work. If $\mu_k$ varies, every iteration in principle needs a new factorization. Reusing a stale factorization as a preconditioner for an inner conjugate-gradient solve is exactly a refresh decision. So the testbed both evaluates our rule and gives the first wall-clock evaluation of that paper against truncated SVD and one-shot Tikhonov regularization. Tikhonov regularization is a single regularized least-squares solve, and the paper shows it equals the method's first iterate.

Baselines

The naive reference points are "never rebuild" and "rebuild every step." The first is a static preconditioner built once at the start. The corpus repeatedly shows it degrading in all four application areas. The second pays the full rebuild cost every step. Both will run on identical problem instances, hardware, and stopping tolerances. Our rule must beat both on wall-clock time to tolerance on every instance to be worth anything.

The strongest competitor is the best fixed refresh interval, tuned per instance by grid search. This is the schedule Ye et al. use for INF, now given the advantage of hindsight tuning. On Graph TV the reported reference is that INF reached the solution on rmf-wide in 190 iterations, about 18.5 seconds, while FISTA failed to converge within 500,000 iterations (Ye et al.). We will first reproduce INF with its published schedule on rmf-wide, horse and manga to anchor against that number. We will then grid-search the interval per instance under a fixed tuning budget, recording total compute spent on tuning. Beating this baseline means matching its wall-clock time within 10% with zero tuning, and beating it when the interval is tuned on one instance and transferred to the others.

On the Darcy-Forchheimer model, implemented in the iFEM MATLAB package, the reported reference is that TPDv-IMEX ran about twice as fast as standard TPDv and outperformed fixed-point iteration (Chen, Guo and Wei). No exact iteration counts or seconds for Darcy-Forchheimer were found on Lacuna. For the eddy-current problem they report a solve in 122 seconds at over three million degrees of freedom. Here the competitor is their continuous preconditioner flow, run with the authors' settings. Our variant replaces the continuous update with discrete rebuilds of the Schur-complement approximation triggered by the rule.

For proximal inversion, no reported result was found on Lacuna, since the original paper has no experiments. The baselines are truncated SVD and one-shot Tikhonov at a regularization level chosen by cross-validation on the same test matrices.

Two ablations isolate the key ingredient, which is that the trigger is denominated in measured rebuild cost. The first is an iteration-count trigger that rebuilds when inner iterations exceed a multiple of the post-rebuild count. This is roughly the shape of Zhao and Feng's heuristic, which ignores how expensive the rebuild is. The second is our rule with $R$ replaced by a constant. If either matches the full rule, the cost-awareness is not doing the work.

Why not just…?

Why not just tune a fixed refresh interval once and reuse it? This is the real threat. If one interval tuned on horse works equally well on manga and rmf-wide, our rule offers convenience rather than performance. The transfer experiment settles it. Rebuild cost depends on graph size and sparsity, and degradation speed depends on how fast the active set moves. Both differ across instances, so we expect transferred intervals to lose on at least one instance. If they do not, we will report that honestly and restrict the claim to the absence of tuning.

Why not just trigger on inner iteration counts, as circuit simulators do? An iteration threshold is blind to the price of a rebuild. Zhao and Feng report support-circuit factorization up to 34.1 times cheaper than the original (their paper), and when rebuilds are that cheap the best threshold should be much lower than when they are expensive. A fixed iteration multiple cannot adjust to this. The first ablation tests whether that matters in practice by varying rebuild cost artificially, through finer or coarser forest extraction in INF and denser or sparser factorizations in the inversion testbed.

Why not just let the preconditioner drift continuously, as in transformed primal-dual methods? The continuous flow of Chen, Guo and Wei is analyzed only for smooth problems. Its rate parameter is itself a tuning knob. It also does not apply to combinatorial preconditioners like spanning forests, which cannot be interpolated. On Darcy-Forchheimer, where it does apply, it may well win, and we will report it as the target to match rather than assume we beat it.

Proposed Experiments

The three testbeds are Graph TV with INF on rmf-wide, horse and manga; Darcy-Forchheimer with variable preconditioners in iFEM, swept across nonlinearity strength and mesh refinement; and proximal pseudo-inversion on synthetic matrices with controlled singular-value decay plus discretized ill-posed operators. The primary metric is wall-clock time to a fixed primal-dual gap or residual. Secondary metrics are rebuild count, the fraction of time spent rebuilding, and the ratio to the best schedule in hindsight.

For the inversion and Darcy testbeds, inner solves run to a fixed tolerance, so the outer iterates barely depend on the refresh schedule. This lets us log per-step costs as a function of preconditioner age and compute the exact optimal schedule by dynamic programming. We can therefore measure the empirical competitive ratio directly and compare it with the proved factor of two. For INF, rebuilding changes the trajectory itself, so the hindsight oracle is the best fixed interval.

The first decisive check is whether the measured ratio to optimal stays at or below two wherever degradation is monotone. We will log monotonicity violations to see whether the bound fails exactly where the assumption fails. The second is the transfer experiment against tuned intervals. The third is the first published runtime comparison of proximal inversion against truncated SVD and Tikhonov. That comparison is worth reporting whichever way it comes out, because the open question in that paper is whether the method is ever faster than a direct factorization.