The arrowhead decomposition method for a block-tridiagonal system of linear equations

The arrowhead decomposition method (ADM) for the parallel solution of a block-tridiagonal system of linear equations is presented. The method consists in rearranging the initial linear system into an equivalent one with the "arrowhead" structure of the matrix. It is shown that such a structure provides a good opportunity for parallel solving. The computational speedup of ADM with respect to the sequential matrix Thomas algorithm is analytically estimated based on the number of elementary multiplicative operations for the parallel and serial parts of the methods. A number of parallel processors required to reach the maximum computational speedup is found. A good agreement of the analytical estimations of the computational speedup and practically obtained results is observed.