We are concerned with the fastest possible direct numerical solution algorithm for a thin-banded or tridiagonal linear system of dimension $N$ on a distributed computing network of $N$ nodes that is connected in a binary communication tree. Our research is driven by the need for faster ways of numerically solving discretized systems of coupled one-dimensional black-box boundary-value problems. Our paper presents two major results: First, we provide an algorithm that achieves the optimal parallel time complexity for solving a tridiagonal linear system and thin-banded linear systems. Second, we prove that it is impossible to improve the time complexity of this method by any polynomial degree. To solve a system of dimension $m\cdot N$ and bandwidth $m \in \Omega(N^{ 1/6})$ on $2 \cdot N-1$ computing nodes, our method needs time complexity $\mathcal{ O}(\log(N)^2 \cdot m^3)$.
Categories: math.NA