BibTeX
@INPROCEEDINGS{
         Bosse2021Esb,
       author = "T. Bosse and R. Seidler and H. M. B{\"u}cker",
       title = "Efficient signed backward substitution for piecewise affine functions via path
         problems in a directed acyclic graph",
       booktitle = "Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete
         Algorithms (ACDA21), July~19--21, 2021",
       editor = "M. Bender and J. Gilbert and B. Hendrickson and D. B. Sullivan",
       pages = "171--181",
       address = "Philadelphia, PA, USA",
       publisher = "SIAM",
       doi = "10.1137/1.9781611976830.16",
       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.",
       year = "2021",
       ad_theotech = "Combinatorics, Computational Graph, Piecewise Linear"
}