Progressively Projected Newton's Method
For computer graphics simulations involving deformable objects, this work offers a faster solver that reduces computational cost while maintaining convergence.
The authors introduce Progressively Projected Newton (PPN), a variant of Newton's Method that selectively projects only a subset of element Hessians to ensure a descent direction, reducing Newton iterations and eigen-decompositions. In experiments, PPN performs fewer than 10% of the projections required by Projected Newton or Project-on-Demand Newton and is the fastest solver in most cases, except for very large time steps and quasistatics.
Newton's Method is widely used to find the solution of complex non-linear simulation problems in Computer Graphics. To guarantee a descent direction, it is common practice to clamp the negative eigenvalues of each element Hessian prior to assembly - a strategy known as Projected Newton (PN) - but this perturbation often hinders convergence. In this work, we observe that projecting only a small subset of element Hessians is sufficient to secure a descent direction. Building on this insight, we introduce Progressively Projected Newton (PPN), a novel variant of Newton's Method that uses the current iterate residual to cheaply determine the subset of element Hessians to project. The global Hessian thus remains closer to its original form, reducing both the number of Newton iterations and the amount of required eigen-decompositions. We compare PPN with PN and Project-on-Demand Newton (PDN) in a comprehensive set of experiments covering contact-free and contact-rich deformables (including large stiffness and mass ratios), co-dimensional, and rigid-body simulations, and a range of time step sizes, tolerances and resolutions. PPN consistently performs fewer than 10% of the projections required by PN or PDN and, in the vast majority of cases, converges in fewer Newton iterations, which makes PPN the fastest solver in our benchmark. The most notable exceptions are simulations with very large time steps and quasistatics, where PN remains a better choice.