求解一类线性方程组的并行算法.pdfVIP

维普资讯 第 lo卷第l期 新■大学学报(自然科学版) Vol_10，No．1 1993年 2月 JournalofXin~angUniversity Feb．．1993 6一lo u 求解一类线性方程组的并行算法’ 郑 盛 林 (新疆大学教学幕鸟鲁木齐830046) TP 。I6 摘 要 ． 本文讨论了由求解偏擞分方程产生的一种线性方程组的井行算法，井给 出了相应的计算复杂度 关键词 并行算法 SIMD算法 正变三^形分解 线性方程组 中囝分粪号 0151．21 0241．6 0 引 言 本文研究的线性方程组是在用子结构法、区域分裂法求解偏微分方程时产生的 “ ，先给 出了一个并行算法 ，然后讨论了相应的并行计算复杂度 - 本文研究的并行算法是面 向SIMD系统的SIMD算法 ．关于SIMD系统，有如下假设”。： (1)处理机数 目的假设 ：在任何时间可用任意多个处理机 、 (2)存储器的假设．在任何时间有任意多个单元的主存储器可供每个处理机存取，不存在 任何存取冲突． (3)时间的假设 ：处理机与存储器传递数据不需时间，每个运算都花同样的时间量，称作一 单位步． 具有 个进程和n个作业层的SIMD算法的最基本特征是 ： (1) n 1，即为同步算法． (2) 每个并行层中的作业彼此恒同，即每个并行操作步所台操作必须完全相同． (3) 能在一个具有 台处理机的SIMD系统中实现 ，一个并行操作步由一条指令控制- 本文结论的证 明方法参见[1]中的定理 5．1． 1 算 法 我们研究求解如下线性方程组 ●|l．|一l ， ●—■ A． 匡 B … … ． 假设 均为偶数 ，A．是 ×^阶非奇异矩阵，并且没有特殊结构 是 ^×1阶矩阵( 0，1， …，m)．通过块初等变换 ，(1)化成如下方程组； ·1992—01—01收到 维普资讯 第 1期 ． 求解一类线性方程组的并行算法 鼍 ● 辱 ■■量 『 Jr_ AtCI AjFJ l ^ C‘2 ^ Fz ‘ ． ： (2) J， ^二C ^= F．