摘要
该文利用块三对角阵分解因子的估值分析了其局部依赖性 ,并用其构造了一类不完全分解型预条件子 ,给出了五点差分矩阵预条件后的条件数估计 ,并比较了条件数估计值与实际值 ,表明了估计值的准确性与预条件的有效性 .在具体实现时 ,考虑了预条件的 6个串行实现方案并提出了一个有效的并行化方法 ,该并行算法具有通信量少的特点 .最后在由 4台微机通过高速以太网连成的机群系统上作了大量数值实验 ,并将其与其它较有效的预条件方法进行了比较 ,结果表明该预条件方法效果较好 ,尤其适用于并行计算 .
The core of many physical applications is how to solve systems of sparse linear equations efficiently. In general direct methods lead to large requirements both in storage and computation. Moreover, when the condition number of the coefficient matrix is large, direct methods are poor in stability. Based on these considerations, more and more researchers focused on iterative methods in recent years. But iterative methods may converge very slowly, or even diverge. One solution to this problem is to construct preconditioners. Preconditioners based on incomplete decomposition of the coefficient matrix have been proved to be efficient. But this kind of preconditioner is hard to be parallelized. In this paper, we consider block tridiagonal matrices. For this kind of matrices, their factorizations have local dependence in some sense, which is analyzed with the help of the evaluation of the actual factors. Then this kind of localization is exploited to construct a type of preconditioners. To analyze this kind of preconditioner, we first give a theorem about the condition number of a preconditioned symmetric M matrix, and then the condition numbers of the preconditioned model matrix are evaluated. With the comparison of these evaluations to the actual ones that are computed with the help of MATLAB, we can conclude that the evaluation is very accurate. Further the condition numbers are small, which means that the constructed preconditioners are effective. To study the efficiency of the preconditioner further, six implementations of the preconditioner are given in this paper. At the same time, there also considers an efficient parallelization, which has the advantage of low communication requirements. Then lots of experiments are done on a cluster of 4 PCs connected with Fast Ethernet to test the provided algorithms. The results show that the preconditioners constructed in this paper are comparable to the known effective ones in serial implementation, but they are more appropriate in parallel computing.
出处
《计算机学报》
EI
CSCD
北大核心
2002年第8期823-829,共7页
Chinese Journal of Computers
关键词
块三对角矩阵
局部块分解
预条件
并行算法
数值解
微机
M matrix, block LU decomposition, incomplete factorization, preconditioner, parallel algorithm
