Designing optimal algorithms for solving banded triangular systems on rings (Q1868492)

The critical part of several numerical algorithms reduces to the problem of solving banded triangular linear systems which is referred to the problem of solving linear recurrence systems. The authors introduce a parallel algorithm for solving such problems on distributed memory parallel computers based on a ring topology, together with the detailed analysis of its complexity. The algorithm relies on data layouts and a combination of broadcast schemes is used to ensure overlapping of communication and computation. First, the authors provide some basic facts on lower bounds based on a data layout and communication pattern of a substitution algorithm. Then they show that their algorithm achieves these bounds within an additive constant.