（计算数学专业论文）实块toeplitz矩阵的相关高性能算法研究.pdf

摘要 块t o e p l i t z 矩阵在计算机的时序分析、自回归时序模型滤波中经常出现，在 处理块t o e p l i t z 矩阵的计算问题( 例如向量积、求解线性方程组、计算特征值) 时，若矩阵的阶数较小，通常的经典算法是可行的( 如l u 分解算法、鲫算法等) ， 但是，在许多实际应用中，矩阵的阶数很大或某个线性方程组需要多次计算直到得 到一个满意的结果( 如，迭代法) ，这些经典算法由于代价太大而失去了实际意义 本文主要是针对实块t o e p l i t z 矩阵的特殊结构与性质来设计一些数值稳定， 快速的算法本文总共分五章，结构如下： 第一章为绪论，主要介绍本课题的研究背景、选题依据，以及研究内容 第二章为预备知识，主要介绍在论文中需要用到的矩阵基本定义、定理和基本 性质，以及符号表示 第三章是针对一般的实块t o e p l i t z 矩阵的结构与性质对其进行嵌入和置换分 裂的不同处理，再利用块状快速傅里叶变换b 一阡丁对其进行快速向量积运算， 从而得到高性能算法 第四章是针对特殊的实块t o e p 厅t z t o e p l i t z 块( b t t b ) 矩阵的结构与性质利 用前一章的处理技巧，然后对其进行块状快速傅里叶变换曰一即丁，通过优化算 法得出其快速向量积运算过程，并对两种不同的方法进行了性能比较 第五章介绍一种基于离散双j 下交小波变换( b d w t ) 的实块t o e p l i t z t o e p l i t z 块( b t t s ) 矩阵的快速变换算法在实序列数据处理中，离散小波变换( d w t ) 不 仅等效于离散傅里叶变换( d f t ) ，其正逆变换又具有相同的形式，而且d w t 仅 需用到实运算，在存储量和复杂性上要比d f t 更经济与一般的三角变换相比， 紧支撑正交小波变换可使其变换后仍然保持原来的b 1 7 b 的特征，具有保结构的 特点，可以很好地保证求解线性方程组中迭代算法的执行，给大型b t t b 线性方 程组的求解可以提供很大的帮助 关键词：实块t o e p l i t z 矩阵；实块t o e p l i t z - t o e p l i t z 块( b t t b ) 矩阵；快速块傅 里叶变换：离散双正交小波变换；保结构： a b s t r a c t b l o c kt o e p l i t zm a t r i c e so f t e na p p e a ri nt h ec o m p u t e rt i m i n ga n a l y s i s ，a u t o r e g r e s s i v et i m es e r i e sm o d e lf i l t e r i n g w h i l ed e a l i n gw i t ht h ec a l c u l a t i o no fab l o c k t o e p l i t z m a t r i x ( s u c ha sv e c t o rp r o d u c t ，s o l v i n gl i n e a re q u a t i o n s ，e i g e n v a l u ec a l c u l a t i o n ，e t c ) ， i ft h eo r d e ro ft h em a t r i xi ss m a l l ，t h eu s u a lc l a s s i c a la l g o r i t h m s ( s u c ha sl u d e c o m p o s i t i o na l g o r i t h m s ，q ra l g o r i t h m s ，e t c ) a r ef e a s i b l e b u ti nm a n yp r a c t i c a l a p p l i c a t i o n s ，t h eo r d e ro ft h em a t r i xo rt h es i z eo fal i n e a rs y s t e mo fe q u a t i o n ss o l v e d b yi t e r a t i o n su n t i lg e t t i n gas a t i s f a c t o r yr e s u l ti su s u a l l yl a r g e t h e nt h eu s u a lc l a s s i c a l a l g o r i t h m sa r es oe x p e n s i v et h a tt h e yh a v en op r a c t i c a lm e a n i n g s i nt h i st h e s i sw ew i l ld e s i g ns o m en u m e r i c a ls t a b l ea n d o rf a s ta l g o r i t h m sf o rt h e r e a lb l o c kt o e p l i t zm a t r i c e sb ye x p l o i t i n gt h e i rp a r t i c u l a rs t r u c t u r ea n dt h en a t u r e t h i s t h e s i si sd i v i d e di n t of i v ec h a p t e r sw h i c ha r el i s t e da sf o l l o w s ： t h ef i r s tc h a p t e ri sa ni n t r o d u c t i o n ，i nw h i c hw ed e s c r i b e st h er e s e a r c hb a c k g r o u n d ，t h em o t i v a t i o no fc h o i c eo ft h et h e m e ，a sw e l la sr e s e a r c hc o n t e n t t h es e c o n dc h a p t e ri sp r e r e q u i s i t e s ，i n c l u d i n go fs o m eb a s i cd e f i n i t i o n s ，t h e o r e m s ，a n dn o t a t i o no f t e nu s e di ns e q u e l i nt h et h i r dc h a p t e rw ed i s c u s sh o wt oe m b e do rs p l i tar e a lb l o c kt o p l i t zm a t r i x f o rt h ec o m p u t a t i o no fam a t r i x v e c t o rp r o d u c tb ye x p l o i t i n gt h ep a r t i c u l a rs t r u c t u r e ， a n dt h e nu s i n gt h eb l o c kf a s tf o u r i e rt r a n s f o r m ，s o m ef a s t ，h i g h - p e r f o r m a n c ea l g o r i t - h m sa r eo b t a i n e d s o m ea l g o r i t h m sf o rt h er e a lb l o c kt o p l i t z - t o p l i t zb l o c km a t r i xv e c t o rp r o d u c t b a s e do nt h ed i s c u s s i o no ft h ep r e v i o u sc h a p t e r sa r ep r e s e n t e di nt h ef o r t hc h a p t e r , s o m e c o m p a r i s o nf o rt h ep e r f o r m a n c eo f t w od i f f e r e n tm e t h o d sa r ea l s og i v e n i nt h ef i f t hc h a p t e rw ed e s c r i b eaf a s ta l g o r i t h mo fr e a lb l o c kt o p l i t z t o p l i t zb l - o c km a t r i xb a s e do nad i s c r e t eb i o r t h o g o n a lw a v e l e tt r a n s f o r m a t i o n i nt h er e a ls e q u - n e ed a t ap r o c e s s i n g ，n o to n l yt h ed i s c r e t ew a v e l e tt r a n s f o r m a t i o ni se q u i v a l e n tt ot h e d i s c r e t ef o u r i e rt r a n s f o r m ，b u ta l s oi t si n v e r s et r a n s f o r m a t i o nh a st h es a m ef o r m ，a n d o n l yr e a lo p e r a t i o n sa r er e q u i r e d ，t h es t o r a g ea n dc o m p l e x i t yo fo u ra l g o r i t h mi sm o r e e c o n o m i c a lt h a no n eu s e dd f t c o m p a r e dw i t ht h eg e n e r a lt r i a n g l et r a n s f o r m a t i o n ，t ec o m p a c t l ys u p p o r t e do r t h o g o n a lw a v e l e tt r a n s f o r m a t i o nc a np r e s e r v et h es t r u c t u r e o ft h em a t r i xu n d e rc o n s i d e r a t i o n ，w h i l et h i ss t r u c t u r ei su s e f u lf o rs o l v i n gal i n e a r s y s t e mo fe q u a t i o n sb ya n yi t e r a t i v ep r o c e d u r e ，e s p e c i a l l yf o rl a r g eb t t bl i n e a r s y s t e m i i k e y w o r d s ：r e a lb l o c kt o e p l i t zm a t r i x ；r e a lb l o c kt o p l i t z - t o p l i t zb l o c km a t r i x ； b l o c kf a s tf o u r i e rt r a n s f o r m ；d i s c r e t eb i o r t h o g o n a iw a v e l e tt r a n s f o r m ； s e c u r i t ys t r u c t u r e i i l 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：唧酞潞 日期：砌口年t - 月驾e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。同时授权中国科学技术信息研究所将本论文收录到中国学位论 文全文数据库，并通过网络向社会公众提供信息服务。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密囤。 ( 请在以上相应方框内打“4 ”) 作者签名：锨八钰各 导师签名：乱1 中云 日期：矽归年r 月7 多e 1 日期：如f 一年j 月日 1 1 研究背景 第一章绪论帚一早三否下匕 结构矩阵的理论和算法研究是近年来的一个研究热点，在实际应用中有许多 问题都归结为矩阵计算问题，而有许多升级应用需要计算的矩阵是一些具有特殊 结构的矩阵n 6 1 ，结构矩阵的形式有很多，如t o e p l i t z ，h a n k e l ，v a n d e r m o n d e 矩阵 等等，人们希望利用这些结构矩阵来设计更快更精确的算法 自2 0 世纪初期开始，t o e p l i t z 矩阵的快速算法已经出现t o e p l i t z 矩阵作为一 类应用广泛的特殊矩阵，它在谱分析、线性预测、误差控制码、自回归滤波器设计 等领域内起着重要的作用，而块t o e p l i t z 矩阵在计算机的时序分析、自回归时序模 型滤波中经常出现因此，针对这类结构矩阵的特点来设计一些能利用它们的结构 的、数值稳定的快速算法，具有非常重要的意义近几年来，对t o e p l i t z 矩阵的研究 一直是国内外一个比较活跃的研究领域，目前对t o e p l i t z 矩阵或块t o e p l i t z 矩阵 快速算法已有了较为广泛的研究n 1 2 5 1 针对t o e p l i t z 矩阵的预处理，s t r a n g 最 初提出用循环矩阵作为t o e p l i t z 矩阵预处理子，其后t c h a n 等发展了几种不同的 循环矩阵预处理子在国内，许多学者也在相关课题上做了大量的研究工作：长沙 理工大学的刘仲云教授h 8 9 1 在数字图像处理中的几类结构矩阵的理论和算法研究 方面，香港大学的吴国宝教授n0 1 1 h 2 1 等在t o e p l i t z 矩阵各类三角变换快速算法方 面，西安交通大学的路浩、游兆永、李磊等在t o e p l i t z 矩阵，循环矩阵求逆的快速 算法与复杂性分析方面，西北工业大学的张凯院、徐仲、陆全等在t o e p l i t z 、 v a n d e r m o n d e 矩阵类的快速算法方面 1 2 选题依据、研究内容 1 2 1 本文的选题依据和研究内容 课题来源：刘仲云教授主持的国家自然科学基金资助项目( 数字图像处理中 的几类结构矩阵的理论和算法研究( ( 1 0 7 7 1 0 2 2 ) ) 本文主要的研究内容是利用实块t o e p l i t z 矩阵的特殊结构与性质来设计一些 数值稳定，快速的算法主要通过两个方面对实块t o e p l i t z 矩阵进行快速算法设 计： 一方面，针对块的结构，对实块t o e p l i t z 矩阵先进行嵌入或置换分裂处理，然后 再利用块状快速傅里叶变换曰一用叮对其进行快速向量积运算，最后对两种不同 处理技巧进行性能分析比较 另一方面，针对矩阵元素为实数的特征，采用离散双正交小波变换( b d w t ) ， 计算中仅需用到实运算，在存储量和复杂性上要比例叮更经济，同时经过紧支撑 正交小波变换后仍然保持其原有的b t t b 的特征，具有保结构的特点，这样很好 地保证求解相应线性方程组中迭代算法的执行，给大型b t t b 线性方程组的求解 可以提供很大的帮助 2 第二章预备知识 本章主要介绍在论文里面用到的一些记号以及所涉及到的定义和性质，其中 的基本性质均只列出参考文献不再写出证明 定义2 1 若记乙。为一个m xm 的实块t o e p l i t z 矩阵( 其中每小块的大小 均为刀, ) ， 乙。= 其中4 ( 1 - m i m - 1 ) 为，l n 的任意实矩阵 ( 1 ) 若每个小块4 ( 1 - m f ，l 1 ) 均为刀刀的t o e p l i t z 矩阵，即 4 = 口f 0 口j 一i ： q 1 a l ，0 q 一1 a t 。 一2a i ， 一1 q 月q口j ， 一2 此时称l 。为实块t o e p f i t z - t o e p l i t z 块( b t t a ) 矩阵 ( 2 ) 若4 f = 以一f ( 1 - m i m - 1 ) 矩阵记为 乙，。= q ，。= b c i r c ( a o ，4 ，4 ，a n 一。) 此时称q 。为实块循环矩阵；如果每个小块4 f ( 1 - m f m - 1 ) 均为刀，l 的 实循环矩阵，n g , q 。为实块循环一循环块矩阵( b c c b ) 矩阵，简记为c c ( 3 ) 若4 ，= 一以一，( 1 - m f m - 1 ) 矩阵记为 3 一 一 一 d 砧。缸；4 4 一 一 一 d 1砧砧缸；以厶 幺4 a ；“a压山；加加4办办；加加 钆即 p o q 气 佗 一 一 q 哆 m 州甜即 乙。= 晶。= b c i r c _ 。( 以，4 ，4 ，a u i ) 此时称最。为实块斜循环矩阵；如果每个小块4 ( 1 - m f m 1 ) 均为n xn 的实斜循环矩阵，则称最，。为实块循环一循环块矩阵( b 双嚣c 口) 矩阵，简记为s ( 4 ) 本文涉及到的四种实块循环矩阵： 实块循环- 循环块矩阵( b c c b ) 矩阵，简记为q ；实块循环斜循环块矩阵 ( b c s c b ) ，简记为e ；实块斜循环一循环块矩阵( b s c c b ) ，简记为置；实块斜循 环一斜循环块矩阵( b s c s c b ) ，简记为s 定义2 2k r o n e c k e r 积的定义与性质 2 6 1 则 a = boc = 岛c6 1 2 c 岛。c 6 2 l c6 2 2 c b e 。c ； l c 2 c c ( 彳o b ) ( c o d ) = a c o b d ( aob ) r = a 7 ob 7 ( ao 曰) 一= a _ 1o b - 1 定义2 3 陋阳k r o n e c k e r 积的向量运算 ，其中。表示k r o n e c k e r 积 记x 为一个厅珑的实矩阵营w c c x ，= 薹二 从而如果记： 可得： y = c x b r v e c ( y ) = ( b pc ) v e c ( x ) v e c ( y ) = ( f o l ) 忧c ( x ) y = i 。t = t y f = f x t 。 其中x 为l , l m 的矩阵，为m m 的f o u r i e r 矩阵，y 为栉研的矩阵，v e c ( y ) 4 即为一次m n 点实序列块肼r 易知形似。) = f l 的m n 点实序列块d f t 可以通过n 次m 点实序列d 刀即可完成，从而计算巴。x 只需要有限次形 似( 。) = ，o 厶的m n 点实序列块d 刀运算 定义2 4n 阶f o u r i e r 矩阵定义如下： e = 1 石 一1 石 w 2 ( ”一1 石 1w | l 一1矿( 川)川) ( 川 忑忑 f 丁 墨型 其中w = en ，i 为虚数单位f o u r i e r 矩阵是酉矩阵，对称矩阵，对一个向量作离散 f o u r i e r 变换( d i s c r e t ef o u r i e rt r a n s f o r m 即d f t ) 即将一个f o u r i e r 矩阵乘以 这个向量19 6 5 年，j w c o o l e y 给出了著名的快速f o u r i e r变换算法 ( f a s tf o u r i e rt r a n s f o r m ) 即即r 定义2 5n 阶c i r c u l a n t 矩阵定义如下： g = c ( a ，五，以) = a五 以 以一以 五 以丸 五以一。 a以一： 五 c i r c u l a n t 矩阵完全由它的第一行元素确定，1 9 7 4 年，d h e l l e r 证明了如下定理 定理2 6 m 1 若c 为n 阶c i r c u l a n t 矩阵且它的第一行为五= ( a ，五，以) ， 则c c 掣= 旃昭( c 旯) ，即c i r c u l a n t 矩阵可以被f o u r i e r 矩阵对角化，其中 、，n f 和，日分别为n 阶f o u r i e r 变换的矩阵和逆矩阵 定理2 7 2 7 1 若s 为拧阶斜循环( s k e w c i r c u l a n t ) 矩阵则l c l = ，即斜 上石立石芝石；上石旦矗立石； 上石一l石上打； 循环( s k e w c i r c u l a n t ) 矩阵可以被f o u r i e r 矩阵对角化其中户和户分别为 ，l 阶f o u r i e r 变换的矩阵和逆矩阵 引理2 8 t 2 7 1 对长度为刀的向量作离散f o u r i e r 变换及逆离散f o u r i e r 变 换所需的运算量及存储空间为o ( n l o g n ) 推论2 9 每个块循环矩阵q 。都能表示为如下形式 c 舢= = 0 那么这两对函数称为互为对偶的双正交小波 由于( 缈，) 和( 驴，汐) 各自生成为一个多分辨率分析，故存在如下二尺度关系 伊( x ) = 压吃伊( 2 x 一疗) ； 沙( x ) = 压邑妒( 2 z 一，1 ) ； 对( 4 3 2 ) 式两边进行f t 得： 其中 痧( w ) = 日( 弘； 痧( w ) = g 、w 2 w 2 ) ； 日( w ) = 击；p m ， 驴( x ) = 压铷( 2 z 一以) ； 妒( z ) = 压季。q 3 ( 2 x 一，z ) ( 5 3 2 ) 参( w ) = 月“【, i w ) 妒2 【i w ) ； 驴( w ) = 月【i ) 妒【i ) ； 痧( 计= g 【r i w 腆“i w ) 痧( 计= g 【：，叭：) f t ( w ) = 去；反e 一 g ( w ) = 去瓯p m ，6 ( w ) = 去彘p m vz二k 经过推导7 1 我们可以得到正交关系表达式为： h ( w ) f - ：+ ( 计+ 日( w + 万) 疗。( w + 万) = 1 g ( w ) g ( w ) + g ( w + 万) g + ( w + 刀) 一( 5 3 4 ) 日( 们g ( w ) + 日( w + x ) g ( w + 万) = 0 h ( w ) g ( 们+ 疗( w + 万) g ( w + 万) = 0 这时令g ( w ) = e - j w 疗( w + 万) ，6 ( w ) = e 一一日( w + 万) ，( 5 3 4 ) 式中后两个方程 式将自动成立，而第二个方程将变成与第一个方程相同的形式，所以 h ( w ) f t ( w ) + 日( w + 万) 疗+ ( w + 万) = 1 ( 5 3 5 ) 可称之为双正交基本条件 如果令疗( w ) = 日( w ) ，则上式退化为正交基本条件：i h ( w ) 1 2 + i h ( w + 万) 1 2 = 1 容易证明( 5 3 4 ) 式等价于 繇= ( 一1 ) 1 石i t ；磊= ( 一1 ) 1 一。万。一t ( 5 3 6 ) 即 反) 和 磊 分别由 磊 和 魄 完全确定，因而可以说滤波器 玩 和 乓) 完全确定了一组双正交小波( 伊，y ，驴，妒) 由小波分解算法可推广到双正交小波的情况，图5 4 为双正交小波的分解和重 构示意图 图5 4 双正交小波分解和重构过 其中 展 和 磊) 的脉冲响应分别为 和 反 的镜像共轭，并称为分解低 通和分解高通滤波器 1 7 5 4 实b t t b 矩阵的离散双正交小波变换( d b w t ) 及其计算量分析 在图5 4 中记 峨) 和 最) 是紧支撑的双正交小波分解与重构滤波器，那么 滤波系数可表示为w = l ，石，g ，季) ，这里h = h o ，啊，h k i 1 ) ，石= h o ，红，k 一 ： 由公式( 5 3 6 ) 可知g l = ( 一1 ) 羹一l 。，i = 0 ，1 ，屯- 1 ：蚕= ( 一1 ) h k i 斗，i = o ，1 ，白一1 毛和恕分别为h 和石的长度当小波长度为奇数时我们设毛= 2 i + l ， 屯= 2 n ：+ 1 ，) j l j z , 玩 和 磊) 的支撑集就分别为 o ，i v , 一1 】和【o ，2 1 】所谓 紧支撑小波是指尺度函数缈( f ) 对应的序列 圾) 。z 只有有限个元素不为零，即 ( h ) 对于n n 由于紧支撑具有紧支撑性，所以具有运算量小，工程 实现相对容易等优点 定义5 4 1 口2 1 当小波函数妒( 工) 满足如下条件时 卜p ( z ) 出= 0 ，( 跏= 0 ，l ，1 一，n - 1 ) ( 5 4 1 ) 称汐( 功具有阶消失矩 那么可记由滤波器 。) 和 反) 生成的双正交滤波系数矩阵如下： 形：吲： l g i , o 1 1 , h k ! 一2h k , 一l 0 00 i , o 啊 h k l 一2 一t 0 氏一2h k l l 00h o 啊 g og i g 如一2 一1 0 0 0 g og i 乳一2 乳一1 0 g b 一2g b l 00 g og i 类似地可以写出 敝 和 反 的滤波系数矩阵刍和6 ，旷= 考 ，当日的 最后一行形式为 o ，o ，h o ，氏一1 时，我们称h 为完全滤波形式那么我们就 定义一个t o e p l i t z 矩阵4 的离散双正交变换形式如下： 曰= 嗽 旷卜瞄卜 疗7 6 r = | - 取g ai 矿y i r h 吼a g g 吖r c5 a 2 ， 令h = 【q 域】7 ，百= 豆幺 r ，g = 【g ig 2 】r ，g = q 龟 r 其中q ，g 1 分 别为h ，g中的前 ( ，z 一也+ 2 ) 2 行；毫，色分别为 疗，0中的前 ( n - k 。+ 2 ) 2 行，此时q 和g l 均为完全形式 引理5 4 2 如果4 是一个的t o e p l i t z 矩阵，h 和疗为完全滤波形式， 当且仅当戤百r 是一个t o e p t z 矩阵 证明：( 充分性) 可设矩阵蜀= 6 ：， u = 姒百r ，由日和疗为完全滤波 形式，记i = ( 咒一向+ 2 ) 2 ，2 = 一包+ 2 ) 2 ，则h r 1 xr ”，膏r 2xr “均为 完全形式，可得 2 ，+ 七- i2 i + k i ib - 1 岛- 1 包，= h m _ 2 f 厩叫。= 历口。一+ 2 ( 叫) ，o i n l ，o j n 2 ( 5 4 3 ) ( 5 4 3 ) 式中我们可以发现6 ，只与下标( i - ) 的变化相关，由此可知矩阵尽。 中的元素沿着每条对角线都是不变的，即h ai t r 为t o e p l i t z 矩阵 ( 必要性) 假设h 和疗不为完全形式，即m ( n - k t + 2 ) 2 ，2 ( 咒一乞+ 2 ) 2 ， 此时 m i n 2 y + k 2 1 ，n m i n 2 i + k i 一1 ，月 m i i i b 一1 ，n 一2 m i n 膏l l , n 一2 l j 岛，=h m 吲蜀叫a m 一，=h m 历a m 小： 叫) ( 5 4 4 ) ( 5 4 2 ) 式中如果( 玎一毛+ 2 ) 2 f 聆或者o 一乞+ 2 ) 2 刀，岛。j 的值不只与 下标o 一) 的变化相关，而且还与i 和_ ，的具体值有关，此时h a h r 中每条 对角线上的元素不唯一，即h a1 7 - i r 不为t o e p l i t z 矩阵，与已知矛盾口 推论5 4 3 已知q 和g l 均为完全形式，由引理5 4 2 我们可知对一个 t o e p l i t z 矩阵4 i 进行一般的双正交离散小波变换后得到的变换矩阵b 中的四 个子矩阵h af f i r ，h a g r ，g a i ：i r ，g a g r 均可表示为如下形式：t + e ， 1 9 其中丁表示一个( n - k z + 2 ) 2 x ( n - k t + 2 ) 2 或( n - k 2 + 2 ) 2 x ( n - k 2 + 2 ) 2 的 乃印z 汜矩阵，e 则表示一个如下的带状矩阵：e = ( ：) ，其中最多只有最后 ( 一一2 ) 2 或( 心一2 ) 2 夕u 和仃为非岑兀黍 定理5 4 4如果办( 尼) = 石( 尼) ，即小波为正交小波，根据引理5 4 2 可知h ai y i r ， h a # j r ，g a f i r ，g a , , g r 四个子矩阵构成的矩阵曰= i 三7 二l 是由一个大小为 。一( 向+ 红一4 ) 2 ) x ( n - ( 向+ 岛一4 ) 2 ) 的乃印疗纪矩阵曰lg l h a 4 i 疗y i f rh g l a 4 , , ( 岛7 i ： 和最 后( k , + k 2 - 4 ) 2 行与( 毛+ k 2 - 4 ) 2 列非零元元素组成，其中h a g t ， = g 1 4 膏r r 证明：令地o - r = ( c f 。，) “，g 1 4 青r = ( 喀，a ，类似( 5 4 3 ) 式我们可知 2 ，+ ，- i2 i + k l - 1七- 1k l - 1 q ，= k 吲蚕叫一，= k 辱，+ ：( h ) ( 5 4 5 ) 1 = 2 j m = 2 il = om = o k 2 一lk t - i d i 广g 。五叫 ( 5 4 6 ) 由蜀= ( 一1 ) k i 一，i = 0 ，1 ，屯- 1 ；磊= ( 一1 ) 7 h k l i 一，i = 0 ，1 ，白- 1 ( 5 4 5 ) 和( 5 4 6 ) 式可表示为 q ，= ( 一1 ) 7 九氏+ ，a m 堋叫) ( 5 4 7 ) 1 = 0m = o “一ik 一lk lh i d i ，= ( 一1 ) ”砭勘五叫+ 2 ( 叫) = 艺( 一1 ) 。纛砭+ 隅，+ 2 ( 叫) ( 5 4 8 ) 已知 ( 后) = 石( 后) ，即岛= 岛，那么由( 5 4 8 ) 式可得 v f ( 0 ，( n - k 2 + 2 ) 2 ) ，j ( 0 ，( n - k 。+ 2 ) 2 ) ， k - 一i 七，一l岛一i 七，一i 反，= ( 一1 ) 7 元瓦+ ，a m ，+ ：( 叫) = ( 一1 ) 7 以十，+ ：( 州) = 勺 口 考虑到和反对矩阵b 的影响，我们采取的一个最简便的方法就是令 和覆都为零矩阵，变换后得到的带状矩阵e 也相应地变为零矩阵，这时变 换后的矩阵b 就刚好由四个t o e p l i t z 子矩阵组成 由5 1 节中介绍的塔式算法我们可以对信号进行多级小波分解，如果记n 维信号 以力= 咳l 一乃一。 ，露力= 唬_ l 一乃一。 那么一个n x n 的t o e p l i t z 矩阵4 进行离散双正交变换( d w t s ) 就可以表示 h ( n j ) = w n ( 力4 叫r 这里的 群力= 孵力暇卜n 孵n ，吃力= 吃力唬卜n 嘭n 推广到实( b t t b ) 矩阵：记l 。为一个实块t o e p l i t z - t o e p l i t z 块( b t t b ) 矩阵， 我们来对其进行离散双正交小波变换( d b w t s ) 如下： 巧幺圳= ( 吃 o 研如) r 。( 吃 】7 o 【磙如】7 ) = ( 吃 o 厶) 【( l 圆嘭如矽m ( lo 嘭如】7 ) 】( 吃 】7 圆l ) 这里的以，j ：表示的是小波变换级数 第一步：计算t 。( o 。, j 2 = ( l 吸也) r m ( lo 嘭如】r ) 第二步：计算t 。( a 。= ( 吃 o l ) ( 呢 】ro l ) 第一步相当于对实( b t t b ) 矩阵乙。的第一列与第一行的t o e p l i t z 块进行离散 双正交小波变换( d b w t ) 很明显，是一个实块t o e p t z 矩阵由引理 3 3 1 可知存在置换矩阵p 使得p r ( 吃j 1 o 厶) p = l 圆吃m ，且使得p r z p 变成一个n xn 的实块矩阵( 其中每小块均为m xm 的实t o e p l i t z 矩阵) 因此第二步可以通过有效地利用t o e p l i t z 矩阵的结构特征进行如下计算： ( 吃 o 厶) 巧( 【唬 】ro l ) = p p r ( 吃 o l ) p p r r 。( o 。, j 2 p p r ( 吃 】ro 厶) p p r = p ( 厶p 唬以) p 7 ( o 。j 2 p ( l 【吃 r ) p r 通过前面的讨论，我们可以知道该计算的第一步需要的计算量大约为 2 l ( 2 m - 1 ) ( 4 n n j 2 ) 8 m n n j 2 ，其中= m a x n i ，2 第二步中的计算量大约为【2 n n ( j 2 + 1 ) 】( 4 m n j l ) = 8 m n n 2 ( 以+ 1 ) 因而，一个实( b t t b ) 矩阵的整个离散小波变换( d 1 4 z l s ) 计算过程中所需要的计 算量大约为8 m n n n j 。( 以+ 1 ) + 以】即运算复杂度为o ( n j , j 2 m n ) 相对于我们熟知的三角变换( d c t ，d s t ，d f t ) 而言，这个算法有如下几个优点： ( 1 ) 在计算量上与f f r 方法相比，避免了复运算；计算一个离散傅里叶变换 矩阵，与一个长度为t l 的向量，的向量积凡所需的计算量为o ( n l o g n ) ， 而计算一个离散紧支撑小波矩阵形与一个长度为刀的向量v 的向量积w v 所需的计算量为o ( n ) ，从而提高了效率 ( 2 ) 对一个稠密的b i t b 矩阵进行紧支撑小波变换可以将其变为一个分块 带状矩阵，因此对于解相应的b t t b 线性方程组的运算量可以大大得到降低 ( 3 ) b t t b 矩阵经过紧支撑小波变换后仍然可以保持原来的b t t b 的特征， 因此可以重复地运用紧支撑小波变换而能保持其原来的特征；这个性质也可以很 好地保证求解线性方程组中迭代算法的执行，给大型b t t b 线性方程组的求解可 以提供很大的帮助 结论 本文一方面通过嵌入和分裂的处理方法设计出针对一般的实块t o e p b t z 矩 阵设计块状快速傅里叶变换曰一仃可的高性能算法，再将其推广至特殊的实块 t o e p l i t z t o e p l i t z 块( b i t b ) 矩阵上，得到了提高其矩阵向量积运算性能的算法 另一方面，通过对实( b t t b ) 矩阵采用离散双正交小波变换( d b w t ) ，不仅避免 了复运算使其变为稀疏矩阵，而且保持其原有的b t t b 的特征，具有保结构的特 点，很好地保证求解线性方程组中迭代算法的执行，给大型b t t b 线性方程组的 求解可以提供很大的帮助 参考文献 【1 】c l a r k e ，rj t r a n s f o r mc o d i n go fi m a g e s a c a d e m i cp r e s s ，l o n d o n ，1 9 8 5 ：2 2 - 7 8 2 】s k m i t r a ，j f k a i s e r , e d s h a n d b o o ko fd i g i t a ls i g n a lp r o c e s s i n g w i l e y , n e w y o r k ，1 9 9 3 ：2 2 - 8 2 3 】 r w i l s o n f i l t e rt o p l o g i e s j a u d i oe n g s o c 19 9 3 ：12 - 58 【4 】c p s a n d b a n d d i g i t a lt e l e v i s i o n w i l e y , c h i c h e s t e r , e n g l a n d ，19 9 0 ：2 0 - 7 8 【5 】b j w e s t ，m s h l e s i n g e r t h en o i s e i nn a t u r a lp h e n o m e n a a m e r s c e i n t i s t ，1 9 9 0 ： 8 5 1 6 2 【6 r a w a n n a m a k e r p s y c h o a c o u s t i c a l l yo p t i m a ln o i s es h a p i n g a u d i oe n g s o c ， 19 9 2 ，4 0 ：6 - 11 【7 】z 。y l i u ，y l z h a n g ，r 。r a l h a c o m p u t i n gt h es q u a r er o o t so fm a t r i c e sw i t hc e n t r - a ls y m m e t r y m a t h e m a t i c sa n dc o m p u t a t i o n ，2 0 0 7 ，3 2 ：715 7 2 6 【8 】z y l i u ，h d c a o ，h j c h e n an o t eo nc o m p u t i n gm a t r i x v e c t o rp r o d u c t sw i t h g e n e r a l i z e dc e n t r o s y m m e t r i c ( c e n t r o h e r i t i a n ) m a t r i c e s m a t h e m a t i c sa n dc o m p u t a t i o n ，2 0 0 5 ，2 7 ：1 3 3 2 - 1 3 4 5 9 】z y l i u ，h f a b b e n d e r s o m ep r o p e r t i e so fg e n e r a l i z e dk - c e n t r o s y m m e t r i c 俘 m a t r i c e s j o u r n a lc o m p u t a t i o n a la n da p p l i e dm a t h e m a t i c s ，2 0 0 7 ，1 2 ：3 5 6 - 3 6 2 【l0 】 m i c h a e lk n g ，w i l s o nc k w a n i m a g er e s t o r a t i o nb yc o s i n e t r a n s f o r m - b a s e i t e r a t i v er e g u l a r i z a t i o n m a t h e m a t i c sa n dc o m p u t a t i o n ，2 0 0 5 ，16 0 ：4 9 9 - 515 【11 】m n g ，r c h a n ，w t a n g af a s ta l g o r i t h mf o rd e b l u r r i n gm o