并行DECELL方法计算矩阵广义逆

由以上表格可看出，并行显然比串行快，而且规模越大计算效果越好．有条件的话，适当 增加处理器可以使得加速比增大，但是效率不一定高．
［参考文献］
Ｂｅｎ—Ｉｓｒａｅｌ Ａ，Ｇｒｅｖｉｌｌｅ Ｔ Ｎ Ｅ．Ｇｅｎｅｒａｌｉｚｅｄ Ｉｎｖｅｒｓｅ：Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ】．Ｎｅｗ Ｙｏｒｋ：Ｊｈｏｎ Ｗｉｌｅｙ，１９７４． 陈国良．并行计算：结构·算法·编程［Ｍ】，北京：高等教育出版社，１９９９ 都志辉．高性能计算并行编程技术一ＭＰＩ并行程序设计【Ｍ］．北京：清华大学出版社，２００１． Ｄｅｃｅｌｌ．Ａｎ ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｃａｌｅｙ—Ｈａｍｉｌｔｏｎ ｔｈｅｏｒｅｍ ｔｏ ｇｅｎｅｒａｌｉｚｅｄ ｍａｔｒｉｘ ｉｎｖｅｒｓｅ［Ｊ］．ＳＩＡＭ Ｒｅｖｉｅｗ，１９６５，７
Ｂ％＋ｌ＝颤ｊ—ＡＴＡＢ七， ｋ＝０，…，ｒ一１，
（１）
６％＋１＝ｔｒ（ＡＴＡＢ％＋１）／（岛＋１）， 忌＝０，…，ｒ一１
（２）
其中，ｔｒ（Ａ）表示Ａ的迹．从而（证明见参考文献［４】）
Ａ十：Ｂｒ．ＡＴ
（３）
辞
１ 并行Ｄｅｃｅｌｌ算法
本文在Ｄｅｃｅｌｌ原始算法的基础上，将原来的串行算法通过矩阵乘法的并行化以加快计 算速度，从而提高计算效率．
ｅｎｄｆｏｒ
ｅｎｄｆｏｒ
（３）ｆｏｒ ｋ＝Ｏ ｔｏ ｎｐｄｉｍ一１ ｄｏ
ｆｏｒ ａｌｌ Ｐｉ Ｊ ｐａｒ—ｄｏ
（ｉ）Ｃｉ，Ｊ＝ｃｔ，ｊ＋Ａｔ，Ｊ木Ｂｉ，Ｊ （ｉｉ）Ａｉ，Ｊ乍Ａｉ，ｏ＋１）。。ｄ（ｎｐｄｉｍ） （ｉｉｉ）Ｂｔ，Ｊ仁Ｂ（件１）。。ｄ（ｎｐｄｉｍ），ｊ
ｅｎｄｆｏｒ
ｅｎｄｆｏｒ
Ｅｎｄ
Ａｌｇｏｒｉｔｈｍ ３求迹并行算法（Ｔｒａｃｅ（ｎｌｏｃａｌ，丰ｃ））
摘要：将Ｄｅｃｅｌｌ算法与ＭＰＩ并行系统进行有效结合，用于计算大规模矩阵的ＭＰ广义逆．给出了算法设计 方案；讨论了在ＭＰＩ环境下的程序执行；并在ＰＣ机集群系统上实现．给出了关于并行加速比及效率的数值 结果． 关键词：并行计算；广义逆；ＭＰＩ环境 中图分类号：０２４１．６ 文献标识码：Ａ
０引 言
近年来，矩阵广义逆【１】已被应用于马尔可夫链、多元统计、网络理论等领域，处理的数 据规模也越来越大，经常导致计算时间超长．另外，大规模并行计算［２］已成为研究科学和工 程技术问题的一种崭新的手段．ＭＰＩ则是目前最重要的并行编程工具【３］’它具有移植性好、 功能强大、效率高等优点，在短短的几年内迅速普及，成为并行编程模式的标准．本文正是 将二者结合，讨论一种求Ｍｏｏｒｅ．Ｐｅｎｒｏｓｅ广义逆的并行算法．
ＣＨＥＮ Ｇｕｏ－ｌｉａｎ９１
（１．Ｄｅｐａｒｔｍｅｎｔ ０，Ｍａｔｈｅｍａｔｉｃｓ，Ｅａｓｔ Ｃｈｉｎａ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００６２，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅ—
ｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｃｈａｎｇｓｈａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈｕｎａｎ ４１００７６，Ｃｈｉｎａ）
第４期
至垒垒垒篁！！旦
华东师范大学学报（自然科学版）
Ｎｏ．４
！呈坚！呈垒！竺！曼塑！篁垒！望垒墼窒！尘塑望坠！塑望！堑』堕墅曼！型曼！丝呈呈竺２墼些；！！！量
文章编号：１０００—５６４１（２００５）０４—０００１—０５
并行ＤＥＣＥＬＬ方法计算矩阵广义逆
丰静１，２
陈果良１
（１．华东师范大学数学系，上海２０００６２； ２．长沙理工大学数学与计算科学学院，湖南长沙４１００７６）
５２６—５２８．
【５】Ｚｉｅｌｋｅ Ｇ．Ｒｅｐｏｒｔ ｏｎ ｔｅｓｔ ｍａｔｒｉｘ ｆｏｒ ｇｅｎｅｒａｌｉｚｅｄ ｉｎｖｅｒｓｅｓ［Ｊ］．Ｃｏｍｐｕｔｉｎｇ，１９８６，３６：１０５—１６２
ＤＥＣＥＬＬ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ａ Ｇｅｎｅｒａｌｉｚｅｄ Ｍａｔｒｉｘ Ｉｎｖｅｒｓｅ
ＦＥＮＧ Ｊｉｎ９１·２
定义０．１设矩阵Ａ∈Ｃｍ黼，若存在Ｘ∈ｃ—ｍ，满足
ＡｘＡ＝Ａ， ＸＡｘ＝Ｘ， （ＡＸ）＋＝Ａｘ， （ＸＡ）４＝ＸＡ
则称ｘ为Ａ的Ｍｏｏｒｅ－Ｐｅｎｒｏｓｅ广义逆，简称ＭＰ逆，记作Ａ十． Ｄｅｃｅｌｌ算法是计算ＭＰ逆Ａｔ的一种有限算法［２】，其原始形式如下： 设Ａ∈ｃ≯×”，Ｂｔ∈Ｃ“×”，５ｉ∈Ｃ（ｉ＝０，…，ｒ），令Ｂｏ＝０，６０＝１，
ｅｎｄｆｏｒ
ＭＰＩＲｅｄｕｃｅ（ｍｙｔｒ，ＭＰＩＳＵＭ，０，ｔｒ） ＭＰＩＢｃａｓｔ（ｔｒ，０） ｊ：广播打
ｅｎｄｆｏｒ
Ｅｎｄ
ｊｃ求和归约ｒｎｙｔｒ至打
２数值结果
万方数据
第４期
丰静，等：并行ＤＥＣＥＬＬ方法计算矩阵广义逆
５
由于硬件条件的限制，我们仅使用了４台Ｐ１１４００ＭＨｚ／６４Ｍ内存的Ｐｃ机，安装了Ｒｅｄ Ｈａｔ７．３版Ｌｉｎｕｘ操作系统和ＭＰＩＣＨ一１．２．５并行环境后，组成自适应局域网并行系统．鉴于矩 阵规模较大，采用的实验矩阵以０或１为元素【５】．
ｅｎｄｆｏｒ
ｅｎｄｆｏｒ
ｅｎｄｆｏｒ
ｅｎｄｆｏｒ
ｆｏｒ ｐｉ－－－－Ｏ ｔｏ ｎｐｄｉｍ一１ ｆｏｒ ｐｊ＝０ ｔｏ ｎｐｄｉｍ一１ ｄｏ ｈ＝ｐｉ，ｎｐｄｉｍ＋ｐｊ ｆｏｒ ｉ＝０ ｔｏ ｎｌｏｃａｆ一１ ｆｏｒ｛＝０ ｔｏ ｎｌｏｃａｌ一１ ｄｏ
ｄａｔａ—ａｔ（ｈ）ｂ ａｔ［（ｐｉ＊ｎｌｏｃａｌ＋ｉ），ｎ＋ｐｊ，ｎｌｏｃａｌ“】
ｆｏｒ ｋ＝１，…，ｒ
６一ｔｒ（Ｃ、 Ｂ一６Ｉ—ｃ Ｃ—ＤＢ
艿一ｔｒ（Ｃ）／ｒ：
最后计算一Ｂｈ＂．
Ｓｔｅｐ３结果输出 各进程的最后结果由０处理器收集并打印，提示计算成功．
万方数据
第４期
丰静，等：并行ＤＥＣＥＬＬ方法计算矩阵广义逆
３
１．３ 具体串并行算法 Ａｌｇｏｒｉｔｈｍ １并行数据分块算法（ｓｕｂｂｌｏｃｋ．Ｃ）
Ｂｅｇｉｎ
（１）ｒｅａｄ ｆｉｌｅ ｄａｔａ—ａ ｄｏ
ａ［ｉ】一Ａ ａｔ［ｉ］一ＡＴ
（２）ｆｏｒ ｐｉ＝Ｏ ｔｏ ｎｐｄｉｍ一１ ｆｏｒ ｐｊ＝Ｏ ｔｏ ｎｐｄｉｍ一１ ｄｏ ｈ＝ｐｉ＊ｎｐｄｉｍ＋ｐｊ
ｆｏｒ ｉ＝０ ｔｏ ｎｌｏｃａｌ一１
ｆｏｒ ｊ＝０ ｔｏ ｎｌｏｃａｌ－１ ｄｏ
ｄａｔａ—ａ（ｈ）÷一ａ［（ｐｉ爿ｃ礼ｆｏｃｏ？＋ｉ）木ｎ＋ｐｊ木礼ｆＤｃｏｆ＋ｊ］
模式一串行（０处理器） 输入一文件ｄａｔａ—ａ 输出一文件ｄａｔａ—ｏ丰及文件ｄａｔａ—ａｔ＊（算法中写为ｄａｔａ—ａ（ｈ）及ｄａｔａ－ａｔ（ｈ）） 描述一将Ａ矩阵从文件ｄａｔａ—ｏ读取后存于数组ａ，进行转置后存于数组ａｔ．同时，对数 组ａ及ａｔ进行ｎｐｄｉｍ×ｎｐｄｉｍ行列分块，转存人新建文件ｄａｔａ—ｎ｝及ｄａｔａ—ｏ抓
模式一并行（所有处理器） 输入一矩阵ｃ的分块 输出一矩阵ｃ的迹 描述一选取包含矩阵Ｃ主对角线的小块Ｃ％，％（对应一个处理器），求得它的迹ｍｙｔｒ后 累加归约到０处理器上的打，即为Ｃ的迹．
Ｂｅｇｉｎ
ｆｏｒ ａｌｌ Ｐｊ，Ｊ ｐａｒ—ｄｏ ｍｙｔｒ＝０．０
ｆｏｒ ｉ＝０ ｔｏ ｎｌｏｃａ２ ｄｏ
ｍｙｔｒ＝ｍｙｔｒ＋ｃ［ｉ，ｎｌｏｃａｌ＋ｉ］
（７）
（叫＝譬＝（竽，。）
㈣
１．２步骤
设开辟ｎｐｅｓ个并行处理器，编号分别为０…．，ｎｐｅｓ一１．
Ｓｔｅｐｌ数据准备 １）将矩阵Ａ的秩ｒ、维数凡及加边矩阵Ａ存于０处理器上的文件ｄａｔａ—ａ中；
块（２ｎ）ｐ０ｄｉ处ｍ＝理俪器），串存行为运文行件ｓｄｕａｂｔａｂ—ｌｏｎｃ木ｋ． 及ｃ文程件序ｄａ将 ｔａＡ—矩ａｔ阵＊（及木其 表转 示各置处进理行器ｎ编ｐｄ号ｉｍ）× ；ｎｐｄｉｍ分
ｅｎｄｆｏｒ
ｅｎｄ士ｏｒ
ｅｎｄｆｏｒ
ｅｎｄｆｏｒ
Ｅｎｄ
Ａｌｇｏｒｉｔｈｍ ２ Ｃａｎｎｏｎ ９｝｛：行算法［２］（Ｃａｎｎｏｎ（ｎｌｏｃａｌ，木ｏ，柏，木ｃ））
模式～并行（所有处理器） 输入一矩阵Ａ，Ｂ 输出一矩阵Ｃ，Ｃ＝Ａ｝Ｂ 描述一＋ｎ，丰６，木ｃ为指向ｄｏｕｂｌｅ型数据的指针，ｎｌｏｃａｌ为各小块矩阵维数．假定矩 阵Ａ和Ｂ分成ｎｐｅｓ （ｎｐｅｓ为开辟的处理器数）Ａｔ，Ｊ与Ｂｉ，ｊ（ｏ≤ｔ，Ｊ≤ｎｐｄｉｍ一１），处理器 排成ｎｐｄｉｍ×ｎｐｄｉｍ的方阵，Ｐ“，表示位于（ｉ，Ｊ）的小块矩阵对应的并行进程，符号“｛＝”表 示移位．为方便解释，不妨假设将矩阵Ａ和Ｂ进行３×３分块，则其初始状态如下图，各处理
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｔｒｉｅｄ ｔｏ ｃｏｍｂｉｎｅ Ｄｅｃｅｌｌ ｍｅｔｈｏｄ ａｎｄ ｔｈｅ ＭＰＩ ｓｙｓｔｅｍ ｔｏ ｃａｌｃｕｌａｔｅ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ｉｎｖｅｒｓｅ ｏｆ ｍａｔｒｉｃｅｓ ｏｆ ｌａｒｇｅ ｄｉｍｅｎｓｉｏｎ．Ｎｅｗ ａｌｇｏｒｉｔｈｍ ｗａｓ ｇｉｖｅｎ，ａｎｄ ｉｔｓ ｒｅａｌｉｚａｔｉｏｎ ｏｎ ａ ＰＣ ｌｏｃａｌ ｎｅｔｗｏｒｋ ｓｙｓｔｅｍ ｗａｓ ｄｅｓｃｒｉｂｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗｅｄ ｔｈａｔ ｔｈｅ ｓｐｅｅｄ ａｎｄ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｕｃｈ ｂｅｔｔｅｒ ｔｈａｎ ｃｏｍｍｏｎ ｓｅｒｉａｌ ａｌｇｏｒｉｔｈｍｓ． Ｋｅｙ ｗｏｒｄｓ：ｐａｒａｌｌｅｌ ｃｏｍｐｕｔｉｎｇ；ｇｅｎｅｒａｌｉｚｅｄ ｉｎｖｅｒｓｅ；ＭＰＩ ｓｙｓｔｅｍ
万方数据
３）开辟并行处理器，由０处理器读取文件ｄａｔａ—ｏ＋及文件ｄａｔａ—ａｔ，，将各分块发送至其他 处理器；广播ｎｌｏｃａｌ（ｎｌｏｃａｌ＝ｎ／ｎｐｄｉｍ）及ｒ． Ｓｔｅｐ ２并行计算
１）采用Ｃａｎｎｏｎ算法并行计算ＡＴＡ，进行初始赋值，
Ｂ。Ｊ， Ｃ．ＡＴＡ． Ｄ。ＡＴＡ：
２）利用Ｃａｎｎｏｎ算法进行主体循环计算，
收稿日期：２００３—０８ 基金项目：国家自然科学基金（１０３７１０４４）；上海市基础研究重点项目ｆ０４ＪＣｌ４０３１）；上海市重点学科建设项目 作者简介：丰静（１９７８－），女，硕士．