Progressively Projected Newton's Method

Computer Graphics Forum

Abstract

Abstract Newton's Method is widely used to find the solution of complex non‐linear simulation problems. 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's residual to cheaply determine the subset of element Hessians to project. The benefit is twofold: most eigendecompositions are avoided and the global Hessian remains closer to its original form, reducing the number of Newton iterations. We compare PPN with PN and Project‐on‐Demand Newton (PDN) in a comprehensive set of experiments covering contact‐free and contact‐rich deformables, co‐dimensional and rigid‐body simulations, and a range of time step sizes, tolerances and resolutions. PPN reduces the amount of element projections in dynamic simulations by one order of magnitude while simultaneously improving convergence, consistently being the fastest solver in our benchmark.

Authors 3

1. José Antonio Fernández-Fernández Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Aachen Germany

2. Fabian Löschner Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Aachen Germany

3. Jan Bender Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Aachen Germany