A time-optimal algorithm for solving (block-)tridiagonal linear systems of dimension N on a distributed computer of N nodes
This provides a fundamental lower bound and optimal algorithm for parallel tridiagonal system solving, relevant to numerical simulation of coupled boundary-value problems.
The paper presents a time-optimal algorithm for solving tridiagonal and thin-banded linear systems on a distributed network of N nodes, achieving O(log(N)^2 * m^3) time complexity for systems of dimension m*N and bandwidth m, and proves that no polynomial improvement is possible.
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 Ω(N^{1/6})$ on $2 \cdot N-1$ computing nodes, our method needs time complexity $\mathcal{O}(\log(N)^2 \cdot m^3)$.