可換なブロック3重対角連立1次方程式の高速並列アルゴリズム

概要

論文の詳細を見る
We consider solving equations Mx=b with following the block tridiagonal coefficient matrix [chemical formula] where A_1, B_1, and C_1 are all n×n matrices, and there exists a constant matrix G, G is satisfied with a)GA_j=A_jG, j=1〜m, GB_j=B_jG, j=1〜m-1, GC_j=C_jG, j=2〜m. b)G has n distinct eigenvalues. In this paper, we present a fast and parallel direct method for solving this linear systems. If the operation time to reduce G into Jordan canonical form is disregarded, then this method takes 10mn^2+8mn-4n^2 arithmetic operations at most. And the number of parallel steps of this method is O(log_2N) at most by using mn^2 processors, where N=max(m, n). Specially, for the linear systems which is got by disturbing the diagonal elements of coefficient matrix of Poisson difference equations, the number of arithmetic operations of this method is O(mnlog_2n) at most by using FFT algorithm. And the number of its parallel steps is O(log_2N) at most by uising mn processoes, where N=max(m, n).
日本応用数理学会の論文
1994-09-15