(Almost) matrix-free solver for piecewise linear functions in abs-normal form.

Abstract

Summary 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 nonsmoothness of the investigated function. The information helps 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 computationally 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.