A survey of parallel direct methods for block bidiagonal linear systems on distributed memory computers (Q1912863)

The paper presents a survey of four dominant direct parallel algorithms for solving linear systems with a block bi-diagonal matrix. The first one is a variant of the sequential algorithm and three remaining ones (Brugnano's reduction algorithm, factorization method and the generalized cyclic reduction method) are parallel approaches primarily developed for parallel solving banded linear systems. The methods for a given problem are compared with respect to their arithmetic computational complexity and memory demands. An observation is made that a recommendation for using a proper approach depends heavily on the size of the system and the number of blocks. The implementation results show also a dependence on the parameters of the distributed-memory system like the memory capacity per processor and the latency.