We introduce a new numerical approach for the solution of grid-based discretizations of nonlinear elastic models. Our method targets the linearized system of equations within each iteration of the Newton method, and combines elements of a direct factorization scheme with an iterative Conjugate Gradient method. The goal of our hybrid scheme is to inherit as many of the advantages of its constituent approaches, while curtailing several of their respective drawbacks. In particular, our algorithm converges in far fewer iterations than Conjugate Gradients, especially for systems with less-than-ideal conditioning. On the other hand, our approach largely avoids the storage footprint and memory-bound nature of direct methods, such as sparse Cholesky factorization, while offering very direct opportunities for both SIMD and thread-based parallelism. Conceptually, our method aggregates a rectangular neighborhood of grid cells (typically a 16x8x8 subgrid) into a composite element that we refer to as a “macroblock”. Similar to conventional tetrahedral or hexahedral elements, macroblocks receive nodal inputs (e.g., displacements) and compute nodal outputs (e.g., forces). However, this input/output interface now only includes nodes on the boundary of the 16x8x8 macroblock; interior nodes are always solved exactly, by means of a direct, highly optimized solver. Models built from macroblocks are solved using Conjugate Gradients, which is accelerated due to the reduced number of degrees of freedom and improved robustness against poor conditioning thanks to the direct solver within each macroblock. We explain how we attain these benefits with just a small increase of the per-iteration cost over the simplest traditional solvers.

@InProceedings{MDS16,
  author       = "Mitchell, Nathan and Doescher, Michael and Sifakis, Eftychios",
  title        = "A Macroblock Optimization for Grid-Based Nonlinear Elasticity",
  booktitle    = "ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA)",
  month        = "jul",
  year         = "2016",
  doi          = "10.2312/sca.20161218",
  projecturl   = "http://nathanmitchell.graphics/publications/macroblocks/",
  url          = "http://graphics.cs.wisc.edu/Papers/2016/MDS16"
}