Anderson acceleration for geometry optimization and physics simulation

Yue Peng, Bailin Deng, Juyong Zhang, Fanyu Geng, Wenjie Qin, Ligang Liu

This paper presents a simple yet powerful "wrapper" technique to significantly speed up common optimization and simulation algorithms in computer graphics. By applying Anderson Acceleration to popular "local-global" solvers, the authors demonstrate how to achieve high-accuracy results in a fraction of the time usually required, all while maintaining the stability that makes these solvers popular in the first place.

TL;DR

The researchers "turbocharge" standard computer graphics solvers (like Shape-Up and Projective Dynamics) by treating them as fixed-point iterations and applying Anderson Acceleration. This approach achieves orders-of-magnitude faster convergence to high-accuracy solutions with a simple, stable "safety switch" that guarantees the energy always decreases.

What Problem Does This Paper Address?

Many tasks in computer graphics—such as smoothing a 3D mesh, designing architectural wireframes, or simulating the drape of cloth—boil down to non-linear optimization. A popular class of "local-global" solvers (e.g., Shape-Up for geometry and Projective Dynamics for physics) has become the industry standard because they are robust, easy to parallelize, and provide a "good enough" answer very quickly.

However, these solvers have a major weakness: they are "first-order" methods with sublinear convergence. While they get close to the solution fast, they "crawl" when you need high precision. Reaching a high-accuracy state can take thousands of iterations, making them frustrating for applications requiring exactness.

Methods

The authors propose treating the two-step local-global process as a single fixed-point mapping: $Q_{k+1} = G(Q_k)$. Once framed this way, they apply Anderson Acceleration (AA), a technique originally from computational chemistry.

Key Technical Components:

  • Multi-secant Acceleration: Unlike standard iterations that only look at the current state, AA looks at the last $m$ iterations (typically $m=5$). It finds an optimal linear combination of these previous states to minimize the "residual" (the difference between where you are and where the solver wants to move you).
  • The "Safety Switch": AA can occasionally be unstable and "jump" to a worse state. The authors introduce a simple energy check: if the accelerated step increases the target energy, the algorithm rejects it and reverts to the standard, reliable local-global step. This ensures monotonic decrease and global convergence.
  • Quasi-Newton Connection: The paper provides a theoretical analysis showing that AA is essentially a quasi-Newton method. They demonstrate that for these specific graphics problems, the "mixing parameter" $\beta$ should be set to 1, which simplifies the implementation.

Datasets

The paper evaluates the method on a wide variety of geometric models and simulation scenarios rather than a single "training" dataset. These include:

  • Geometry Optimization: Planar quadrilateral (PQ) meshes and material-aware wire mesh designs (e.g., a 230K vertex "Male Torso" model).
  • Deformation: 2D and 3D bar models under ARAP (As-Rigid-As-Possible) constraints.
  • Physics Simulation: Cloth and elastic solid simulations (e.g., the "Armadillo" mesh).
  • Stress Tests: A massive 50-million-vertex wire mesh model to test scalability.
  • Other Solvers: Lloyd’s algorithm for Voronoi tessellation and the SLIM solver for mesh parameterization.

Key Insights and Ideas

  • AA as a "Plug-and-Play" Wrapper: One of the most elegant aspects is that you don't need to rewrite the underlying solver. You simply wrap the existing local and global steps in the AA logic.
  • Negligible Overhead: The cost of the acceleration (solving a tiny $5 \times 5$ linear system) is practically zero compared to the cost of mesh projections and large-scale linear solves.
  • The Power of Memory: By using just a few previous iterations, the algorithm effectively "learns" the curvature of the optimization landscape, allowing it to take much smarter steps than a standard first-order solver.

Key Results

  • Speedup: In many cases, the method reaches a high-accuracy threshold (relative energy error of $10^{-10}$) 10x to 100x faster than the unaccelerated version.
  • Comparison to State-of-the-Art: The method performs comparably to or better than L-BFGS and Chebyshev acceleration. In physics simulations, it produced results much closer to the "ground truth" exact solution within the same time budget compared to other methods.
  • Robustness: The "safety switch" worked as intended; even when started far from a solution or used on meshes with degenerate (broken) elements, the solver remained stable.

Limitations and Future Work

  • Hard Constraints: The current formulation focuses on "soft" constraints (minimizing a penalty). The authors note that strictly enforcing "hard" constraints (which must be satisfied exactly) would require integrating this with other frameworks like ADMM or Augmented Lagrangians.
  • Parameter Tuning: While $m=5$ and $\beta=1$ worked well for their tests, they acknowledge that for general fixed-point problems outside of local-global graphics solvers, choosing these parameters automatically remains an open research question.
  • Theoretical Convergence: While the energy check guarantees the energy goes down, it doesn't strictly prove that the variables themselves converge to a specific point in all mathematical edge cases, though this was never an issue in their extensive practical testing.

Summary updated

Abstract

Many computer graphics problems require computing geometric shapes subject to certain constraints. This often results in non-linear and non-convex optimization problems with globally coupled variables, which pose great challenge for interactive applications. Local-global solvers developed in recent years can quickly compute an approximate solution to such problems, making them an attractive choice for applications that prioritize efficiency over accuracy. However, these solvers suffer from lower convergence rate, and may take a long time to compute an accurate result. In this paper, we propose a simple and effective technique to accelerate the convergence of such solvers. By treating each local-global step as a fixed-point iteration, we apply Anderson acceleration, a well-established technique for fixed-point solvers, to speed up the convergence of a local-global solver. To address the stability issue of classical Anderson acceleration, we propose a simple strategy to guarantee the decrease of target energy and ensure its global convergence. In addition, we analyze the connection between Anderson acceleration and quasi-Newton methods, and show that the canonical choice of its mixing parameter is suitable for accelerating local-global solvers. Moreover, our technique is effective beyond classical local-global solvers, and can be applied to iterative methods with a common structure. We evaluate the performance of our technique on a variety of geometry optimization and physics simulation problems. Our approach significantly reduces the number of iterations required to compute an accurate result, with only a slight increase of computational cost per iteration. Its simplicity and effectiveness makes it a promising tool for accelerating existing algorithms as well as designing efficient new algorithms.
BibTeX
@article{peng2018anderson,
  author = {Yue Peng and Bailin Deng and Juyong Zhang and Fanyu Geng and Wenjie Qin and Ligang Liu},
  title = {{Anderson acceleration for geometry optimization and physics simulation}},
  journal = {ACM Trans. Graphics},
  year = {2018},
  url = {https://openreview.net/forum?id=qMJ2mZpV6vg},
}

Loading related content...

Figure