带状（块）Toeplitz方程组的快速并行算法

FAST AND PARALLEL ALGORITHMS FOR SOLVING BAND (BLOCK) TOEPLITZ SYSTEMS OF EQUATIONS

带状（块）Ｔｏｅｐｌｉｔｚ方程组的快速并行算法成礼智，蒋增荣（国防科技大学）ＦＡＳＴＡＮＤＰＡＲＡＬＬＥＬＡＬＧＯＲＩＴＨＭＳＦＯＲＳＯＬＶＩＮＧＢＡＮＤ（ＢＬＯＣＫ）ＴＯＥＰＬＩＴＺＳＹＳＴＥＭＳＯＦＥＱＵＡＴＩＯＮＳ￥ＣｈｅｎｇＬｉ－ｚｈｉ；Ｊｉ...

Abstract In this paper, an efficient fast and parallel algorithm for solving band (block)Toeplitz systems of equations are developed. The amount of operations in serial is (3np2+ p2) M(m) + O(1), which is exactly the same as the best result in [10]when m = 1. The amount of operations in parallel is (M (pm) + p2m2) log2n + 3P M(m)+ o(1), where n is the order of the matrix, p is the bandwidth, and M(k) is the amount of operations for matrix multiplication with order k. Finally the validity of the presented algorithm is shown by solving Toeplitz equations with YH -I.