A parallel algorithm solving a tridiagonal Toeplitz linear system
Authors:
Hyoung Joong Kim and Jang Gyu Lee
Affiliation:
Department of Control and Instrumentation Engineering, Kangwon National University, Chooncheon 200-701, Korea
Department of Control and Instrumentation Engineering, Seoul National University, Seoul 150-742, Korea
Abstract:
A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).