线性方程组大数法快速并行解法.pdf

2 0 0 3年 8月 第 4 O 卷第4 期 四川大学学报 自然科 学版 j o u r n a l o f S i c h u a n Un i v e r s i t y Na t u r a l S c i e n c e E d i t i o n Au g 2 0 0 3 Vo 1 4 0 No 4 文章麴 号 0 4 9 0 6 7 5 6 2 0 0 3 0 4 0 6 2 6 0 6 线 性 方 程组大 数 法快速 并行 解 法 杨本 立 中国工程物理研究院职TT学院 四川绵阳 6 2 1 9 0 0 摘要 利用 S e h mi d t 正交规 范化方法和分治策略 给 出了一个求解含部 分 已定值变量的任 意线 性代数方程组的快速 并行迭代解法 分析 了解法的收敛性和计算复杂度 探 讨 了解法的 内在并 行性及其对应的消息传递并行算法的设计 方法 关键词 线性代数方程组 MGS方法 分 治策略 行处理法 并行迭代 解法 中圈分类号 0 2 4 1 6 O 2 4 6 文献标识码 A 1 预备知识 将任意的 Xm阶线性代数方程组 AX b A R b R 1 1 记为 a i X b L 1 1 一 1 2 或者 z n 一6 1 1 问题为 设 cx x 1 已给定 要求出x中其余的分量的值并保留 1 1 的同解方程组 A X b 的数据 A I 6 问题在给出线性代数方程组解结构的计算中不可避免 有较大的理论价值和实用价值 本文给出此问题 的一个并行迭代计算方案 对应的程序算法及 的给出方法不在本文讨论 定义 1 1 对 1 2 m 及 1 2 用 e tl 表示第 t 分量等于 1 而其余分量等于 0的 m维向 量 用 z 表示 X R l 中第 分量和 Yr Y由 1 篮7 f 7 z 分量 设 为已知实数 将 Xm 阶线性方程 f f n x b l 1 i 一1 2 x 一 1 2 记为 或者 1 称 x是 1 1 的已定值集合或已定值 2 称 A I 是 1 1 的约束 收 稿 日期 2 0 0 3 0 2 1 8 基金项 目 中国工程物理研究院科学技术基金 2 2 O 6 5 6 作者简介 杨本立 1 9 4 7 一 男 副教授 1 I 2 1 2 r i 菰 丽 i 疆l m一 r L r J 1 I 1 A IL 维普资讯 币 4朋 杨本立 线性 方程组天数 法快速并行 解法 6 2 7 3 称求解 1 2 为求解含部分已定值变量 的线性代数方程组 1 1 针对实际应用 在问题 1 2 中约定 n 当且仅当 以及 1 仇一r a n k A 问题 1 2 有解的 必 要 充 分 条 件 是 r a n k 会 r a n k 会 I妻 定义 1 2 沿于文 2 1 其中 过程 B I d r 2 m t y p e M G s 会I m 1 3 表示用改进的 S e h mi d t 正交规范化方法 MGS方法 对 i 2作同解变形 使得 当 1 2 相容时 r l r a n k A r 2 一 r a n k r A T 一 1 B R r r2 是 正 交 规 范 行 向 量 组 4mw 不I 1 r a n k B 则t y p e 0 m 1 uD X 一 l 则 t y p e 1 当 1 1 ff 相容时 r 1 r a n k A r 0 t y p e 2 当 1 1 相容时 但 1 2 不相容时 r l r a n k A r 2 r a n k f 会 1 一 一 3 e 0时 1 2 i 多 解 i i t yp e t y p t y p e 1时 1 2 有唯一解 t y p e 2时 不存在而 1 2 无意义 t y p e 3时 取 值错误而使 1 2 无解 过程 1 3 求出 B所作的实数乘法次数不大于 巩 定义 1 2 称算法 尢 一 麟 为问题 1 2 的正交化行处理法大数法或大数法 甩 一 晒 1 B i r l r 2 t y p e M G s t 见 1 3 记 B 一 b i i 1 2 2 i f t y p e 2 I Xo 0 Xo R l f X 卅一X i 1 n e n I o 1 2 r i i 循 环 I X 一 解向 量 X 6 n 算法考虑了易读性 尚可优化 在 t y p e 2时记求解过程为 X 7 Y ur s r A Y 一 6 AX X 咒 咒 优 1 4 在 t y p e O且 x o o时 模块 中迭代格式应改为 X件 一X 6 一 n 件 X n 件 一0 1 2 r m1 有x 一 z b n 一 口 n 在用改进的S e h m i d t 正交规范化方法实现模块 时 一 晒 方 法 有 较 好 的 数 值 稳 定 性 过 程 1 4 中 实 数 乘 法 运 算 量为0 程 序 实现 时 可 对f 会 压 缩存储 算法兼备直接法和迭代法两者的优点 对 过 程 1 4 有 A x 6 且 c x 甘 t Y P e 2 甘 r a n k 会 r a n k 会 I 妻 因 为 B x d 与 1 2 同解 在 t y p e 2 时B 是正交规范化行向量组 B X B 暑b 口 i 一d 参见文 1 2 2 大 数法快速 并行 解法 按照 并行 解法 并行计 算机 一并 行算法 的模 式 用分治 策略 给出 7 r m一 晒 方法的并行解法 维普资讯 0 四川大学学报 自然科 学版 蕾 n尘 i V管 7 r 肛 一 脑 一 磁 语句 f o r e a c h s l q p a r a d o 表示对每一个问题 S施行同一指令序列 定义 2 1 称算法 G r为 1 2 的划分方法 f 记划分过程为 一 1 2 A I 5 3 一 r A L A1 1 X E x 1 q l q m 万A I 妻 口 I I l 2 I A 1 I A A的列分块划分 I X 1 I X d X的对座行分块划分 A 6 l m 一 G R AX 一 6 一AX l l q 2 i 程序实现时容易使分块负载平衡 对应于 1 2 有 I r i I I f I I I 口J 7 2 x 一 鱼 是 直 和 运 算 定义 2 2 称算法 一 M U 8 一 为 1 2 的正交化行处理大数法快速并行解法或大数法快速并行解法 A 6 7 2 m 一G R A X 6 l m q 见 2 1 r l 0 r 2 0 t y p e 一0 f o r e a c h l q p a r a d o K 口 1 a j K r 一 K K r 一 d 斗 1 2 IP 循环 b f o r e a c h s l q p a r a d o f 口 一 K b I 一b 汁 一 K b I I I 卢 I ll 卢 ll 卢 州II 一 I 卢 I 言 l 1 州 I I 0 t h e n i f 咒 一 1 t h e n r i r 1 1 e ls e 一 1 d f o r e a c h 1 4s q p a r a d o i f lI 卢斗 o t he n i 1 j 斗 一 ji e l s e i f b i l O 1 1 或者 1 2 矛盾 返回结束信息 m i X l 一 一 岔 口 Z l 维普资讯 币 期 杨本立 线性方程组大数法快速并行解法 6 2 9 t h e n i f n 1 t h e n t y p e 2 r e t u r n t y p e e l s e t ype 3 r e t u r n t ype i 0 1 2 一1 i 循环 完成 1 2 的 MGS同解变形 i i f r 1 r 2 一m t h e n t ype 1 1 2 唯一解 X o 0 X o 在 X o O 时应改写 f o r e a c h 1 g p a r a d o 一 b f x 一 x 是直和运算 x 为 1 2 的解向量 r e t d r n t ype X 报告 1 2 的解 结束 记求解过程为 t y p e X 丌矶 脑 一 AX 一 6 AX X m g 2 2 解法设计考虑了易读性 尚可优化和扩充功能 在模块 采用改进的 c n ml d t 正交规范化方法时过程 2 2 有较好的数值稳定性 4 ma x m F m q l 在 t ype 2 时过程 2 2 中对每一分块 s 的实数乘法运算 量为0 F m l q 1 当 A为大型稀疏矩阵时运算量远小于此 在给出X的选取方法后 丌甩 一 掀 一 解法可用于求解AX O的基础解系和确定 AX b的解结构 本 文方法亦可用于结构力学中用 大数法 求解的问题 定 理 2 对 过 程 2 2 有 A X 6 X C X 臼 ty p e 2 臼 ra n k ra n k i妻 证 明模块 是 1 2 的划分过程 模块 和 完成过程 1 3 等价于下面运算 I t yp e O In j 件 L f l e o i i 0 i i 0 当J9 汁 一 0 汁 i I I 部 0 I I 6 f 1 一 l 0 当J8 汁 一 0 且b 一 0 I 当卢 汁 一 0 但 0 1 i 0 1 2 船 一1 维普资讯 o U 四川大学学报 自然科学版 f 0 若 1 2 多解 l 1 若 1 2 唯一解 y p e 一 1 2 若 1 1 不 相 容 使 1 2 无 解 i 3 若 1 1 相容但 x取值不当使 1 2 元解 所以模块 和 完成 了 1 2 的同解变形过程 1 3 模块 等价于下面运算 t e 2 1 2 相容 Xo X f t D H 1一 卢 X i L 八 T 厶O l p f 1 1 2 霓一 1 x 一 一 霎 卢 一 鱼 霎 6I 卢 一 鱼 在 t y p e 2 时 由文 1 2 有关结论可知定理 2 1 成立 证毕 例 2 1 用 一 脑 一 解法求 1 2 其中 A I 明 一 6 一 一 1 求解过程模拟如下 1 分组存储 A m s l X1 一 x l z 2 了 2 X2 一 3 z 4 x T 0 3 X3 一 5 当 会 为 大 型 稀 疏 矩 阵 时 可 对 采 用 动 态 链 表 压 缩 存 储 2 正交规范化同解变形 初始 r l O Y 2 一O y I J 一nv Al I 一 f 1 q r6 1 2 一 1 2 A3 I O O n n O O 2 0 n 1 O O 弟 4 0罨 一一 L O O O u 1 O O O 1 1 O O 1 1 1 O 1 1 1 O l 1 1 nu O 1 1 O nu O 1 1 O 0 一 O O O O 0 一 O l 1 一 1 1 O O O 0 1 1 O O O u 一 1 1 1 O U O 1 1 O O U O o 一 1 1 1 一 o 一 1 1 1 一 O O 2 O O A O 1 O O C O r l L o 一 1 1 1 一 o O O n O 维普资讯 第 4 期 杨本立 线性方程组大数法快速并行解法 6 3 1 r 1 5 r 2 5 5 0 t y 1 e O 3 解向量 x 取 x ff一0 R x 一Qx i 口 6 一 亩f 卢 一 1 2 1 2 o 一1 1 2 o 1 2 一1 一 1 2 1 2 一 1 1 2 1 2 一 1 经验证 X 确为问题 1 2 的一个特解并且 一一1 满足 一XCX 可看出过程 2 2 的并行实现是容易 的 3 一 一 解法应用前景分析 对于线性代数方程组 无论是传统的串行迭代算法还是新兴的并行迭代算法 一些已发表的有效迭代算 法都是针对工程技术中某类特殊线性代数方程组的 7 噩一 凇 解法针对任意的问题 1 2 并且在 乒 时 可用于求解任意线性方程组 1 1 无疑有一定的理论价值 在用 7 c 一 麟 一 解法开发消息传递 MI MD并行迭代算法时 可对 A I 6 s 一1 2 q 分布存储 可用 各处理机并行完成 f o r e a c h s 1 q p a r a d o j 指令而用主机或者主机与各处理机协同完成其余指令 在 t y p e 2 时 需 要由 各处 理机向 主机 传递的 数据主要是K 实数 各专 箍 十 一 次 实 1 数 各t n l 一n 次 和x x 各1 次 需要主机向各处理机通信传递的数据主要是j r 实数 共专 钾 z 一 次 j9汁 实数 共 次 在 以一个 实数作 通信单位时其通信量为 O 7 l 7 r 一 麟 一 解法有较好的内在并行性 又因划分过程 能做到负载平衡 故其对应的并行算法有较为 理想的加速比和并行效率 参考文献 r 1 朱励 张玲 李方军 等 部分变量已定值的线性方程组的行处理法D 四川师范大学学报 2 0 0 0 2 3 1 6 8 6 9 2 曾宪雯 郝军 祁晓彬 等 线性代数方程组正交化行处理法 J I J I I 师范大学学报 自然科学版 1 9 9 9 2 2 3 2 6 5 2 6 8 Qu i c k ri VI aA I IM mA I II c I1 Me t h o d U一 1 L a r g e Nu mb e r s r S y s t 锄U L L i n e a r E q u a t i o n s y ANG Be n Li S t a f f Co l l e g e Ch i n a Ac a d e my o f En g i n e e r i n g Ph y s i c s S i c h u a n M i a n y a n g 6 2 1 9 0 0 Ch i n a A tya c t M a r k i n g u s e o f t he me t h o d b y h mi d t s o r t h o g o n a i z a t i o n wi t h n o r ma l i z a t i o n a n d t h e d i v i d i n g c o n q u e r i n g s t r a t e g y t h e a u t h o r p u t f o r wa r d a q u i c k p a r a l l e l me t h o d t o s o l v e a