Coordinate Condensation: Subspace-Accelerated Coordinate Descent for Physics-Based Simulation

Basic Information

• Paper ID: 2510.12053
• Title: Coordinate Condensation: Subspace-Accelerated Coordinate Descent for Physics-Based Simulation
• Author: Ty Trusty (University of Toronto)
• Category: cs.GR (Computer Graphics)
• Publication Date: October 14, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12053

Abstract

This paper proposes the Coordinate Condensation method, a variant of coordinate descent that accelerates physics-based simulation by augmenting local coordinate updates with subspace corrections based on the Schur complement. The method reuses the perturbed subspace from JGS2 but solves local and subspace displacements independently, eliminating the damping effects introduced in JGS2. When the subspace adequately captures global coupling, the method achieves convergence rates approaching Newton's method while maintaining the efficiency and parallelizability of coordinate descent.

Research Background and Motivation

Core Problem

In physics-based animation simulation, implicit time integration is typically formulated as an optimization problem. While Newton's method exhibits fast convergence, it requires computing and inverting the full Hessian matrix at each iteration, which is computationally prohibitive for large-scale or real-time applications.

Limitations of Existing Methods

1. Standard Coordinate Descent: Highly parallelizable with efficient per-iteration cost, but convergence severely degrades under strong coupling (e.g., stiff materials, fine meshes, or constraints)
2. JGS2 Method: Accounts for global coupling through a precomputed perturbed subspace, but enforces a rigid proportionality relationship between local and subspace displacements, introducing damping effects that may reduce convergence performance

Research Motivation

There is a need for a solver that maintains the parallel efficiency of coordinate descent while effectively handling global coupling, achieving rapid convergence under stiff materials and fine mesh conditions.

Core Contributions

1. Proposes the Coordinate Condensation Method: A coordinate descent solver with subspace correction based on the Schur complement
2. Eliminates Damping Effects: Solves local and subspace displacements independently, avoiding rigid proportionality constraints in JGS2
3. Comprehensive Convergence Assessment: Performance analysis across varying mesh resolutions, material stiffness, and subspace quality
4. Analysis of Method Limitations: In-depth discussion of success and failure conditions for subspace-based coordinate methods

Detailed Methodology

Problem Formulation

Solving the nonlinear optimization problem for physics-based simulation: $x_{t+1} = \arg\min_x E(x)$

where the energy function is: $E(x) = \frac{1}{2}(x-\tilde{x})^T M(x-\tilde{x}) + h^2\Psi(x)$

Core Technical Approach

1. Perturbed Subspace Construction

For each coordinate i, construct a perturbed basis $U_i$: $U_i = -H_{CC}^{-1}H_{Ci}$

This basis represents how a unit perturbation of coordinate i affects the complementary degrees of freedom.

2. Schur Complement Formulation

Express the local displacement as: $\delta x_i = \begin{bmatrix} I & 0 \\ 0 & U_i \end{bmatrix} \begin{bmatrix} \delta x_i \\ \delta \alpha_i \end{bmatrix} = B_i q_i$

Through block elimination, obtain the Schur complement form of the update: $\delta x_i = -(H_{ii} - S)^{-1}\tilde{g}_i$

where:

• $S = H_{iC}U_i\tilde{H}_{ii}^{-1}U_i^T H_{iC}^T$ (Schur complement)
• $\tilde{g}_i = g_i - H_{iC}U_i\tilde{H}_{ii}^{-1}U_i^T g_C$ (corrected gradient)
• $\tilde{H}_{ii} = U_i^T H_{CC}U_i$ (reduced complementary stiffness)

3. Key Differences from JGS2

• JGS2: Uses $(H_{ii} + U_i^T H_{CC}U_i)$ as the update Hessian, strictly increasing system stiffness and always damping updates
• Coordinate Condensation: Subtracts the Schur complement $S$ from $H_{ii}$, effectively reducing stiffness by removing components coupled to the complementary subspace

4. Large Deformation Handling

Addresses nonlinear problems by estimating per-vertex rotations $R_j \in SO(3)$ and rotating corresponding blocks in the basis: $U_i^{rot}[j] = R_j U_i[j]$

Experimental Setup

Test Scenarios

1. 1D Elastic Rod: Pulse loading test analyzing information propagation characteristics
2. 2D Elastic Stretching: Nonlinear quasi-static stretching of square meshes
3. Cantilever Beam Bending: Quasi-static simulation under large deformations
4. Buckling Simulation: Testing extreme nonlinear behavior
5. Unexpected Coupling Test: Spring-induced new coupling

Evaluation Metrics

• Normalized Gradient Norm: $\|g\|/(V \cdot n \cdot E) < \epsilon$
• Convergence Iterations: Number of iterations required to reach specified tolerance
• Energy Decrease: Energy reduction during optimization

Comparison Methods

• Newton's method
• Standard Coordinate Descent
• JGS2
• Various Coordinate Condensation variants

Experimental Results

Main Results

1. Mesh Resolution Scaling Performance

In 2D elastic stretching tests:

• Standard Coordinate Descent: Rapidly reaches 500 iteration limit with mesh refinement
• JGS2: Significant improvement but still far exceeds Newton's method iteration count
• Coordinate Condensation: Approaches Newton's method convergence speed across all resolutions

2. Material Stiffness Scaling Performance

In 1D rod pulse tests:

• Coordinate Condensation: Achieves optimal convergence (single iteration for this quadratic problem)
• Standard Coordinate Descent and JGS2: Severe degradation with increasing stiffness, reaching 10,000 iteration limit at 1e5 Pa

3. Subspace Quality Impact

• Fixed Basis: Convergence degrades under large deformations
• Reconstructed Basis: Subspace reconstructed every 5 time steps, convergence restored
• Co-rotated Basis: Using estimated vertex rotations, maintains good convergence without additional computational cost

Ablation Studies

Noise Sensitivity Testing

Adding random noise to the basis $U_{noisy} = U_{initial} + \sigma \cdot \mathbf{1}$:

• Both variants (with/without global line search) degrade significantly with increasing noise
• Line search improves robustness at moderate noise levels, but fundamental basis quality degradation limits convergence

Unexpected Coupling Test

Adding springs between beam corner vertices:

• CC with Springs: Rapid convergence to lower energy
• JGS2 with Springs: Complete stagnation
• Both Methods without Springs: Complete failure to converge

Related Work

Coordinate Descent Methods

• Vertex Block Descent (VBD): Efficient GPU implementation
• Second-Order Stencil Descent: Second-order stencil descent
• JGS2: Enhanced method using perturbed subspaces

Subspace Methods

• Subspace Compression: Adaptive subspace deformation for full space by Teng et al.
• Adaptive Subspaces: Strategies for detecting new coupling and updating bases

Conclusions and Discussion

Main Conclusions

1. Coordinate Condensation effectively eliminates JGS2's damping effects through Schur complement formulation
2. Achieves convergence rates approaching Newton's method on problems where the subspace accurately captures coupling structure
3. Significantly outperforms standard coordinate descent and JGS2 across varying mesh resolutions and material stiffness

Limitations

1. Basis Quality Dependence: Method performance heavily depends on precomputed basis quality and relevance
2. New Coupling Handling: Precomputed basis cannot adapt when new coupling emerges in simulation (e.g., contact)
3. Extreme Nonlinearity: Co-rotated adaptation proves insufficient in extreme nonlinear cases such as buckling

Future Directions

1. Adaptive Strategies: Detect new coupling emergence and update basis accordingly
2. Error Estimation: Mechanisms to trigger basis updates or fallback to standard coordinate descent
3. Hybrid Methods: Adaptive frameworks combining multiple solution strategies

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Introduction of Schur complement formulation eliminates JGS2's inherent damping with solid theoretical foundation
2. Comprehensive Experiments: Covers diverse scenarios from simple 1D problems to complex nonlinear large deformations
3. Significant Performance Improvement: Achieves near-optimal convergence performance under appropriate conditions
4. Thorough Limitation Analysis: Honestly discusses method failure conditions

Weaknesses

1. Limited Applicability: Heavily dependent on precomputed basis quality, performs poorly with dynamically changing coupling structures
2. Implementation Complexity: Requires additional subspace management and Schur complement computation compared to standard coordinate descent
3. Lack of Real-time Performance Assessment: Primarily focuses on convergence, lacking detailed analysis of actual runtime

Impact

1. Academic Contribution: Provides new theoretical perspective and practical improvements for coordinate descent methods
2. Practical Value: Direct application value in computer graphics and physics simulation
3. Inspirational Value: Provides important insights for future adaptive solver design

Applicable Scenarios

1. Static or Quasi-static Problems: Simulations with relatively stable coupling structures
2. Known Coupling Patterns: Problems where primary coupling structures can be pre-identified
3. Moderate Nonlinearity: Simulations not involving extreme geometric or topological changes

References

Key references include:

1. Lan et al. (2025) - JGS2 method
2. Teng et al. (2015) - Subspace compression techniques
3. Chen et al. (2024) - Vertex Block Descent
4. Gast & Schroeder (2015) - Optimization integrator foundations

This paper makes significant contributions to the field of coordinate descent solvers. Through clever mathematical derivation, it addresses key deficiencies in existing methods, providing more efficient solution approaches for physics simulation. Despite certain limitations, both its theoretical innovation and experimental validation achieve high standards.