（计算数学专业论文）一些结构矩阵的快速算法.pdf

摘要 本文主要研究一些特殊结构矩阵的快速算法首先，我们提出了关于广义中 心对称矩阵和广义中心厄米特矩阵的矩阵一向量乘积的快速算法；其次，提出了 关于广义中心对称矩阵和广义中心厄米特矩阵的矩阵矩阵乘积的传统的快速算 法；最后提出了关于广义中心对称矩阵和广义中心厄米特矩阵的矩阵矩阵乘积 的块算法与传统的算法进行了比较，我们算法无论在计算量还是存储量方面， 都能确保相当的节省 本论文共分五章 第一章为引言主要介绍了本论文研究问题的主要背景、研究内容和创新 第二章主要介绍了一些在本论文中要用到的基本概念及符号表示 第三章建立了广义中心对称( 厄米特) 矩阵一向量乘积的快速算法并对所建 立的算法进行了分析。说明了新建立的算法在计算量和存储量方面比传统的算法 有很大的改进 第四章建立了广义中心对称( 厄米特) 矩阵一矩阵乘积的传统的快速算法在 计算量和存储量方面也有类似的改进 第五章建立了广义中心对称( 厄米特) 矩阵一矩阵乘积的块算法在此算法 中采用了分块的矩阵乘法，并且在算法中把矩阵的乘法转化成矩阵的加减法计 算，从而提高了计算的速度，节省了不少的内存 关键词：广义中心对称矩阵：广义中心厄米特矩阵：广义斜中心对称矩阵；快速 算法；目m i l 算法 s o m ef a s ta l g o r j t h m sf o rc c r t a i nc l a s s e so fs t 九i c t u r e dm a t r i c e sa r ec o n s i d e r c di n t b i st h e s i s f i r s t ly ，w ep m p o v e r a if 弱ta l g o r i t h m sf o rc o m p u t j n gt h ep m d u c t so f m a t r i x v e c t o rw j t hag e n e r a l i z e dc e n t m s y m m e t r i cm a t r i x ( o rg e n e r a l j z e dc e n t r o h e 哪i t i a nm a t r i x ) s e c o n d ly w ed e v e l o ps o m ec o n v e n t i o n a lf a s ta j g o r i t h m sf o r c o m p u t i n gt l l ep r o d u c t so fm a x m a 倒b 【w i t hag c n e r a l i z e dc e n t r o s y m m e t r j cm a t r i x ( o rg e n e r a l i z c dc c n t r o h e 册i t i 卸m a t 血) a tl a s t ，w ei n v e s t i g a t et h eb l o c ka l g o r i t h m s f o rc o m p u t i n gt l l ep 刚u d so fm a t r i x m a t r i xw i t hag e n e r a l i z e dc e n t r o s y m m e t r i c m a 砸x ( 0 rg e n e r a l i z e dc e n t m h e 彻i t i a nm a t x ) ( = o m p a n gw i t h t h ec o n v e n t j o n a l a l g o t h m s ，o u ra l g o r i t b m se n s u r es j 印m 啪ts a v j n 擎j nc o m p u t a t i o n a lc o s t s 卸d m e m o r yu n i t s n j s p a p e r c o n s i s t so ff i v ec h a p t e r s h lt h ef i r s tc h a p t e r ，w em a i n l yi n t r o d u c et h eb a c k g r o u n d ，i h em a i nc o n t e n t s 柚d t l i eo r i 百n a l i t i e so fc h et h e s i s i i lt h es c c o n dc h a p t e r ，w eb r i e n y 北v i e ws o m eb 硒j cd e f i n j t i o n sa n dn o t a t i o n w h j c hw i l lb eu s e di nt h et h e s i s i i lt h et h j r dc h a p t e r ，s e v e r a la 1 9 0 r i t h m sf b rc o m p u t i n gt h ep r o d u c t so fm a t r i x 。 v e d o rw i t hac c n t r o s y m m e t r i cm a t r i x ( o rac c n t r o h e 皿i t i 卸m a t r i x ) a r ep r o p o s e d w e g i v es o m ed e t a j i e da n a l y s i so ft h e s ea l g o r i t l l n l s ，c o m p a r i n gw j t h t h ec o m p u t i o n a l c o s t s 卸ds t o r a g e so f t h e n v e n t i o n a la l g o r i t l l i l l s ，o u ra l g o r i t h m sc a ns a v ea l o t i nt h ef o u n hc h a p t e r ，w eo f f c r c d s e v e r a lc o n v e n t i o n a lf a s ta l g o r i t h m sf o r c o m p u t i n gt h ep m d u c t so fm a t r i x - m a t r i ) 【w i t hag e n e r a l j z e dc c n t r o s y m m e t r i cm a t r j x ( o rag c n e r a l i z e dc e n t m h e 姗i t i a nm a 啊x ) t h o s ea l g o r i l h m sh a v et h es i m 柚a r 轴v i n g s i i lt h ei a s tc h a p t e lw ep r o p o s e daf c wb l o c ka i g o r i t h m sf o rc o m p u t i n gt h e p r o d u d s o fm a t r i x m a t r i xw i mag e n e m l i z e dc e n t r o s y m m e t r i cm a t r i x( o r a g e n e r a l i z e dc c n t r o h e 册i t i 柚m a t r i x ) b yu s i n gb l o c k e dm 枷xp r o d u c tw h e r c m e m u l t j p i i c a t i v eo p e r a t i o n sa j 己t r a n s f o 册e d i n t o r e l a t i v ea d d i t i v e o p e r a t i o n s ， o u r a l g o r i t h m se n s u r et h ei m p r o v e m e n to f m p u t a t j o n a ls p e e d a i l ds a v i n go fs t o r a g e n k e yw o r d s ：g e n e r a l i z e dc e n t r o s y m m e t cm a t c e s ；( k n e r a i i z e d c e n t m h e m i t i a n m a t c 嚣； g e n e n l i z e d s k e wc e n t m s y m m e t r i c m a t c 髓；f a s ta i g o r i t h m s ； s t m s s e na l g o r i t h m s i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：砖噢专 日期：d 7 年上月加日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 曲乓丢 导师签名： 割冲舂 日期：c 7 年s 月；日日期：p 年s 月；日 日期0 7 年岁月加日 1 1 背景 第一章引言帚一早，ii 在当代的许多科学与工程问题中都会遇到大规模的矩阵计算问题，例如，在 计算信号复原问题时，离散的方程所表现的大多是一个大规模的线性方程组目 前许多的信号复原问题，大多是在对原问题的边界加以一些特殊的限制后来进行 研究这些限制使离散问题表现为具有某种特殊结构和某些特殊性质的线性方程 组( 例如应用反卷积技术到信号复原问题，就会出现系数矩阵为循环矩阵、 而印批：矩阵、而印，比+ 月口月妇，矩阵等结构矩阵见参考文献 3 6 、 3 8 ) 虽然 以上几类矩阵已有一些快速算法，但对于其他许多的已在信号复原问题中出现的 结构矩阵( 例如应用小波技术处理信号复原问题时，就会出现诸如中心对称矩阵、 中心厄米特矩阵等结构矩阵见参考文献 1 、 3 8 ) ，至今还没有找到有效的快 速算法因此，为了减少计算量和节省内存，设计快速的算法( 当讨论的结构矩 阵为非奇异矩阵时) 或有效的最小二乘解算法( 当讨论的结构矩阵是奇异或超定 矩阵时) ，尤其显得十分重要目前有关这方面的研究尚属起步阶段，至今只有极 少数的论文所以，对结构矩阵的研究以及建立相关的快速算法是很有研究价值 的 对于一些超大规模的计算问题，我们就不得不研究并行算法了例如，在有 些信号复原问题中，如天气预报、大地石油勘探等问题，所表现的方程组通常是 超大规模的( 上百万阶) ，串行的算法根本就不能解决这些实际问题目前，对于 有些实际问题，已有一些实用的并行算法但是对有些问题( 如图象复原问题 等) ，由于起步阶段较晚，加上计算方面的困难，目前的研究主要集中在中、小 规模的信号复原问题，而对大规模的信号复原问题和相关的超大规模计算问题 还很少有涉及然而，在实际问题中有时常会碰到这些计算问题因此，为了解 决这些超大规模问题的计算问题，很有必要进一步研究他们的并行算法 在研究结构矩阵线性方程组的求解的时候有时会遇到矩阵的乘积因此，矩 阵乘积也是我们要解决的问题目前，国内外对结构矩阵的乘积问题的研究也有 不少的研究，同时也出现了很多相关的算法，并且都在不同的程度上达到了我们 设计快速算法的最终目的减少计算量、节省内存，见参考文献 2 、 3 但 是至今还没有找到最优化的快速算法，所以其中还有许多的工作值得继续深入 研究 线性方程组的求解问题是矩阵计算中的核心部分，许多科学与工程问题最终 会归结到线性方程组的求解目前，对于一些结构线性方程组，如何进行迭代改 进直是国内外一个比较活跃的研究领域，研究的主要目的是如何利用矩阵的 特殊结构来减少计算量和存储量，从而可以节省计算的时间和计算需要的费用， 主要结果见参考文献【2 】、【3 】、【3 5 】、【4 7 】 另外，结构矩阵有着广泛的应用背景，经常出现在下面的一些研究领域中： ( 1 ) 微分方程的数值求解； ( 2 ) 马尔可夫过程的研究； ( 3 ) 电子与机械的振动和控制； ( 4 ) 调和恢复问题； ( 5 ) 自正交小波基的构造： ( 6 ) 其他各种各样的工程和物理问题 1 2 本文的研究内容和创新 1 2 1 本文研究的内容 在本论文中，主要研究了广义中心对称矩阵( 广义中心厄米特矩阵) 的矩阵 乘积的快速算法和此类系数矩阵线性方程组的并行计算方法此类方程组有着广 泛的应用背景，经常出现在下面一些领域中：1 ) 在微分方程的数值求解中；2 ) 在某个马尔可夫过程的研究中；3 ) 在自正交小波基的构造中；4 ) 在多维的调和恢 复问题中：5 ) 在别的各种各样的物理和工程问题中其中小波分析是数学中的一 个迅速发展的领域，正在成为一个重要和活跃的研究领域，更重要的是它已经在 数学家和电子工程师之间建立了一种牢固的联系，引起了其它学科的科学家和工 程师的注意对于小波分析是用泛函分析的方法研究的，然而在小波的研究中矩 阵方法起着一个重要的作用 论文中主要讨论了三个问题第一：关于含有广义中心对称矩阵( 广义中心 厄米特矩阵) 的矩阵一向量乘积的快速算法；第二：关于含有广义中心对称矩阵 ( 广义中心厄米特矩阵) 的矩阵一矩阵乘积的传统算法；第三：关于含有广义中 心对称矩阵( 广义中心厄米特矩阵) 的矩阵一矩阵乘积的块算法，即翮位删n 算 法 1 2 2 本文的主要创新 1 ) 在第三章中，针对广义中心对称矩阵和广义中心厄米特矩阵设计了一 种关于这两种矩阵与向量乘积的快速算法建立的算法主要是在计算量和占用计 算内存方面有了很大的改进：并且对于广义斜中心对称矩阵也有类似的结论成 立 2 ) 在第四章中，利用第三章得出的定理和算法，把它推广到关于广义中 2 心对称矩阵与矩阵乘积的问题而且算法在计算量和占用计算内存方面也有类似 的改进 3 ) 在第五章中，利用矩阵的分块来计算关于广义中心对称矩阵与矩阵乘 积的问题，5 打n 盯绷算法相比于传统算法来说，计算量和占用计算内存都有一定 的改进 第二章预备知识 实矩阵的集合；- ，为置换矩阵，其中次对角线( 左底到右上) 元素为1 而其它元素 定义2 1 设爿为n h 的复数矩阵，如果，一，。一爿成立，则称彳为中心对 称矩阵，其中，。为次对角线上元素为1 其余元素为o 的置换矩阵 定义2 2 若矩阵爿中的元素满足下面的关系式：4 “。口，。小。，一r ”，则 月一( 罢；：暑：) ，e c r “m p ，。6 ，。a 。 4 置ln 7 a 口7 ，l ，口，c 月删，口，6 尺4 砌，口r 1 x 1 ic 6 ，丑，j 定义2 3 设一为n n 的复数矩阵，如果，一j 。；彳成立，则称一为中心厄 爿：f 兰n 苎z 1 ，( 其中。：2 ，1 ) ，。彳1 。，m 爿1 ，m 定义2 4 设4 为n _ r l 的复数矩阵，如果，。- 一彳成立，则称爿为斜中 定义2 5 一个矩阵彳c 称为广义中心对称矩阵，如果翩k 一：称为广 义斜中心对称矩阵，如果刖k 一一一；称为广义中心厄米特矩阵，如果删k - 爿， 其中爿定义为彳的共轭 等价地，一个矩阵爿= ( 4 叫) c 为广义中心对称矩阵当且仅当口，一4 ，( ；x 。( ； 为广义斜中心对称矩阵当且仅当4 - 一4 州h ( ；为广义中心厄米特矩阵当且仅当 口，一口r “n ( ) ，f ，j - 1 ，万 显然，当r o ) - 万一f + 1 ，即k 一，时，一个广义中心对称矩阵爿c 就变 成了一个中心对称矩阵；一个广义中心厄米特矩阵爿c 就变成了一个中心厄 米特矩阵 第三章广义中心对称矩阵的矩阵一向量乘积的计算 3 1关于矩阵一向量乘积 在这一章里，我们将讨论广义中心对称矩阵的矩阵一向量乘积的计算 对称的( 厄米特) 而印舷矩阵形成了中心对称( 中心厄米特) 矩阵的一个 重要的子类，它们很自然地出现在数字信号处理和其它领域，见例 1 ，2 和其中 的文献中心对称矩阵及其相关矩阵近来在许多问题的求解中起了重要作用，这 些问题是在实的或复的物理系统分析中提出来的，而这些物理系统通常在某一水 平上是几何对称的，见例文献 4 ，5 ，7 在传统算法中，矩阵一向量乘积血的计算量为n 2 次乘法和n 2 一h 次加法，其 中爿和x 都是n 维的然而，当4 为一结构矩阵时，通过探索矩阵的结构和性质， 计算量将会大大减少近来， 把砌册 6 考虑了矩阵一向量乘积爿石的计算，其中彳 1 为对称中心对称矩阵在 耙砌口_ r l 的算法中，只需要三月2 + n 次乘法和二竹2 + ，1 次加 24 法来计算“一血前不久，励船6 e n 如r 和j ) 打伽 2 进一步讨论了更一般的情 1 形，当爿为中心对称矩阵时，在他们的算法中，计算“一缸用了二n 2 + d ( n ) 次乘 z 法和n 2 + d 0 ) 次加法我们注意到在f 口嬲6 翻胁和，七m d v 的算法中，主要工具 是( 斜) 中心对称( 中心厄米特) 矩阵的约化，利用了一个简单的相似变换在 他们工作的推动下，本章中，我们继续讨论计算触这个问题我们首先研究所 谓的广义中心对称矩阵，广义斜中心对称矩阵和广义中心厄米特矩阵的约化，特 别地，我们提出的关于这几类矩阵的算法可视为而船6 朗如r 和肋小d v 的算法的 推广我们看到我们的算法，当计算很多的矩阵一向量乘积爿工，其中矩阵爿为同 一个广义中心对称矩阵，可以节省许多计算量此外，对于某广义斜中心对称 矩阵和广义中心厄米特矩阵，我们也有类似的结果 3 2 几个例子和定理 关于广义中心对称矩阵类，除了中心对称矩阵外，我们还发现了其它的矩阵 类，它们出现在各种实的或复的物理和工程系统分析中提出的一些问题的求解 中，其中每一个k ，。是一个对称置换矩阵我们列举3 个例子，即三个广义中 6 k 0 ，】 例2 块中心对称矩阵( 对称块而印f f z 矩阵可以看成一个块中心对称矩阵的特 k 2 一 ip l p l p ( 2 ) 例3 分块中心对称矩阵( 7 中的b l o c k c i r c i l l a n t - c i r c u l a i i t _ b o l c k 矩阵为一个特 殊的分块转中心对称矩阵) ，其中 玛- ( 3 ) 众所周知，总存在一个简单的相似变换，使得每一个n n 的中心对称矩阵相 似为一个对角块矩阵，见 2 对于广义中心对称矩阵，我们有以下类似结论 定理3 1 矩阵4 c 为一个广义中心对称矩阵当且仅当存在一个如方程( 8 ) 所定义的正交矩阵q ，使得 q 7 爿q 耳( bc ) c 4 ， 其中口c 扣一i 4 一，c c 对，= ，口n 七( ，一k ) 在给出定理3 1 的证明之前，我们首先给出矩阵q 的一种构造设k 为对应 于不相交对换的固定积j r 的n 阶置换矩阵，可以推知，k 2 一，和k 7 k 根据广义中心对称矩阵的定义，我们设r = t ，一，其中“。是 个对象 的f 不相交对换，定义了一个变换，它交换了第五个和第r ( 工) 个对象的位置( 我 们假设 c ，：c c ) 用乞川 ) 表示对应于变换一的置换矩阵，记为 即 巴。( ) = 1 c o l u mc 0 l u ” j ik t i 1 0 1 1 0 1 1 r o w r 。wr ( 工) ( 5 ) 因此，对应于_ | r 的置换矩阵k 就是( 5 ) 中的矩阵只州 ) 的乘积，其中，一1 ，f k = 乞州 ) 巴r f 】 不失一般性，我们假设工一r ( 工) ，f = 1 ，f 因为当“一f ) 时，( 5 ) 式中 己巾l 一， 令 q ，。f ) = 1 c o l u 瑚c o l u 姗 j 。k “0 压 2 互 2 压压 22 r o wr ( 上) ( 6 ) 我们可以看到，( 6 ) 中的q 肛 j 为一个j 下交矩阵，并且对于f ，s t l ，有 q 。t i j 、q p t i ，一q i 妲i j 、 定义 蚕5 珥* ， ( 7 ) 则产生了一个正交矩阵 我们定义一个新矩阵q ，它由( 7 ) 中的西列列交换而得到，特别地，正交 矩阵西的_ | r ( ) ，r ( ) 列为新矩阵的h 一，+ 1 ，月列，也就是说，存在一个置换 矩阵芦使得 q 一蚕芦一( q 1 ，q ：) ( 8 ) 其中q 1 定义为q ( 1 ：厅一f ) ，由q 的前h 一，列组成；q 2 定义为q o 一“- 1 ：n ) ，由矩 阵q 的最后，列组成 定义 k = ；( + k ) ，k ：一三( ，一k ) ( 9 ) 容易验证，矩阵q 1 和q 2 为( 9 ) 中矩阵k 和的最大秩分解即q l q f k ， q ：西一哎 我们现在回到定理1 的证明： 定理3 1 的证明：由前面的构造，我们知道( 8 ) 中的正交矩阵已经定义好了 ”一”假设( 8 ) 中的正交矩阵q 满足下面关系 q 7 彳q = ( 口c ) 等价地，有 小q ( bc ) q 7 注意到，k = q 。q j q 2 讲和q = ( q i ，q ) ，可推知 9 c ”q ，( bc 腿卜q ，( 曰c 刊 q 7 爿q 一( 要) 爿c q ，q ，= ( 簧三蓦要三曩) 岫翘一( 曼卜刮= ( 裟麓) 因为q 7 一q q 7 翩翘，这表示q f 爿q 2 = o 和q j 爿q 1 = o 必须同时满足，因此，我 q 7 爿q 罩( 口c ) 其中口= q j 爿q c n 一卜肛o ，c l q ；爿q ：c m 譬二 ， 托三) 1 0 孚一 互 2 当p 一2 鼋+ 1 时，q 有如下形式： 压 2 i ，目 一lq ，q q l q】l 压 压 一l l j4 一l q 口 对于j 义斜甲心对杯矩| 5 牛，我们硐如r 足埋，为j 义斜甲心对杯矩阵阴千甘似 可约性 定理3 2 设q 如方程( 8 ) 中所定义，则矩阵爿c 为广义斜中心对称矩 阵当且仅当如下关系式 q 7 彳q = ( ，) c t ， 成立，其中c n 。川，c 。“，一，口月七( ，一k ) 证：”一”设q 如( 8 ) 中所定义，等价地( 1 1 ) 式成立，所以 爿皇q ( ，e ) q 7 因为k = q 1 研一q ：篮，q 一( q l ，q 2 ) ，我们有 c ”q ，( fe 腿) | - ( q 川( fe 刊 ”一”设爿为广义斜中心对称矩阵，q 为如( 8 ) 所定义，那么由假设，我们有 q _ q = ( 要) 一c q ，幺，2 ( 要三耋簧：笼) 和 岫叫豺c 蜴，刮- ( 裟麓) 因为q 7 爿q ；一q 7 删磁，那么q j 一q l o 和q j 爿q 2 - o 必须要同时满足，因此我 们有 q 7 爿q 暑( ，e ) 其中e 一研爿q j c ”m ，f t q f 爿q 1 c 7 巾。 口 对于中心厄米特矩阵，我们总可以利用一个简单的相似变换把它转换成一个 实矩阵，同样对于广义中心厄米特矩阵，我们有同样的结论这就是下面的这个 定理 定理3 3 设q 为如方程( 8 ) 中形式，并定义 u 一( q l ，j q 2 ) ( 1 2 ) 那么矩阵爿c 为广义中心厄米特矩阵当且仅当下面方程 c ，”彳u = ( 雪：主：) r “” c ，。， 成立，其中j 1 1 r ( 4 ) 一( 一一n ，j 1 2 r 扣。m ，j 2 。月。一。一n ，j r 证：容易验证u 为酉矩阵 ”一”设u 如( 1 2 ) 所定义，等价地( 1 3 ) 式成立，所以 叫麓p 因为k = q l 鲜一q 2 西，u = ( q 1 ，f q 2 ) ，我们有 c 旷训睇阍= 一圳封j 由定义，我们得出结论月为广义中心厄米特矩阵 ”一”设爿为广义中心厄米特矩阵，由假设，我们有 心u 一( 要卜训_ ( 裴 和 f 研爿q 2 1 骈爿q 2j 班翮一鼢c q ，一咖眨篙鬻) 因为u ”爿u ；u ”k j k 【，所以甜爿q j q j 面，q f 爿q j 一一q f j q | ， q q 1 - 一篮鸽和辨爿q 2 一q j 鸽必须同时满足，因此我们有 u ”一u 傺纠 i 爿2 1爿2 2 j 其中j 。讲一q j r ( 一。) 巾_ f ) ，j - 2 一h n ( q f 爿q 2 ) r “一m ， j ：。一i | l l ( q j 爿q 】) 月j x ( “和j zz q j 爿q 2 r “，l m ) 记为矩阵s 的虚部 口 3 3 算法 在前面一节的讨论的基础上，我们将针对广义中心矩阵( 广义中心厄米特矩 阵) 一向量乘积4 工提出两种算法，它们可以看作是 2 中而船6 翻d e r 和腑叼m 洲的 算法的推广在下面算法中，我们假设算法3 1 中的矩阵爿为n x 疗的广义中心对 称矩阵，算法3 2 中的矩阵彳为一x 月的广义中心厄米特矩阵 算法3 1 该算法用来计算广义中心对称矩阵一向量乘积4 工 准备步： 步i ：构造一个如方程( 8 ) 的正交矩阵q ，把q 分划成q 一击( 西。，蚕z ) ， 其中m n t ( q 2 ) 一f ，f 一阳船( ，一k ) 步i i ：计算矩阵x 。矩，y 一爿a ： 步i i i ：计算矩阵否。a j x 和0 ，反y 计算步： 步l ：计算向量 y 埘工恒心) 步2 ：计算向量 z - 褂 步3 ：计算向量 “一壶彩一拉毛+ 翻 现在我们来给出该算法的计算量特别地，在准备步中，我们需要计算z ， y ，曰和c 因此在准备步中需要如f 次加减法和o 一2 ，) ( 知一f ) 次乘法在计算步 中，步1 需要型次加减法和n 一2 ，次乘法，步3 需要同样的加减法加上n 次除法 在步2 中，由传统算法，需要q f ) 2 次乘法和o 一矿一o f ) 次加法来计算匆。， f 2 次乘法和f 2 一f 次加法来计算a ，：所以，计算矩阵一向量乘积“：血的总的计算 量为抽2 + 甜2 7 月，+ 知一甜次乘法和h 2 + 爿2 + 月f + 4 f 一胛次加法在传统算法中， 需要n 2 + o ( h ) 次乘法和n 2 + d o ) 次加法，比算法3 1 中的结论要好一些，而且 比而卵6 p n 如和舭小d v 的算法中的去n 2 + d ( h ) 次乘法和甩2 + d ) 次加法的结 果还要差一点然而，当爿为中心对称矩阵时，作一个小的修正，我们的算法就 注l ：如 3 中所述，我们计算了很多的乘积，就像用同样的矩阵爿来计算五：石 一样例如，用迭代法来计算爿工，那么只有我们算法里计算步中的步卜3 一定 会被新的向量；所替换，准备步中的否和a 被储存也就是说用同样的矩阵一来 计算，每一个多余的乘积只需要0 一f ) 2 + f 2 + d 0 ) 次乘法和同样次数的加法如果 乘积的数字充分大，那么我们的算法在计算量上就有很大的节省 注2 ：对于一个给定的广义中心对称矩阵，在准备步中降低计算量是可能的如 果矩阵k 有一定的结构，例如在例卜3 中的k = k ，k ，玛在这种情况下，对应 于k ，矩阵爿可以分划成某种块结构，比如说中心对称矩阵的情况例如，如果爿 1 4 一b 磊：象】 口一( 4 澎9 矧 扣 一- 卜辋3 鼢 2 拈删0 辋。三 ) ) ) m 垤 m ( ( ( 啦吼 = 以，在计算矩阵一向量乘积h = 瓜时，总的计算量为( p + q ) 2 + p 2 + 2 p 口+ n 次乘法 和p + q ) 2 + 3 p 2 + 2 p + 口次加法运算注意到g - 月一2 p ，则运算浮点数可写成 2 ，1 2 2 朋+ 印2 如果牙p ，即2 p 一厅时，此时的浮点数近似等于昙n 2 ，这也就 是说计算量上的一个很大的节省是可以达到的 现在，我们回到计算广义中心厄米特矩阵一向量的乘积上来，即下面的算法 算法3 2 该算法用来计算广义中心厄米特矩阵一向量的乘积a x 准备步： 步l ：构造方程( 8 ) 中的正交矩阵q ，并且把q 分划成q = 击( 西。，蚕：) ，其 中m 础( a ：) 一f ，f = 阳础( ，一k ) 令【，一击( a ，f 蚕：) 步2 ：计算 j = 矩，和y ；爿蚕： 步3 ：计算矩阵互。：茁x ，互：1 1 1 1 ( a i 】，) ，j ：，。一i i n ( 圣：x ) 和j ：a r y 步4 ：构造实矩阵 j 怯习 计算步： 扪州韩量y 砌( 荛卜“h i f q ：工j 步2 ：计算向量 r e ( z ) 一j r e o ) 并定义 z = r e ( z ) + f l m ( z ) 步3 ：计算向量 “一击沈= 扭嘶) 一蚕：h n 】+ 籀i i l l + 蚕：r e ( 圳 在准备步中，我们需要计算x ，y ，j ，五：，j ：。j 。一个乏味而简单的计算表明， 1 6 计算量大约为4 n f 次复数加法和2 n 0 一型) 次复数乘法在计算步中，主要的工作 是做步2 ，它需要的计算量大约为相同维数的复矩阵一向量乘积的一半步l 和步 3 的计算量可以忽略同样，该算法的结果看起来比传统算法要差一些，但是， 如前面注中对于广义中心对称矩阵所说，该算法在我们用广义中心厄米特矩阵计 算许多矩阵一向量乘积时，它保证了重要的结果而且，当矩阵k 有一定结构时， 那么在准备步中的计算量可能会减少例如，特别地在例卜3 中，k k ，哎，巧 1 时，作一个小的修正，在准备步的计算量大约为去以2 次加法和更少的乘法在其 z 它情况下，我们的算法相对来说也有一定的节省，比如说，用我们的算法来做 2 中的中心厄米特矩阵 第四章广义中心对称矩阵的矩阵矩阵乘积的 传统算法 4 1 关于矩阵一矩阵乘积 矩阵乘法是数值代数领域中一个不可缺少的内容，一直以来人们关于矩阵乘 法的研究都很多因为关于矩阵乘法的研究在实际问题中有着重要的应用价值 比如越来越多的工程问题最终会归结到关于线性方程组的求解，这样就不能不牵 涉到矩阵乘积计算随着科学的发展，计算机水平的不断提高以及人们对解决问 题速度的不断提高，我们就不得不研究新的计算方法来达到人们的不同要求从 目前来看，主要的矩阵乘法的方法可以归纳于以下几种 ( 1 ) 关于矩阵乘法的最早的算法是我们平时最常用的传统矩阵乘积算法， 也就是根据矩阵乘法的定义来计算这种计算方法不仅计算的速度慢，而且要求 计算的内存空间要很大。并且在运算过程中采用的是一水平级的点一点运算，同 时当我们涉及到超大规模的矩阵乘积时这种计算方法几乎是没有实际应用价值 的用传统的方法计算矩阵乘积一一p ，其中一、p 都是n 阶矩阵，需要至少 加3 次浮点运算见参考文献 3 ( 2 ) 另外一种方法是r 鲫册算法研，口船朗算法采用了一种递归的方法 把两个h 一拥阶的矩阵乘法转换成许多阶数为肌的子问题来计算，最终可以把 问题转换成m x m 的子块运算，即7 个子块矩阵乘法与1 8 个子块矩阵的加减法运 算在整个算法中一共需要孙崦i 一2 n2 8 1 次运算与传统的算法相比在计算量方 面有了很大的改进：并且在，口船朗算法中采用了块块的三水平级的计算，减 少了计算所需要的时间，见参考文献 3 ( 3 ) 目前关于矩阵乘法在需要计算量方面最少的是由胁昭阳d 和 卸p p 胚加油提出的算法，他们的算法只需要0 02 “) 次计算量，但是这种算法 在实际的运用中没有应用价值见参考文献 3 ( 4 ) 对于一些特殊的矩阵，根据它们相应的性质，提出的许多新算法在 本章的以下部分我将主要建立广义中心对称矩阵和广义中心厄米特矩阵的矩阵 与矩阵乘积的算法 4 2 广义中心对称矩阵乘积的传统算法 4 2 1 引言 在这一部分当中，我们主要研究了关于矩阵乘积- a p 的几种算法，用传 统的算法计算矩阵乘积胛，其中彳、p 都是甩疗矩阵，需要n3 次乘法运 算以及咒3 一，1 2 次加法运算，即大约需要2 疗3 浮点运算 本章中，我们运用广义中心对称矩阵和广义中心厄米特矩阵的约化性质得到 几个计算矩阵与矩阵乘积一爿p 的快速算法，其中彳或p 为广义中心对称矩阵 或广义中心厄米特矩阵，与文【4 0 】的对应算法相比有更一般的结果当彳或尸为 广义斜中心对称矩阵，可建立类似算法，计算量方面也有类似的结果 4 2 2 知识回顾 我们先回顾一下几个重要的关于广义中心对称矩阵和广义中心厄米特矩阵 的约化结果，见第三章中的定理3 1 ，定理3 2 和定理3 3 4 2 3 算法 在以上讨论的基础上，我们提出两种算法用来计算矩阵与矩阵的乘积彳p ， 在算法4 1 中，假设爿为广义中心对称矩阵：在算法4 2 中，假设4 为广义中心 厄米特矩阵 算法4 1 该算法用来计算广义中心对称矩阵与矩阵的乘积爿尸 准备步： 步1 ：构造第三章中方程( 8 ) 所定义的正交矩阵q ，并作分划使得 q = 击( 西。，计其中阳州珏川州m ) 步2 ： 计算矩阵 x 一q 。，y 一爿q ： 步3 ：计算矩阵吾；拜x ，己。a ：y 计算步： 步1 ：计算矩阵 1 9 吖锄p 甾心) 步2 ：计算矩阵 = 吖= 倒) 步3 ：计算矩阵 一去q ；抑l + 西：2 】 下面讨论一下该算法4 1 的计算量在准备步中我们只要计算x ，y ，和 a ，需要知f 次加减法和2 ，1 2 + ，l ，+ 型2 在计算步骤中，步1 需要2 n f 次加减法和 n 2 + 2 ，l f 次乘法；步2 中需要矿一2 ，1 2 ，+ 知f 2 一九2 次加减法和n 3 2 ，1 2 “抽f 2 次乘 法：步3 中需要_ r 1 2 + 2 ，l f 次加减法和知2 + 2 ，l f 次乘法那么共需要的计算量为 n 3 2 n 2 f + 2 ，l f 2 + 7 n f 次加法和n 3 2 ，1 2 f + 知，2 + 5 n 2 + 5 n “刀2 次乘法如果 f 一三n ，则算法4 1 中的计算量近似为三”3 个乘法运算和三一3 个加法运算，即n 3 个 浮点运算与传统的矩阵与矩阵乘积相比较，节省了大约一半的计算量如果 ，n 或f 1 ，则无需进行约化，直接用传统的乘法算法但是当一为中心对称矩 阵时，只要做一个小的修正，我们的算法就变成了 4 0 中对应的算法了所以说 我们的算法是 4 0 中对应算法的一个推广 算法4 2 该算法用来计算广义中心厄米特矩阵与矩阵乘积a p 准备步： 步1 ：构造第三章中方程( 8 ) 所定义的正交矩阵q ，令q 击( 圣。，蚕：) ， 使得朋州a ：) - f ，其机删州嘲，令u = 击f 蚕：) 步2 ：计算x 。爿西。，y ；爿蚕：x 步3 ：计算矩阵五，；茁x ，互：；i m ( 蚕：y ) ，j ：。一i t i l ( a ：x ) 和j ：蚕：y 2 0 j = 瞄习 计算步： 步1 ：计算矩阵 肌脚儿峨阶n m ， 步2 ：计算矩阵 r e ( j v ) - 一r e ( m ) l i i l ( ) 1 l n 似) 并定义 = r e ( ) + f i m ( | v ) 步3 ：计算矩阵 彤- 去叫- 擀，f 础r c ( ) + f h n ( ) ) 一抑r e ( ) 一蚕：i i i l ( ) 】 + 圭 蚕。i i i l ( j v ) + a zr e ( ) 】- r e 缈) + 洒) 在该算法中，主要计算量为计算爿r e ( m ) 和爿i i i l ) ，按传统的矩阵与矩阵 乘法算法，总共需要2 ，1 3 个实乘法运算和2 n 3 个实加法运算，总共需要4 n 3 个实浮 点运算而计算爿p 则需要n 3 复乘法运算和n 3 个复加法运算容易观察，一个复 乘法运算等价于4 个实乘法加上2 个实加法运算，一个复加法运算等价于2 个实 加法运算所以计算爿p ，用传统算法计算则等价地需要大约8 n 3 个实浮点算术 运算相比较而言，我们的算法节约了大约一半的计算量 第五章广义中心对称矩阵一矩阵乘积的块算法 在上一章中，矩阵一矩阵乘积的算法需要大约加3 次浮点运算，它表明还有 其它的计算矩阵一矩阵乘积的方法，使得计算量会有相当的减少& r 口船册算法 是这些方法中最早被发现的，也是最易于解释的一种方法该算法把两个乘积矩 阵分划成2 2 的块矩阵，并且用7 个矩阵乘法和1 8 个矩阵加法来计算子块，这 些矩阵的子块为原矩阵阶数的一半 5 1 广义中心对称矩阵一矩阵乘积的跏韶柳算法 算法5 1 ( 在算法4 1 中我们引进斯口s s e n 算法( 见参考文献 3 ) 就可以得到 算法5 1 ) 该算法用来计算广义中心对称矩阵与矩阵的乘积爿p 准备步： 步1 ：构造第三章中方程( 8 ) 所定义的正交矩阵q ，并作分划使得 q 一击( 蚕。，计其中觚( a ：) 乩，一枷( ，旧。 步2 ：计算矩阵 i 一爿a 。，哥= 爿蚕： 步3 ：计算矩阵 e ：薪膏，屹；a ：哥 计算步： 步1 ：计算矩阵 ，岫叫弘川馁 y 2 r 贬乏) a 在此步中我们引进旭站e h 算法来计算z ：口y 木 z 一勋s s 明( b ，y ，1 ) 车返回z = b y ，其中曰、y 为月n 阶的矩阵丰 k 匕 ， = 、ll， 芝 r r 2 q q 矿 疗l ，p m ，玎 z 曩口y e b p 删砌一b 。封y 5 限净鳓每个子块觯均枷研 阶矩阵丰 丁，s ，r 区，卵n ( 一口。，l ，：。+ y n ，n ) 7 ：一跏韶e n ( 口。+ 口。，y 。+ y 。，n ) r ，跏n 鼯明( 矾，y 。+ y 。n ) r 。一慨一( 曰。y 。，n ) r ，一慨盯( 口，y 。一y 。，多n ) r 。一胁n 船e n ( 如，y ：，一y 。n ) r ，一& 旭船朗( b 。，y 。n ) z 1 l = r l + 丁2 一丁4 + 丁6 z 1 2 - 丁4 + r ， z 2 1 一丁6 + 丁7 z 2 2 一r 2 一r 3 + z 5 一r 7 胁川z 2 巨射 步3 ：计算矩阵 矽一击凹- 舡a z ) 眨孙舡u + 瓴，醌厄z z ：) 算法分析：下面我们计算算法5 1 所需要的浮点运算数我们知道此算法中除在 步2 较算法4 1 有所改进以外，其他的步是一样的在应用r 口船明算法计算 z 制一f 名1 剐乏乏) 时需要大约2 n k l z 7 2 ，1 2 “次计算量；然而此时有： e ：；哎。= o ，故此时我们只需要1 ，1 2 8 1 次计算量 综上所述，当n 较大时，算法5 1 只需要1 n 2 。1 次计算量，计算过程更简单 明了，比原来的5 加船硎算法减少了总计算量的 类似地，当彳为斜中心对称矩阵时，利用改进的m & 明算法计算一爿p 只需要1 n 2 ”，比原来的算法减少了大约n 2 “，故此算法有很大的实用价值 5 2 广义中心厄米特矩阵一矩阵乘积的胁船鲫算法 在本节中总是假定爿为月n ( 月一2 册) 阶的中心厄米特矩阵，p 为h n 阶 的任意的矩阵，下面我们来讨论此时缈一爿尸的算法在这一部分当中彳、p 分别 记为：月一4 + 坞：尸；号+ 幔其中4 、4 分别表示爿的实、虚部：p 。、p ：分 别表示p 的实、虚部 首先我们考虑用传统算法计算一一尸，即 彤a 胛一( 4 + 坞) ( 号+ 以) ；4 # 一4 足+ f ( 4 罡+ 4 墨) 在这个计算过程当中我们总共要计算4 个n x n 阶矩阵的乘法以及4 个厅n 阶矩 阵的加减法，需要的总计算量大约为：跏3 次计算量若用勋4 船翻算法计算大约 需要8 ，l i o | z 7 8 ，l “次计算量 算法5 2 ( 在算法4 2 中我们引进旭韶p n 算法( 见参考文献 3 ) 就可以得到 算法5 2 ) 该算法用来计算广义厄米特矩阵与矩阵的乘积4 p 准备步： 步1 ：构造第三章中方程( 8 ) 所定义的正交矩阵q ，令q 一击( 蚕，a ：) ， 使得旭似a ：) = f ，其中f - 阳州，訇，令u 一击( 蚕a ：) 步2 ：计算膏。_ 蚕，：爿a ： 步3 ：计算矩阵j 。蚕。7 夏，j 。：l m ( 蚕。7 哥) ，j ：。一j m ( 蚕：孑) 和j 。；蚕：哥 步4 ：构造实矩阵 j 也 计算