PaperlayerView exact revision on arXiv

Source-linked AI summary

Anderson Acceleration for Geometry Optimization and Physics Simulation

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

arXiv:1805.05715v1cs.GRcs.NAmath.NA

TL;DR

Local-global solvers efficiently produce approximate solutions for constrained geometry and physics problems, but may converge slowly to high accuracy. The paper applies Anderson acceleration with an energy-based selection strategy and reports fewer iterations at slight additional per-iteration cost across varied problems.

  • Problem

    Local-global solvers can take a long time to compute accurate results, limiting their appeal for interactive optimization despite efficiently producing approximate solutions.

    Source: §1 · p. 2

  • Method

    The paper treats local-global steps as fixed-point iterations, applies Anderson acceleration, and reverts to the local-global iterate when acceleration increases target energy.

    Source: §1 · p. 2

  • Results

    The method achieves comparable or better results than state-of-the-art fast solvers on varied problems, while reducing iterations for high-accuracy solutions with only a slight per-iteration cost increase.

    Source: §1 · p. 2, §6 · p. 13

  • Takeaways & Limitations

    The technique can increase accuracy within a fixed time budget or reduce computational cost at a fixed accuracy, and also applies to other iterative solvers meeting stated conditions.

    Source: §1 · p. 2

    Choosing the mixing parameter automatically for general fixed-point solvers remains an open research problem; β = 1 is not established as effective for all such solvers.

    Source: §6 · p. 13

Abstract

from arXiv · show

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.

1 INTRODUCTION

Anderson acceleration reduces the iterations needed for accurate geometry and physics solutions while preserving local-global solvers’ efficiency. The paper also addresses stability, analyzes the mixing parameter, and extends the approach to other iterative solvers under stated conditions.

1 INTRODUCTION

  • Nonlinear constraints and globally coupled variables make interactive shape optimization challenging, while Newton-type solvers require costly gradient, Hessian, and linear-system computations.Local-global solvers produce approximate solutions efficiently but may take a long time to reach high accuracy because convergence is generally sublinear.Source: §1 · p. 2
  • The paper treats local-global steps as fixed-point iterations and applies Anderson acceleration to speed their convergence.The authors also report effectiveness on other solvers with a similar structure.Source: §1 · p. 2
  • If an accelerated iterate increases target energy, the solver reverts to the local-global iterate, guaranteeing monotonic energy decrease with slight added per-iteration cost.This selection strategy addresses Anderson acceleration’s lack of a global-convergence guarantee and possible stagnation from a distant starting point.Source: §1 · p. 2
  • For the problems considered, the canonical mixing parameter β = 1 is suitable, and Anderson acceleration is closely related to L-BFGS through an equivalent initial approximate Hessian.The methods differ in how they adapt that approximation using a limited number of previous iterations.Source: §1 · p. 2
  • The method significantly reduces iterations for high-accuracy solutions with only a slight increase in per-iteration cost, and can trade time for accuracy or computational cost.It is evaluated on geometry processing and physics simulation problems.Source: §1 · p. 2
  • Beyond local-global solvers, the approach applies when iterations decrease target energy and consecutive iterates are related by well-defined mappings.The authors propose a general procedure and showcase it on two geometric computing algorithms.Source: §1 · p. 2

2 RELATED WORK

Related work spans local-global methods for geometry and simulation, techniques for accelerating their convergence, and other fast geometry optimizers. Anderson acceleration has a separate history across numerical and scientific computing.

Local-global solvers

  • Local-global formulations support geometry tasks including ARAP modeling, parameterization, geometric constraints, mass-spring simulation, and projective dynamics.These methods use auxiliary variables to represent closest feasible configurations or local deformations.Source: §2 · p. 3
  • For projective dynamics, Chebyshev semi-iteration, preconditioned gradient descent, and L-BFGS have been used to accelerate convergence.The cited L-BFGS method reports faster convergence than the local-global solver.Source: §2 · p. 3

Fast geometry optimization

  • Other fast geometry optimizers use nonlinear least squares, local convex quadratic proxies, reweighted proxies, or convex majorizers.The cited methods address geometric constraints or energies through distinct optimization formulations.Source: §2 · p. 3

Anderson acceleration

  • Anderson acceleration has been used in quantum chemistry, electronic-structure calculations, nonlinear PDEs, and other iterative numerical problems.It has also been analyzed as a quasi-Newton method that uses previous iterates to approximate the inverse Jacobian [Eyert 1996; Fang and Saad 2009; Rohwedder and Schneider 2011].Source: §2 · p. 3

3 BACKGROUND

The background describes local-global optimization for geometric constraints and its related use in physics simulation. Both formulations alternate projections with a global position update.

3 BACKGROUND

  • The background reviews local-global solvers as preparation for discussing their acceleration.The formulation represents point positions and constraint projections using auxiliary variables.Source: §3 · p. 3, §3.1 · p. 4

3.1 Geometry optimization

  • For geometry optimization, the local step projects constrained elements onto feasible sets, while the global step solves a sparse positive-definite system for point positions.The fixed system matrix permits precomputation of a Cholesky factorization; both steps can be parallelized and lower energy until a local minimum is reached.Source: §3.1 · p. 4

3.2 Physics simulation

  • In physics simulation, projective dynamics formulates implicit time integration as optimization, with constraint terms defining potential energies and induced internal forces.It alternates projection updates with a global sparse positive-definite solve, then computes velocities from the updated positions.Source: §3.2 · p. 4

4 OUR METHOD

The method accelerates local-global optimization by treating its steps as a fixed-point iteration and applying Anderson acceleration. An energy-based selection strategy stabilizes acceleration, while the analysis motivates β = 1 and extension to other iterative solvers.

4.1 Anderson acceleration

  • Anderson acceleration models the fixed-point map using recent iterates and selects a new iterate by minimizing the residual within their affine subspace.The local and global steps are combined into a fixed-point iteration; the model is formed by barycentric interpolation and the residual minimization is a linear least-squares problem.Source: §4.1 · pp. 4–5

4.2 Improving stability

  • The energy check accepts the accelerated iterate only when its target energy decreases; otherwise, it reverts to the local-global iterate, preserving monotonic energy decrease and convergence to a local minimum.The paper's lower-cost check compares against the previous iterate and adds only one energy evaluation when the accelerated iterate decreases energy.Source: §4.2 · pp. 5–6
  • At equal computational time, comparing the accelerated iterate with the previous iterate gives faster target-energy decrease than the other tested energy-checking strategies.The comparison is for PQ mesh optimization; energy is checked to select the next iterate.Source: Figure 2 · p. 5, §4.2 · p. 6

4.3 Choice of m

  • Beyond m = 6, increasing the number of previous iterates brings limited convergence improvement, so the method uses m = 5 by default.Larger m uses more information but raises computational cost and can overfit iterates far from the solution.Source: §4.3 · p. 6, Figure 3 · p. 6

4.4 Analysis

  • Anderson acceleration is interpreted as a quasi-Newton method whose inverse-Jacobian approximation satisfies m secant equations, and β = 1 initializes it consistently with the local-global solver's fixed-projection assumption.Unlike L-BFGS's sequential two-loop updates, the method enforces the m secant equations together and parallelizes its m inner products.Source: §4.4 · pp. 6–7

4.5 Beyond local-global solvers

  • The method also applies to iterative solvers that monotonically decrease target energy and have a well-defined mapping between consecutive iterates.Some solvers that do not strictly meet these conditions may still be accelerated with minor modification.Source: §4.5 · p. 7

5 RESULTS

The experiments compare accelerated geometry and physics solvers with existing methods using relative energy or distance errors over time and iterations. They also test Anderson acceleration on Lloyd and SLIM solvers and under stress-test conditions.

5.1 Geometry Optimization

  • The accelerated Shape-Up solver reaches the planarization final solution with significantly fewer iterations and less computational time than unaccelerated Shape-Up.For wire-mesh optimization, the accelerated solver takes a fraction of the iterations to compute an accurate result, significantly reducing computational time.Source: §5.1 · pp. 8–9
  • For ARAP deformation, the accelerated solver converges to the lowest energy in most cases, though different solvers can reach different local minima.Figure 5 plots relative energy errors across resolutions; its caption notes that CM may converge to a suboptimal local minimum.Source: Figure 5 · p. 8, §5.1 · p. 10

5.2 Physics simulation

  • With equal per-frame computational budgets, the accelerated solver’s cloth simulation is closer to the exact solution than the other methods.For physics simulation, all three accelerated solvers outperform original Projective Dynamics; Anderson acceleration has similar energy decrease per iteration to L-BFGS but lower computational time, while Newton’s high per-iteration cost limits its time performance.Source: Figure 9 · p. 10, §5.2 · p. 11

5.3 Other solvers

  • For Lloyd’s CVT solver, acceleration achieves speed-up comparable to L-BFGS without evaluating the gradient or using a preconditioner.An accelerated iterate is accepted only if it decreases target energy and keeps generating points inside the domain; otherwise, the method reverts to Lloyd’s result.Source: §5.3 · p. 12
  • For SLIM, acceleration effectively speeds optimization of symmetric Dirichlet energy, but remains slower than the CM solver.SLIM’s proxy solution is accelerated because discrete line search means consecutive iterates lack a well-defined mapping; the selected next iterate is checked against the original target energy.Source: §5.3 · p. 12

5.4 Stress Tests

  • On a wire mesh with over 50M vertices, the method achieves similar speedup to the smaller model while using one Jacobi step for the global linear system.Full convergence took too long, so the experiment plots energy rather than relative energy errors.Source: §5.4 · p. 12, Figure 12 · p. 12
  • The physics-simulation method remains effective after 100 randomly added degenerate tetrahedrons are introduced to the Armadillo model.The added tetrahedrons are formed by inserting a vertex within a randomly selected triangle face and connecting it to the face’s three vertices.Source: §5.4 · pp. 12–13
  • On a Hilbert-curve-shaped mesh unwrapped onto a cylinder, the accelerated SLIM solver achieves the fastest energy decrease and convergence to the solution.The comparison uses the difference between each solver’s resulting energy and the ground-truth minimum energy.Source: §5.4 · p. 13, Figure 14 · p. 13

6 DISCUSSION AND CONCLUSION

The paper concludes that Anderson acceleration is effective for local-global solvers and reports comparable or better results than state-of-the-art fast solvers across varied problems. It also identifies limits in mixing-parameter selection, convergence guarantees, solver scope, and the use of Type-I acceleration.

6 DISCUSSION AND CONCLUSION

  • The canonical mixing parameter β = 1 is effective for local-global formulations, but choosing β for general fixed-point solvers remains open.Other β values can produce better convergence on some problems.Source: §6 · p. 13
  • The default selection strategy can accept an accelerated iterate with higher energy than the local-global iterate, and monotonic energy decrease does not guarantee convergence to a critical value or convergence of variables.The authors report no such pathological cases in their experiments and call for further investigation of the strategy's convergence behavior.Source: §6 · p. 13
  • The paper discusses Anderson acceleration as Type-II; investigating the application and performance of the Type-I method remains future work.Type-I approximates the Jacobian rather than its inverse.Source: §6 · p. 13
  • Beyond fixed node positions, the approach does not support general hard constraints; extending it to solvers with primal and dual variables remains future work.The paper notes that such constraints can be handled using dual variables with an augmented Lagrangian or ADMM solver.Source: §6 · p. 13
  • The technique achieves comparable or better results than state-of-the-art fast solvers across varied problems and also applies beyond classical local-global solvers.The authors describe it as a promising tool for improving existing algorithms and designing new ones.Source: §6 · p. 13

Related papers

Loading 1805.05715v1…