基于初等因子法的線性代數(shù)復(fù)矩陣相似標(biāo)準(zhǔn)型研究

宋 永

線性代數(shù)復(fù)矩陣的運(yùn)算在信號(hào)處理、雷達(dá)成像、人工智能、衛(wèi)星通信等科技領(lǐng)域都具有重要作用，憑借著簡(jiǎn)明、直觀的表達(dá)方式及穩(wěn)定可靠的運(yùn)算速度，已經(jīng)成為現(xiàn)代工程技術(shù)中的重要數(shù)學(xué)求解工具［1].線性代數(shù)復(fù)矩陣求解的方式很多，包括分解、乘法和求逆，其中，線性代數(shù)復(fù)矩陣的相似標(biāo)準(zhǔn)型是解決這些問題的關(guān)鍵.國(guó)外對(duì)于基于初等因子法的線性代數(shù)復(fù)矩陣相似標(biāo)準(zhǔn)型研究通常采用Cholesky分解算法，上世紀(jì)末期，研究者基于Cholesky分解算法設(shè)計(jì)了一種線性代數(shù)復(fù)矩陣相似標(biāo)準(zhǔn)型存在性的研究方法，并對(duì)其進(jìn)行了實(shí)驗(yàn)驗(yàn)證，Cholesky分解算法的運(yùn)算量非常小，在應(yīng)用過程中方便硬件的實(shí)現(xiàn)［2]；國(guó)內(nèi)學(xué)者最初將QR分解算法應(yīng)用到基于初等因子法的線性代數(shù)復(fù)矩陣相似標(biāo)準(zhǔn)型研究中，具有較高的并行度，在硬件設(shè)計(jì)中具有重要應(yīng)用［3].

許成亮等人［4]根據(jù)線性代數(shù)變換相似性與復(fù)矩陣相似性之間的等價(jià)關(guān)系，利用任意域上位移算子與一般算子，推導(dǎo)出線性代數(shù)復(fù)矩陣中相似標(biāo)準(zhǔn)型的存在性，并將其推廣到任意域上，求出廣義意義上的相似標(biāo)準(zhǔn)型；梁海華等人［5]考慮到一類帶非負(fù)系數(shù)矩陣的復(fù)雜性，當(dāng)矩陣線性增長(zhǎng)時(shí)，會(huì)具有奇異性，利用矩陣的初等變換法建立了解的存在性充分條件，并給出實(shí)例來證明正解存在性的應(yīng)用.

基于以上研究背景，本文研究了線性代數(shù)復(fù)矩陣的相似標(biāo)準(zhǔn)型存在性，以簡(jiǎn)化線性代數(shù)復(fù)矩陣的求解過程.

1 優(yōu)化線性代數(shù)復(fù)矩陣運(yùn)算算法

針對(duì)高速、高并行、低資源消耗系統(tǒng)對(duì)線性代數(shù)復(fù)矩陣計(jì)算性能的要求［6]，對(duì)線性代數(shù)復(fù)矩陣的運(yùn)算算法進(jìn)行了研究與比較.將線性代數(shù)復(fù)矩陣運(yùn)算算法直接應(yīng)用到矩陣求解計(jì)算中，具有諸多缺點(diǎn).在矩陣的QR分解算法中，存在許多復(fù)雜的計(jì)算過程，如平方根運(yùn)算、除法運(yùn)算等，而傳統(tǒng)的LU分解算法包含了大量的消元計(jì)算和迭代計(jì)算過程.用QR分解算法和LU分解算法的逆算法，首先對(duì)線性代數(shù)復(fù)矩陣進(jìn)行分解運(yùn)算，然后對(duì)分解后得到的兩個(gè)中間矩陣進(jìn)行逆運(yùn)算，最后將兩個(gè)逆矩陣相乘得到線性代數(shù)復(fù)矩陣的逆矩陣.線性代數(shù)復(fù)矩陣的全分解逆過程具有計(jì)算量大、中間的迭代操作多、并行度低、資源消耗高以及運(yùn)行時(shí)間長(zhǎng)的問題［7]，因此采用按位替換法來求解線性代數(shù)復(fù)矩陣.

假設(shè)存在線性代數(shù)復(fù)矩陣：

A表示所有主子式中不為0的n階方陣，aij為第i行、第j列的元素，其中i，j=1，2，3，…，n.依據(jù)按位替換法來求解線性代數(shù)復(fù)矩陣，先對(duì)待求解的線性代數(shù)復(fù)矩陣求解約化系數(shù)，得到線性代數(shù)復(fù)矩陣的n階方陣N，具體的計(jì)算過程為：

采用公式（2）得到約化系數(shù)n階方陣N的第1行第1列元素：

式中：i和j的取值從2開始，通常取正整數(shù).

根據(jù)公式（3）得到約化系數(shù)n階方陣N的對(duì)角元素為：

式中：k的取值為k=2，3，…，i?1，i的取值為i=2，3，…，m.

根據(jù)公式（4）計(jì)算約化系數(shù)n階方陣N的下三角元素為：

式中：i的取值為i=2，3，…，m?1，j的取值為j=i+1，i+2，…，m.

基于以上步驟，得到約化系數(shù)n階方陣N，表示為：

與線性代數(shù)復(fù)矩陣的傳統(tǒng)求解方法不同的是，按位替換法［8]計(jì)算出約化系數(shù)n階方陣N之后，可以直接求解出線性代數(shù)復(fù)矩陣A分解后的三角矩陣和上三角矩陣，最后將兩者相乘得到線性代數(shù)復(fù)矩陣A的解.

線性代數(shù)復(fù)矩陣的計(jì)算復(fù)雜度［9]是比較計(jì)算功耗與計(jì)算速度的重要指標(biāo).在算法的優(yōu)化設(shè)計(jì)中，線性代數(shù)復(fù)矩陣的計(jì)算復(fù)雜度包括空間復(fù)雜度和時(shí)間復(fù)雜度.對(duì)于高性能運(yùn)算算法的設(shè)計(jì)，關(guān)鍵在于根據(jù)算法應(yīng)用的不同領(lǐng)域和應(yīng)用平臺(tái)來改進(jìn)運(yùn)算算法，從而實(shí)現(xiàn)內(nèi)容和體系結(jié)構(gòu)的整體優(yōu)化.評(píng)估線性代數(shù)復(fù)矩陣性能的一個(gè)重要指標(biāo)應(yīng)該是復(fù)矩陣本身的運(yùn)行次數(shù)，運(yùn)算量也可表示為線性代數(shù)復(fù)矩陣執(zhí)行時(shí)間的長(zhǎng)度，它與資源存取次數(shù)和邏輯切換次數(shù)有直接關(guān)系.

對(duì)于高速、高并行、低資源消耗的高性能線性代數(shù)復(fù)矩陣的優(yōu)化設(shè)計(jì)而言，線性代數(shù)復(fù)矩陣的空間復(fù)雜度主要體現(xiàn)在計(jì)算次數(shù)和計(jì)算類型上，而時(shí)間復(fù)雜度則主要體現(xiàn)在計(jì)算的全過程中.若線性代數(shù)復(fù)矩陣的計(jì)算過程比較簡(jiǎn)單，且具有較高的并行性，將大大降低線性代數(shù)復(fù)矩陣在時(shí)間和空間上的復(fù)雜性.

以上分析了線性代數(shù)復(fù)矩陣的求解過程，在計(jì)算過程中可以降低復(fù)雜度，同時(shí)具有較高的并行性，節(jié)省大量的資源能耗，在完成線性代數(shù)復(fù)矩陣求解的基礎(chǔ)上，證明了線性代數(shù)復(fù)矩陣的相似標(biāo)準(zhǔn)型存在性.

2 證明線性代數(shù)復(fù)矩陣的相似標(biāo)準(zhǔn)型存在性

2.1 線性代數(shù)復(fù)矩陣的相似標(biāo)準(zhǔn)型

人們?cè)谇蠼饩€性代數(shù)復(fù)矩陣時(shí)往往希望采用簡(jiǎn)單的計(jì)算步驟，在線性代數(shù)復(fù)矩陣中，其目的就是將線性代數(shù)空間分解成為一個(gè)個(gè)子空間的直和，找到線性代數(shù)復(fù)矩陣的標(biāo)準(zhǔn)型.而相似標(biāo)準(zhǔn)型是對(duì)線性代數(shù)復(fù)矩陣的一種精細(xì)分解，對(duì)研究線性代數(shù)復(fù)矩陣的特性、線性代數(shù)復(fù)矩陣函數(shù)具有重要作用.在線性代數(shù)中，證明復(fù)矩陣的相似標(biāo)準(zhǔn)型存在性都是構(gòu)造出來的，通常有兩種形式：

①根據(jù)線性代數(shù)復(fù)矩陣的特征多項(xiàng)式得到矩陣的準(zhǔn)素分解和循環(huán)分解，再推導(dǎo)出線性代數(shù)復(fù)矩陣A的相似標(biāo)準(zhǔn)型；

②將λ?線性代數(shù)復(fù)矩陣的理論應(yīng)用到A的特征矩陣中，得到矩陣A的標(biāo)準(zhǔn)型.

以上兩種形式的優(yōu)點(diǎn)是只給出了線性代數(shù)復(fù)矩陣A的相似標(biāo)準(zhǔn)型的具體步驟，但無法從根本上說明線性代數(shù)復(fù)矩陣為什么會(huì)有相似標(biāo)準(zhǔn)型.本文利用模理論的相關(guān)知識(shí)，證明線性代數(shù)復(fù)矩陣存在相似標(biāo)準(zhǔn)型.

假設(shè)存在整數(shù)環(huán)Z與加群G，對(duì)任意一個(gè)元素n,m∈Z，u,v∈G，整數(shù)環(huán)Z與加群G的元素之間存在如下關(guān)系：

將上述關(guān)系進(jìn)行一般化處理，即一個(gè)整數(shù)環(huán)作用到一個(gè)加群上，就可以得到模的概念.

定義1［10]：假設(shè)R是一個(gè)具有單位元1的整數(shù)環(huán)，M是加群，同時(shí)還存在R×M到M之間的運(yùn)算°，如果針對(duì)a,b∈R，u,v∈M，R×M到M之間的運(yùn)算°就會(huì)滿足下列關(guān)系：

因此，稱M是整數(shù)環(huán)R上的模，通常將其記作R?模M，那么加群G很顯然就是一個(gè)Z?模.

在上述推導(dǎo)的基礎(chǔ)上，文中給出下列定義.

定義2［11]：R?模M的子集N又可以被稱為M的R?子模，如果存在R°N?N，那么就可以推導(dǎo)出R°N={a1u1+a2u2+…+anun|ai∈.

定義3［12]：假設(shè)N是R?模M的R?子模，針對(duì)商加群中，規(guī)定R×到的運(yùn)算符號(hào)為?，運(yùn)算過程為a?( )

u+N=a°u+N，a∈R，u∈M，那么就可以得到是關(guān)于?運(yùn)算的R?模，并將其稱為R?模M關(guān)于R?子模的商模.

定義4［13]：假設(shè)M是R?模，Mi是M的子模，如果M滿足下列關(guān)系：

①M(fèi)=M1+M2+…+Mt，m∈M，m=m1+m2+…+mt，mi∈Mi；

那么就可以將R?模M稱為子模M1+…+Mt的直和.

引理1［14]：有限交換群G可以唯一分解為素?cái)?shù)冪循環(huán)群的和，可以假設(shè)它的階為n=是不同的素?cái)?shù)，那么就存在：

①G=G11⊕G12⊕…⊕G1k1⊕G21⊕…⊕Gsk，其中Gij表示階為pnij

i的循環(huán)群；

在引理1的基礎(chǔ)上，可以輕松得到引理2.

引理2［15]：假設(shè)R?模M是加群，就會(huì)得到下列事實(shí)：

①如果元素g的階是t，( )t,s=1，那么sg的階也是t，同時(shí)還存在；

②如果g1+g2+…+gm=0，且gi的階ti兩兩互素，那么對(duì)于所有的元素i都存在gi= 0.

2.2 主要結(jié)果

線性代數(shù)矩陣的初等因子組為：λ?1，λ2+1，其無法分解為一次多項(xiàng)冪，無法轉(zhuǎn)化成矩陣標(biāo)準(zhǔn)型.為此，引入，其中pi是線性代數(shù)矩陣中不同的素?cái)?shù)，所以存在：

①M(fèi)=M1⊕M2⊕…⊕Mt，其 中，Mi是Z?子模，Mi中元素的階為pi的冪；

②如 果M=M1⊕M2⊕…⊕Mt=M′1⊕M′2⊕…⊕M′t，則在重新調(diào)整腳碼之后，就有Mi≡M′i.

證明，如果存在n=pm，就會(huì)使下列結(jié)論成立：

①M(fèi)=Z°m1⊕Z°m2⊕…⊕Z°mk；

②如果M=Z°m1⊕Z°m2⊕…⊕Z°mk=Z°h1⊕Z°h2⊕…⊕Z°hs.

那么必定存在k=s，并且適當(dāng)重新排列腳碼之后，可以得到Z°mi≡Z°hi.

然而，事實(shí)上，M存在有限生成元集，假設(shè)是M的兩個(gè)元素個(gè)數(shù)相等的生成元素集合，相應(yīng)的階集合是，如 果 存 在m1+m2+…+mk＜l1+l2+…lk，就可以稱.然后選取一個(gè)元素個(gè)數(shù)最少并且在以上關(guān)系條件下是最小的生成元素集合，可以嘗試記作，其中對(duì)應(yīng)的階數(shù)為，最 后 有M=Z°g1+…+Z°gk.

根據(jù)上述證明步驟可知，G是M的生成元素集合，但是，由于存在psmj gj=lj gj≠0，所以ps＜prj.又因?yàn)閜sg′j= 0，g′j的階≤ps，因此有g(shù)′j的階＜prj，那么G小于生成元素集合，這與的定義是相互矛盾的，因此有M=Z°m1⊕Z°m2⊕…⊕Z°mk，從而完成了①的證明.證明了線性代數(shù)復(fù)矩陣都存在相似標(biāo)準(zhǔn)型.

由于Euclid環(huán)屬于主要的理想整數(shù)環(huán)，而且具有上述證明中用到的Z的性質(zhì)，因此該證明可以推廣到由主理想整數(shù)環(huán)作用于加群之后所得到的模.

3 總結(jié)與展望

3.1 總結(jié)

本文提出了基于初等因子法的線性代數(shù)復(fù)矩陣相似標(biāo)準(zhǔn)型，在分析線性代數(shù)復(fù)矩陣求解的基礎(chǔ)上，優(yōu)化了線性代數(shù)復(fù)矩陣運(yùn)算算法，在算法優(yōu)化過程中，主要是由線性代數(shù)復(fù)矩陣的運(yùn)算單元、控制單元、交叉匹配模塊、地址生成單元以及存儲(chǔ)單元等多個(gè)部分組成的，一般情況下，可用來計(jì)算16到128之間的2n階單精度線性代數(shù)復(fù)數(shù)矩陣.

通過對(duì)線性代數(shù)復(fù)矩陣的相似標(biāo)準(zhǔn)型進(jìn)行性能分析和驗(yàn)證，本文提出的定理可以在線性代數(shù)復(fù)矩陣求解的基礎(chǔ)上滿足相似標(biāo)準(zhǔn)型的處理速度快、運(yùn)算性能高、計(jì)算準(zhǔn)確率高等要求，從而證明了線性代數(shù)復(fù)矩陣存在相似標(biāo)準(zhǔn)型.本研究的創(chuàng)新點(diǎn)如下：

（1）研究了線性代數(shù)復(fù)矩陣在運(yùn)算過程中的運(yùn)算原理和算法，并對(duì)其進(jìn)行了對(duì)比和分析，采用原位替換算法對(duì)線性代數(shù)復(fù)矩陣進(jìn)行了逆運(yùn)算，同時(shí)，基于線性代數(shù)復(fù)矩陣求逆過程中實(shí)部矩陣與虛部矩陣之間的相互交叉運(yùn)算，對(duì)線性代數(shù)復(fù)矩陣的各個(gè)運(yùn)算模式和存儲(chǔ)模式進(jìn)行了優(yōu)化設(shè)計(jì)，并且在滿足線性代數(shù)復(fù)矩陣運(yùn)算性能的前提下，減少運(yùn)算過程中的資源消耗.

（2）在線性代數(shù)復(fù)矩陣的相似標(biāo)準(zhǔn)型存在性證明中，本文提出了一個(gè)針對(duì)線性代數(shù)復(fù)矩陣求解的定理，在保證并行度高且高維計(jì)算的條件下，平衡了線性代數(shù)復(fù)矩陣在資源消耗、運(yùn)算速度、元素安全以及存儲(chǔ)接口上的問題.通過將線性代數(shù)復(fù)矩陣求解算法與數(shù)據(jù)存儲(chǔ)方式相結(jié)合的形式，采用線性代數(shù)復(fù)矩陣求解模塊中的運(yùn)算結(jié)構(gòu)復(fù)用、模塊復(fù)用，充分開拓出線性代數(shù)復(fù)矩陣存在相似標(biāo)準(zhǔn)型的并行度，從而提高相似標(biāo)準(zhǔn)型的求解性能.

3.2 展望

本文在證明線性代數(shù)復(fù)矩陣存在相似標(biāo)準(zhǔn)型的過程中還存在一些不足，具有一定的改進(jìn)空間，對(duì)于線性代數(shù)復(fù)矩陣存在相似標(biāo)準(zhǔn)型的研究還可以作進(jìn)一步地優(yōu)化，在以后的研究中，優(yōu)化工作主要有以下幾點(diǎn).

（1）本文在證明線性代數(shù)復(fù)矩陣存在相似標(biāo)準(zhǔn)型過程中只針對(duì)二階矩陣，今后還可以適當(dāng)作進(jìn)一步改進(jìn)，將線性代數(shù)復(fù)矩陣是否存在相似標(biāo)準(zhǔn)型這一問題擴(kuò)展為任意維度的證明中.

（2）本文在證明線性代數(shù)復(fù)矩陣存在相似標(biāo)準(zhǔn)型過程中只考慮到線性代數(shù)復(fù)矩陣是否存在相似標(biāo)準(zhǔn)型的求逆方案，在后續(xù)的研究中可以適當(dāng)集成多種運(yùn)算方案，例如實(shí)數(shù)矩陣與復(fù)數(shù)矩陣相乘、逆求解實(shí)數(shù)矩陣以及矩陣間的轉(zhuǎn)置運(yùn)算等，從而實(shí)現(xiàn)線性代數(shù)復(fù)矩陣運(yùn)算資源的極大化利用.

（3）針對(duì)維度較大的線性代數(shù)復(fù)矩陣，可以嘗試將本文的證明過程與分塊矩陣的求解相結(jié)合，將待求解的線性代數(shù)復(fù)矩陣進(jìn)行分塊處理，對(duì)單個(gè)線性代數(shù)復(fù)矩陣塊采用寄存器堆緩存的方式來求解線性代數(shù)復(fù)矩陣，從而平衡線性代數(shù)復(fù)矩陣的存儲(chǔ)接口，分塊矩陣的求解方式對(duì)大維度的線性代數(shù)復(fù)矩陣求解具有非常強(qiáng)的可拓展性和實(shí)用性.

（4）在今后的研究中，可以將大維度的線性代數(shù)復(fù)矩陣求解作為證明的基礎(chǔ)，進(jìn)而證明線性代數(shù)復(fù)矩陣中存在相似標(biāo)準(zhǔn)型.