2023/05/02 by Uwe Naumann, Naumann, Uwe
Computer Science · Mathematics · #47A05 #49M15 #68N99 #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Software (cs.MS) #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2305.01669
openalex publication_date 2023/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A modification of Newton's method for solving systems of n nonlinear equations is presented. The new matrix-free method relies on a given decomposition of the invertible Jacobian of the residual into invertible sparse local Jacobians according to the chain rule of differentiation. It is motivated in the context of local Jacobians with bandwidth 2m+1 for m≪ n. A reduction of the computational cost by O((n)/(m)) can be observed. Supporting run time measurements are presented for the tridiagonal case showing a reduction of the computational cost by O(n). Generalization yields the combinatorial Matrix-Free Newton Step problem. We prove NP-completeness and we present algorithmic components for building methods for the approximate solution. Inspired by adjoint Algorithmic Differentiation, the new method shares several challenges for the latter including the DAG Reversal problem. Further challenges are due to combinatorial problems in sparse linear algebra such as Bandwidth or Directed Elimination Ordering.