(Almost) Matrix-free solver for piecewise linear functions in Abs-Normal form
The abs-normal form (ANF) is a compact algebraic representation for piecewise linear functions. These functions can be used to approximate piecewise smooth functions and contain valuable information about the non-smoothness of the investigated function. The information help to define step directions within general Newton methods that obey the structure of the original function and typically yield better convergence. However, the computation of the generalized Newton directions requires the solution of a piecewise linear equation in ANF. It was observed that the ANF can become very large, even for simple functions. Hence, if a solver is based on the ANF and uses the (Schur-complement) matrices of the explicit ANF representation, it has to be considered computational expensive. In this paper, we will address this question and present the first (almost) matrix-free versions of some solver for ANFs. The theoretical discussion is supported by some numerical run-time experiments.