The Wall Clock Tradeoffs of Preconditioning

67 concepts61 papers1 proposal

When solving large linear systems or optimizing complex machine learning models, the conditioning of the problem dictates how fast an iterative solver can converge. Ill-conditioned systems cause standard gradient methods or Krylov subspace solvers to stall, bouncing back and forth across narrow valleys in the loss landscape.

The classic remedy is preconditioning: transforming the system $Ax = b$ into $M^{-1}Ax = M^{-1}b$, where the operator $M^{-1}$ approximates $A^{-1}$ but is much cheaper to compute. If $M^{-1}A$ is close to the identity matrix, its eigenvalues cluster together, and the solver converges in just a handful of steps.

However, this theoretical elegance hides a practical trap. In real-world computing, we do not care about the number of iterations; we care about wall-clock time. Preconditioning introduces a fundamental trade-off governed by a simple equation:

$$\text{Total Wall-Clock Time} = \text{Setup Time} + (\text{Iteration Count} \times \text{Per-Iteration Cost})$$

As Yichen Li et al. emphasize in Learning Preconditioners for Conjugate Gradient PDE Solvers, every sophisticated preconditioner faces this balance. If a preconditioner takes too long to build (high setup time) or too long to apply (high per-iteration cost), it can easily become slower than using no preconditioner at all.

The Setup Bottleneck

The first major component of preconditioning overhead occurs before the solver even begins its first iteration. Constructing a high-quality approximation of a matrix inverse or a Hessian operator often requires significant computational effort.

In high-order finite element simulations, this initialization phase can completely overwhelm the actual computation. For instance, Alexey Voronin demonstrates in Monolithic Multigrid Preconditioners for High-Order Discretizations of Stokes Equations that the setup phase for complex multigrid preconditioners can consume up to 98% of the total simulation time. When setup dominates to this extent, optimizing the speed of individual solver iterations yields virtually no practical benefit; efficiency gains must come from streamlining the construction of the operator itself.

A similar bottleneck arises in optimization frameworks that use curvature information. Subsampled Hessian preconditioners are widely used to capture the local geometry of a loss function, but Chih-Yang Hsia et al. show in Preconditioned Conjugate Gradient Methods in Truncated Newton Frameworks for Large-scale Linear Classification that the time required to build these subsampled matrices frequently introduces a massive wall-clock penalty. The reduction in iteration count is rendered useless because the algorithm spends too long in the construction phase.

Even modern randomized techniques designed to alleviate this burden carry heavy constant factors. Sachin Garg et al. note in Distributed Least Squares in Small Space via Sketching and Bias Reduction that constructing preconditioners via random matrix sketching introduces substantial upfront overhead that can offset theoretical asymptotic runtime advantages. For dense matrices, this overhead is so severe that Michal Derezinski et al. demonstrate in Solving Dense Linear Systems Faster than via Preconditioning that alternative stochastic coordinate descent methods can bypass preconditioning entirely to achieve faster overall runtimes.

The Per-Iteration Burden

Even if a preconditioner can be constructed efficiently, it must be applied at every single step of the iterative process. If evaluating $M^{-1}v$ requires dense matrix-vector products or solving an auxiliary linear system, the cost per iteration increases.

This trade-off is clearly illustrated in polynomial preconditioning, where $M^{-1}$ is expressed as a polynomial expansion of $A$. Nikita Doikov explains in Polynomial Preconditioning for Gradient Methods that increasing the degree of the polynomial improves the condition number and drops the iteration count. However, higher-degree polynomials require more matrix-vector products per step. Eventually, the computational cost of these extra products overpowers the convergence gains, creating an optimal threshold beyond which more preconditioning hurts performance.

Similarly, in graph and network problems, Yanchun Wang et al. observe in A Preconditioned and Shifted GMRES Algorithm for the PageRank Problem with Multiple Damping Factors that the additional matrix operations required to apply a preconditioner can easily negate the savings from a lower iteration count. The solver becomes trapped in a state where individual steps are too heavy to justify the faster mathematical convergence.

Scale, Architecture, and Amortization

Because preconditioning costs act as an upfront investment, whether they are "worth it" depends heavily on the scale of the problem and the underlying hardware architecture.

The Amortization Threshold

On smaller datasets or simpler models, the upfront cost of preconditioning cannot be amortized. Di Wang et al. demonstrate this dynamic in Large Scale Constrained Linear Regression Revisited: Faster Algorithms via Preconditioning, showing that while advanced preconditioning pays massive dividends in large-scale settings, it falls behind simpler, non-preconditioned optimization methods on smaller problems where the setup time dominates.

Parallelization and Communication Limits

Modern high-performance computing architectures introduce another layer of complexity: communication overhead. Many sophisticated preconditioning setup routines are inherently sequential or require tight synchronization across processors. Li Zhao et al. point out in Parallel multi-stage preconditioners with adaptive setup for the black oil model that these setup phases frequently fail to scale with high processor counts, creating a strict performance ceiling.

Furthermore, mathematically superior preconditioners (such as Gauss-Seidel) require sequential dependencies that trigger high communication latency in parallel environments. As a result, Carlo Janna et al. explain in Parallel Energy-Minimization Prolongation for Algebraic Multigrid that simpler methods like Jacobi preconditioning often achieve faster wall-clock times. Even though Jacobi requires more iterations to converge, its embarrassingly parallel nature eliminates communication bottlenecks, allowing it to win the wall-clock race on modern hardware.

Preconditioning in Deep Learning

This exact wall-clock dilemma is a central battleground in modern deep learning optimization. Standard optimizers like Adam utilize diagonal preconditioning, which is computationally cheap but ignores the correlations between different weights. Non-diagonal preconditioners (such as Shampoo) capture full curvature information, drastically reducing the number of training steps required to reach a target accuracy.

In an analysis of the AlgoPerf competition, Priya Kasimbeg et al. highlight in Accelerating neural network training: An analysis of the AlgoPerf competition that while non-diagonal preconditioning offers massive theoretical benefits, it has historically been dismissed due to its high per-step computational costs. The core challenge of modern optimizer design is determining whether these sophisticated methods can provide a net reduction in wall-clock training time.

Even when moving away from full matrix operations, Hemanth Saratchandran et al. note in Weight Conditioning for Smooth Optimization of Neural Networks that simpler conditioning techniques still add a tangible temporal cost to the training loop. The success of any optimization advancement hinges entirely on developing highly efficient implementation strategies that protect the hardware's execution speed while capturing the mathematical benefits of a better-conditioned space.

Key Foundational Work

Toeplitz preconditioners for Hermitian Toeplitz systems (1993) — contributed 1 concept elements to this direction.
An Optimization Network for Matrix Inversion (1987) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_preconditioner_computational_overhead_2eb74c27,
  title = {preconditioner computational overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/preconditioner-computational-overhead/rdr_2eb74c27fdb84e04af7e08ba3d9d8e4a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_preconditioner_computational_overhead_2eb74c27_v1,
  title = {preconditioner computational overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/preconditioner-computational-overhead/rdr_2eb74c27fdb84e04af7e08ba3d9d8e4a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake