Skip to content

Preconditioning

Preconditioning is mandatory for efficient solution of the coupled system arising from constrained mechanics. Without it, Krylov solvers converge slowly or stagnate, especially as constraints become stiff or numerous.

For the mathematical background on constraints as physical interactions, see Constraints & Physical Interactions.

Why preconditioning is mandatory

Without preconditioning:

  • Krylov solvers (CG/GMRES) converge slowly or stagnate
  • the spectrum is dominated by constraint-related modes
  • conditioning deteriorates rapidly as constraints become stiff or numerous

Because the solver is fully matrix-free, preconditioning must itself be formulated as an operator application, not as a sparse factorization. This excludes most classical FEM preconditioners relying on assembled matrices.

Block preconditioners

A first family of strategies preserves the coupled primal–dual structure while approximating the inverse of the block system. These preconditioners exploit the geometric decomposition of the configuration space into free motions and constraint reactions.

Block-diagonal preconditioner

\[ P^{-1} = \begin{bmatrix} \tilde A^{-1} & 0 \\ 0 & \tilde S^{-1} \end{bmatrix}, \]

where:

  • \(\tilde A^{-1}\) approximates the inverse of the primal operator \(A\) (dynamics in free motion space)
  • \(\tilde S^{-1}\) approximates the inverse of the Schur complement \(S = G A^{-1} G^\top\) (dynamic compliance seen by constraints)

This choice is simple and robust but neglects coupling between primal and dual variables (free motions and constraint reactions).

Block-triangular (Uzawa-type) preconditioner

\[ P^{-1} = \begin{bmatrix} \tilde A^{-1} & -\tilde A^{-1} G^\top \tilde S^{-1} \\ 0 & \tilde S^{-1} \end{bmatrix}. \]

This form captures coupling effects between free motions and constraint reactions, and typically improves convergence, especially for GMRES on strongly constrained problems. It accounts for how constraint forces affect the dynamics and vice versa.

Schur complement methods

Physical interpretation

The Schur complement \(S = G A^{-1} G^\top\) represents the dynamic compliance seen by the constraint: given a constraint force \(\lambda\), it determines how the constraint "feels" the system's response.

Key insight: This is not merely a numerical construct but a physical quantity:

  • \(A^{-1}\) is the dynamics compliance: how the system responds to applied forces
  • \(G\) maps constraint forces to the dynamics space
  • \(G^\top\) maps constraint violations back to the constraint space
  • \(S = G A^{-1} G^\top\) is the effective compliance that the constraint experiences

This physical interpretation guides both physics-based approximations and learned models. For example, a learned preconditioner (see Integration Points) should respect this physical meaning rather than treating \(S\) as an arbitrary matrix.

Connection to geometric decomposition

The Schur complement is intimately connected to the geometric decomposition discussed in Constraints & Physical Interactions:

\[ \mathcal{Q} = \ker G \oplus \operatorname{range}(G^\top) \]

The Schur complement operates entirely in the constraint space \(\operatorname{range}(G^\top)\), while \(A^{-1}\) operates in the free motion space \(\ker G\). This separation enables decoupling strategies that respect the underlying physics.

Schur complement system

Formally eliminating the primal increment \(\delta x\) from the coupled system (see Newton–Krylov Solver) yields a Schur complement system on the multipliers:

\[ S \, \delta \lambda = G A^{-1} G^\top \delta \lambda = r_c - G A^{-1} r_u. \]

This enables decoupling of dynamics and constraints:

  1. Solve the constraint problem in the constraint space (smaller dimension): \(S \delta\lambda = r_c - G A^{-1} r_u\). This step typically employs Gauss-Seidel or Projected Gauss-Seidel (PGS). While the Schur complement matrix \(S\) is dense (coupling all constraints), iterative solvers like PGS are effective as they update multipliers sequentially without requiring the full inversion of \(S\).
  2. Recover the primal update from the constraint solution: \(\delta x = A^{-1} (r_u - G^\top \delta\lambda)\)

Advantages

  • Reduces problem size: When \(n_c \ll n_x\), solving in constraint space is much cheaper than solving the full coupled system
  • Enables separate solvers: Dynamics and constraints can be solved with different strategies optimized for each
  • Respects physics: The decoupling reflects the geometric decomposition of the configuration space

Challenges

  • Requires efficient approximation of \(A^{-1}\): The dynamics inverse must be approximated (e.g., via iterative solves or learned models) without assembling matrices
  • Requires approximation of \(S^{-1}\): The Schur complement inverse is needed for preconditioning or direct solution
  • Remains fully matrix-free: All operations must be via operator actions
  • Sensitive to quality of inner solves: Poor approximations of \(A^{-1}\) lead to poor Schur complement approximations

Implementation in SOFAx v2

In SOFAx v2, Schur-based strategies are envisioned as iterative inner solves rather than explicit elimination or condensation:

  • \(A^{-1}\) is approximated via Krylov iterations (CG/GMRES) on the dynamics system
  • \(S\) is never explicitly formed; only its action \(S \delta\lambda\) is computed
  • Learned models can approximate either \(A^{-1}\) or \(S^{-1}\) directly (see Integration Points)

The key insight is that \(S\) is a physical quantity (compliance), not just a numerical construct, which guides both physics-based and learning-based approximations.

Connection to AI integration

The physical interpretation of the Schur complement and the block structure of preconditioners provide natural integration points for learned components:

  • Learned approximations of \(A^{-1}\): Neural networks can learn to approximate the dynamics inverse, enabling Schur complement computation without expensive inner solves
  • Learned Schur complement actions: Models can directly approximate \(S\) or \(S^{-1}\), respecting the physical meaning as dynamic compliance
  • Learned block preconditioners: The block structure (diagonal or triangular) can be enriched with learned corrections while preserving the geometric decomposition

For detailed discussion, see Integration Points, particularly the sections on learned preconditioners and Schur complement assistance.

See also