基于Gram-Schmidt正交法的矩阵并行QR分解算法

qr分解 论文呢

第３１卷第３期

２０１佛山科学技术学院学报（自然科学版）ＪｏｕｒｎａｌｏｆＦｏｓｈａｎＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｖ０１．３１ＮＯ．３３年５月Ｍａｙ２０１３文章编号：１００８—０１７１（２０１３）０３—００４４—０４

基于Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交法的

矩阵并行ＱＲ分解算法

黄丽嫦，黄润

（佛山职业技术学院计算机系，广东佛山５２８１３７）

摘要：分析了线性无关向量组的Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化过程以及矩阵的ＱＲ分解原理。在多核架构的微机中，设计实现了一种基于Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交法的矩阵ＱＲ多核并行分解算法。新算法易于计算机编程实现，数值实验也验证了算法具有良好的并行性。

关键词：Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交法；ＱＲ分解；多核并行计算

中图分类号：０１５１．２１文献标志码：Ａ

矩阵的ＱＲ分解在数值代数中有着重要的应用，它为矩阵特征值的数值求解提供了理论依据，并且也是求解最小二乘问题、最优化问题和某些病态方程组的有效工具。ＱＲ分解的优点是具有良好的数值稳定性，无须像选主元策略那样进行某些行或列的交换；而缺点就是在分解过程中所产生的串行计算次数远高于Ｉ。Ｕ、Ｃｈｏｌｅｓｋｙ等其他矩阵分解，为此，研究并行ＱＲ分解算法有着重要的实用意义［１］。矩阵的ＱＲ分鳃通常有Ｈｏｕｓｅｈｏｌｄｅｒ变换、Ｇｉｖｅｎｓ变换及Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化三种实现方法，近年来，在机群高速网络环境中基于Ｇｉｖｅｎｓ变换的并行ＱＲ分解算法得到了很好地研究［２。４］。注意到目前的微机普遍具有多核架构计算环境，本文采用Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化的方法，在多核微机中设计实现了一种并行矩阵ＱＲ分解算法。

１Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化法及矩阵的ＱＲ分解原理

线性无关向量组的Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化过程

设口。，ａ：，…，‰是咒维欧氏空间中，”（，咒≤ｎ）个线性无关的向量，Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化过程就是求１．１取一组单位向量ｑ，，ｇｚ，…，ｇ。使得：

（１）口。，口２，…，‰张成的空间等于ｑ。，ｑ２，…，ｑ，。张成的空间，即ｓｐａｎ（乜】，ａ２，…，％）一ｓｐａｎ｛ｑｌ，ｑ２，…，ｑ，。｝；

（２）口，，口。，…婚。两两正交，即内积（ｑｉ，ｑｊ）一妻％孙一｛：’ｉ＿ｊ：’

＾一Ｉ（ｉ，Ｊ一１，２，…，，舱）。Ｉｕ，ｌ－Ｆ－Ｊ。

遵循上述条件，可得如下的Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交化过程［５］：

，厂：＿—一

（１）取ｇｉ一口－，化为单位向量有ｇ 一１ｒ爱兀，其中ＩＩｇ川ｚ一√蚤（ｇ ；）２为ｑ！的向量范数。

收稿日期：２０１３－０１—２６

基金项目：佛山职业技术学院校级科研基金资助项目（２０１１ＫＹ０１７）作者简介：黄丽嫦（１９６２一），女，广东中山人，佛山职业技术学院讲师。

qr分解 论文呢

第３期黄丽嫦等：基于Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交法的矩阵并行ＱＲ分解算法

（ｆ２）取ｑ；一＆！一卜崩¨ｇ－（卢㈡∈Ｒ）．从（ｑ－ ｑ：）一。可知卢；”一一湍一一（＆： ｑ．卜故ｑｉ—ｄ：一

ｐｒ”ｑｊ～ｆ秽－ｇ、÷…÷雕二，％一，（卢≯＿‘’．卢≯屯’，…，ｊ≥岸ｉ∈Ｒ）．同理．从（口：，ｑ．：）一ｌ乜．－（７ｉ）口！ 把ｑ；化为单氲向量 有ｑ：一可翻一：（３）取ｇｊ—ａ。＿Ｌ

ｏ，（ｇｚ婚！）一。，…，（％：一。饵！）一。可知雕一１）一一篙薯窘一一（％，．ｑ。），雕一！）一一÷瓮÷舅一一（％。ｑ！）。…，卢矬，一一石羔一一（％：，％一，），故ｇ上一‰一（％。，ｑ－）ｑ 一（‰，ｑｚ）ｇｚ一…一（“：，％一 ）吼卜 一‰一圣（‰，ｇ。）ｇ一，把“化为单位向量有吼：一可曩记。

１．２矩阵的ＱＲ分解原理

引理１设Ａ是九阶实（复）非奇异矩阵，则存在正交（酉）矩阵Ｑ与实（复）非奇异上三角矩阵Ｒ，使得

Ａ—ＱＲ

成立‘６ｊ。（１）

引理２设Ａ是，ｚ×Ⅲ（，胛＜，ｚ）实（复）矩阵，且其川个列线性无关，则Ａ有分解

Ａ—ＱＲ，

其中，Ｑ是门×，咒实（复）矩阵，且满足Ｑ丁Ｑ＝Ｉ或ＱＨＱ＝Ｉ，Ｒ是，咒阶实（复）非奇异上三角矩阵‘６｜。２基于Ｇ—Ｓ正交化的矩阵并行ＱＲ分解算法设计

设Ａ一（＆。，ｄ２，…，ｄ。）为门×，７２（７咒≤订）实矩阵，ｒａｎｋ（Ａ）一７”，且Ａ＝ＱＲ，其中Ｑ一（ｑ１，９２，…，‰）为列

●

Ｈ

●

ｎ

正交阵，尺一

●为，咒阶实非奇异上三角矩阵，可得如下向量方程组

ｎ吃；‰ｍ

』ａＧ：Ｉ一＝ｒ，．，ｌ：ｌ口ｑ。ｌ’＋ｒ：：口：，

ｌａ，，。一，．，。ｑ，＋，．：，。ｇ。

其中，ｑ，ｇ：∈Ｒ”（ｉ一１，２，…，７竹）；Ｖｉ≠歹，３（ｑ。，ｇ，）一０；，。十ｒ…口。。（２）ｄＪ一∑ｊ－ｉ（％ｇｉ）北，ｉ＝ｊ，

毒

从式（２）的第１个方程开始，取，．。。一｜１ａ。ｌｌ：，ｇ。一－‘ｘ１；然后以ｇ。代人式（２）中的第２个方程，求出，．Ⅲ，．：。，口：；如此类推，求出＿ｒ¨。，，．：。，…，‰，。和口…这种依照列方式顺序来求解月矩阵的方法往往具有数值稳定性差的缺点，主要原因是当ｄ，和以前的ｄｉ（ｉ＜歹）接近线性相关时，，‘，，也接近０，而用它作为分母去求ｇ，将会出现较大的误差，最终导致口。，口：，…，口，。失去了正交性。

为了增强数值稳定性，可以依照行方式顺序从式（２）中求解尺矩阵，即先求出式（２）中右边以第ｌ列，接着求出第２列，直至求出Ｑ、Ｒ矩阵为止。具体过程为：

（１）取“一ｌＩｄ。１１。，ｇ。一｝；

，１１

（２）在式（２）的第２～，咒个方程中分别施行与ｇ。的内积计算，根据正交性的条件有ｒｌｊ一（ｄ，，ｑ。）（Ｊ一２，３，…，７竹）；

（３）为式（２）的第２～，，ｚ个方程消去ｇ。分量（与口。的平行分量），得到如下的方程组

qr分解 论文呢

佛山科学技术学院学报ｆ自然科学版）第３１卷

｛ａ；¨一ｒ！！口：

＜口；¨一ｒ？。口：寸一，‘？３９３．（３）

ｌａ碧’＝ｒ２ｍｑ！＿＿， ¨。ｇ３＋…＋，。。‰。

其ｅｐ，ａ；¨一口，～口１ｒ１，（歹一２，３，…，７咒）。

（４）类似过程（１）～（３），直至求出Ｏ、Ｒ矩阵为止。

在式（２）的Ｒ矩阵求解过程中，行方式顺序比列方式顺序具有更好的数值稳定性，这是因为在计算ｇ，。时，‰向量已被更新了，咒一１次，各次的更新分别对ａ。，ａ：，…，％一。的平行分量进行消除，因而由口。，ｄｚ，．”，‰接近线性相关所引起的舍入误差将会很好地消除。

综上所述，可设计如下的多核Ｇ—Ｓ正交化的矩阵并行ＱＲ分解算法：

输入：矩阵Ａ。。（，咒≤门）；

输出：正交阵ａ。，。和非奇异上三角矩阵Ｒ。。。。

算法描述：（设ＣＰＵ的核数为Ｐ）

ｆｏｒ（ｉ一１，ｊ＜一７咒；ｉ＋＋）

｛

厂：＿

（１）多核并行计算“一ＩＩ嘶ｌｌ。一＾／∑ｄ磊，ｑ？一嘶／靠。在核１中计算：ＳＵｍｌ＝ｄ备＋口玉＋…＋ｄｊ。，Ａ—ｃｅｉｌ（参）是求不小于（詈）的最小整数；在核２中计算：ｓｕｍ２一ｄ备＋船＋¨＋…＋娘，Ｂ—ｃｅｉｌ７７”）＋１，ｃ一２＊ｃｅｉｌ（詈）；在核户中计算：ｓｕｍｐ＝ａ氮＋ｄ曼扎ｉ＋…＋最，ｘ一（户一１）＊ｃｅｉｌ（芳）＋１，ｙ＝以。核１～核户并行计算，待所有核计算完毕后，通过双向管道把各核的计算结果ｓｕｍｌ，ｓｕｍ２，…，ｓｕｍｐ汇总到任一核中，并计算出“一１１啦ＩＩ。一＾／∑口磊一“面司Ｒｉ面西干ｉ干面和ｇｉ一口ｉ／“。广：＿－一

（２）多核并行计算～＝（ａｊ，ｑｉ）＝√ｄ１脚ｑ。＋ｄ２，ｑ２。＋…＋口。』ｑ。。（歹一ｉ＋１，ｉ＋２，…，７规）。在核１中计算：“州一（ａｉ＋ｌ，ｑｉ）ｒｉ，ｉ＋２（０ｌｉ＋２，ｑｉ），…，ｎ一一（劬，ｇ，），Ａ＝ｃｅｉｌ（＿ｍ－－矿ｉ）；在核２中计算：ｎＢ一（％，ｇｉ）∥加＋ｔ一（Ｏ＇Ｂ＋１，ｑｉ），…，，一ｉｃ一（％，ｇｉ）；Ｂ—ｃｅｉｌ（ｍ＿厂－－ｉ）＋１，ｃ一２＊ｃｅｉｌ（ｍ＿厂－－ｉ）；在核户中计算：ｒ：ｘ一（口ｘ，ｇ。），“ｘ＋，＿（颤¨，¨，…∽ｙ＿。ｎｇｆ）Ⅸ叫户＿１）＊ｃｅｉｌ（等），ｙ＝ｍ。

（３）多核并行计算ｄ，一ａｊ－－ｑ以，（歹一２，３，…，优）。与（１）、（２）类似，可把ａｊ－一－ａｊ－－ｑｍ，（歹一２，３，…，７７ｚ）按计算载荷平均的原则分配到核１～核Ｐ中并行计算。

｝

３算法的性ｚ月，．匕ｌａ测试

在ＩｎｔｅｌＸｅｏｎＥ５４５０四核３．０ＧＨｚＣＰＵ（每个核心的一级缓存各由３２ＫＢ数据缓存和３２ＫＢ指令缓存组成，二级缓存容量为１２ＭＢ，）、ＫｉｎｇＳｔｏｎＤＤＲ３１３３３ＭＨＺ４ＧＢ内存及ＲｅｄＨａｔＥｎｔｅｒｐｒｉｓｅＬｉｎｕｘ６．１操作系统的环境中对上述算法进行了模拟，程序采用ＯｐｅｎＭＰ和Ｃ＋＋语言进行编写呼８：。

为了节省存储空问，式（１）中矩阵Ａ按如下规则产生踟

Ｉ以，ｉ一歹，

Ａ一（口ｉ，）。×７ｌ—ｌｌ下一≠７。ｉ＋ｉ．，．ｉ，Ｊ一０，１，…，扎一１。

实验结果如表１所示，实验数据表明，四核Ｇ—Ｓ正交化的矩阵ＱＲ并行分解比单核串行分解在运算速度上提高了近６０％。

qr分解 论文呢

期黄丽嫦等：基于Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交法的矩阵并行ＱＲ分解算法

表］单核Ｇ—Ｓ正交化的矩阵ＱＲ串行分解与四核Ｇ—Ｓ正交化的矩阵ＱＲ并行分解的耗时比较

４结语

本文在ＰＣ多核微机上设计实现了一种基于Ｇｒａｍ—Ｓｃｈｍｉｄｔ正交法的矩阵ＱＲ多核并行分解算法，新算法具有易于实现和并行性高的特点，理论分析及相关实验均表明了它的有效性。

参考文献：

［１］张宝琳．数值并行计算原理与方法［Ｍ］．北京：国防工业出版社．１９９９：９３．

Ｅ２］张艳，孙世新．网络并行计算中矩阵ＱＲ分解的并行算法［Ｊ］．计算机应用，２０００，２０（１０）：２９—３２．

［３］陈政洪，郁松年．一个基于ＱＲ分解的并行原一对偶内点算法［Ｊ］．应用科学学报，２００４，２２（４）：５４９—５５２．

［４］陈一呜，杨爱民．肖晓丹，等．机群系统中矩阵的并行ＱＲ分解算法［Ｊ］．燕山大学学报，２００７，３１（３）：２２５—２２８．［５］罗家洪．矩阵分析引论［Ｍ］．３版．广州：华南理工大学出版社，２００４：４０．

［６］程云鹏．矩阵论［Ｍ］．３版．西安：西北工业大学出版社，２００１：２０３．

［７］周伟明．多核计算与程序设计［Ｍ］．武汉：华中科技大学出版社，２００９：７５．

［８］武汉大学多核架构与编程课程组．多核架构与编程技术［Ｍ］．武汉：武汉大学出版社，２０１０：２３．

［９］尚月强．局域网上求解线性方程组的～种并行Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代算法研究［Ｊ］．计算机应用与软件，２００８，２５（９）

２４５—２４７．

【责任编辑：王桂珍ｆｏｓｈａｎｗｇｚｈ＠１６３．ｃｏｍｌ

ＴｈｅＧｒａｍ—－ＳｃｈｍｉｄｔｂａｓｅｄｏｒｔｈｏｇｏｎａｌｍｅｔｈｏｄｆｏｒｍａｔｒｉｘｅｓｐａｒａｌｌｅｌＱＲｄｅｃｏｍｐｏｓｉｔｉｏｎａｌｇｏｒｉｔｈｍ

ＨＵＡＮＧＬｉ—ｃｈａｎｇ，ＨＵＡＮＧＲｕｎ

（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒ，ＦｏｓｈａｎＰｏｌｙｔｅｃｈｎｉｃ，Ｆｏｓｈａｎ５２８１３７，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅａｎａｌｙｚｅｄｔｈｅｏｒｔｈｏｇｏｎａｌｉｚａｔｉｏｎｐｒｏｃｅｄｕｒｅｏｆｌｉｎｅａｒｉｎｄｅｐｅｎｄｅｎｔｖｅｃｔｏｒｇｒｏｕｐｓａｎｄｔｈｅＱＲｄｅｃｏｍｐｏｓｉｔｉｏｎｐｒｉｎｃｉｐｌｅｏｆｍａｔｒｉｘｅｓａｎｄｄｅｓｉｇｎｅｄａＧｒａｍ—ＳｃｈｍｉｄｔｂａｓｅｄｏｒｔｈｏｇｏｎａｌｍｅｔｈｏｄｆｏｒｍａｔｒｉｘｅｓｐａｒａｌｌｅｌＱＲｄｅｃｏｍｐｏｓｉｔｉｏｎａｌｇｏｒｉｔｈｍ．Ｔｈｅａｌｇｏｒｉｔｈｍｐｒｅｓｅｎｔｅｄｉｎｔｈｉｓｐａｐｅｒｐｒｏｖｅｄｔｏｂｅｅａｓｙｔｏｉｍｐｌｅｍｅｎｔｃｏｍｐｕｔｅｒｐｒｏｇｒａｍｍｉｎｇａｎｄｈａｖｅｇｏｏｄｐａｒａｌｌｅｌｐｒｏｐｅｒｔｙ．Ｋｅｙｗｏｒｄｓ：Ｇｒａｍ—Ｓｃｈｍｉｄｔｏｒｔｈｏｇｏｎａｌｍｅｔｈｏｄ；ＱＲｄｅｃｏｍｐｏｓｉｔｉｏｎ；ｍｕｌｔｉ—ｃｏｒｅｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍ●

qr分解 论文呢

基于Gram-Schmidt正交法的矩阵并行QR分解算法作者：

作者单位：

刊名：

英文刊名：

年，卷(期)：黄丽嫦， 黄润， HUANG Li-chang， HUANG Run佛山职业技术学院计算机系,广东佛山,528137佛山科学技术学院学报（自然科学版）Journal of Foshan University(Natural Science Edition)2013,31(3)

1.张宝琳 数值并行计算原理与方法 1999

2.张艳.孙世新 网络并行计算中矩阵QR分解的并行算法 2000(10)

3.陈政洪.郁松年 一个基于QR分解的并行原-对偶内点算法 2004(04)

4.陈一鸣.杨爱民.肖晓丹 机群系统中矩阵的并行QR分解算法 2007(03)

5.罗家洪 矩阵分析引论 2004

6.程云鹏 矩阵论 2001

7.周伟明 多核计算与程序设计 2009

8.武汉大学多核架构与编程课程组 多核架构与编程技术 2010

9.尚月强 局域网上求解线性方程组的一种并行Gauss-Seidel迭代算法研究 2008(09)

本文链接：http://www.77cn.com.cn/Periodical_fskxjsxyxb201303010.aspx

本文来源：https://www.bwwdw.com/article/yndi.html