Efficient signed backward substitution for piecewise affine functions via path problems in a directed acyclic graph.

Abstract

We introduce an efficient signed backward substitution for a highly-structured system. More precisely, the problem is to find a vector u of dimension s that solves the system of piecewise affine equations u = c + L|u|, where L is a strictly lower left triangular s times s matrix, c denotes a given vector of dimension s, and the notation |cdot| indicates the component-wise absolute value of a vector. The novel approach is based on a Neumann series reformulation and attempts to exploit a high degree of parallelism. We provide an analysis of its parallel run-time and show that it is suited for large, sparse systems whose triangular matrix has a small switching depth. The general idea behind this approach which is also used in the convergence proof is based on modelling the switching depth by a graph theoretic model. The key observation is that the computation of the switching depth corresponds to a single-pair shortest path problem in a directed acyclic graph. The proposed method is implemented and numerically evaluated using several examples whose problem structures are representative of various applications in scientific computing.