Parallel Solution of Diagonally Dominant Banded Triangular Toeplitz Systems Using Taylor Polynomials

摘要

We present a new numerical and inherently parallel algorithm for solving banded (strictly) diagonally dominant triangular and banded Toeplitz (BDDTT) systems of linear equations. A Taylor polynomial, derived from the matrix analog of the Taylor Series for evaluating (1-x)-1 where |x| <; 1, is applied, in conjunction with other techniques, to compute an approximate solution to a BDDTT-type system. This method requires O(n log2 n) arithmetic operations (ops) and O(log2 n) parallel steps (steps). Two FFTs and an IFFT of order 2n are the main contributors to the workload. This matches the FFT count for a triangular Toeplitz-matrix-vector multiplication. Clearly then, our method improves on the many algebraic FFT based processes that first determine the triangular Toeplitz matrix that is the inverse of a BDDTT matrix in order to then solve the associated BDDTT system.