  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.
