基于Seysen算法的新型同步格基規(guī)約算法研究

孫全超

(青島科技大學(xué)，山東 青島 266000)

格基規(guī)約的算法及其應(yīng)用，是幾何數(shù)論及組合數(shù)學(xué)領(lǐng)域的核心分支?；狙芯繉?duì)象是格點(diǎn)空間，因此也被稱為格點(diǎn)理論。該理論自創(chuàng)立之初就與若干重要數(shù)學(xué)分支如組合數(shù)學(xué)、泛函分析等有緊密聯(lián)系。尤其是L.Lovász提出著名的Lenstra-Lenstra-Lovász (LLL)算法[1]以來，格基規(guī)約在當(dāng)前很多熱門領(lǐng)域均得到了廣泛而深入的應(yīng)用。

LLL 算法是首個(gè)具有多項(xiàng)式時(shí)間復(fù)雜度的規(guī)約算法，實(shí)用價(jià)值較高。同時(shí)，為進(jìn)一步滿足各類實(shí)際應(yīng)用需要，一系列高效格基規(guī)約算法，如BKZ算法、Seysen算法、Brun算法、對(duì)角規(guī)約算法[2,10]等也于近年被相繼提出。

當(dāng)前以LLL算法為代表的主流格基規(guī)約算法均以最大限度改進(jìn)格基矩陣或其對(duì)偶格基矩陣的基向量長度為目標(biāo)。它們的缺點(diǎn)是僅單純考慮給定格基矩陣的性態(tài)，并未考慮格基矩陣與其對(duì)偶基矩陣的關(guān)聯(lián)。所以，本文提出來一類基于Seysen算法的新型同步格基規(guī)約算法，該算法與傳統(tǒng)LLL算法有本質(zhì)的區(qū)別。而且在一定情況下還要優(yōu)于傳統(tǒng)的LLL算法。

1 LLL算法與Seysen算法

1.1 LLL算法

1.1.1 LLL算法的思想

Lovasz，Lenstra和Lenstra三人最早提出LLL算法，現(xiàn)在它被應(yīng)用到整數(shù)規(guī)劃、密碼學(xué)、數(shù)論等領(lǐng)域，并起到了許多重要的應(yīng)用。它用到的是格矩陣A的一種QRZ分解：

A=QRZ-1

(1)

其中Q是正交矩陣，R是上三角陣，Z是單模陣。關(guān)于單模陣的定義如下：

定義1 如果對(duì)于任意非奇異整數(shù)矩陣M，有det(M)=1或det(M)=-1則M被稱為單模陣。

由定義，我們可以很容易地得出，非奇異整數(shù)矩陣Z是單模陣的充要條件是Z-1也是一個(gè)整數(shù)矩陣。傳統(tǒng)的LLL算法以DU的形式來計(jì)算 ，其中D是一個(gè)正定的對(duì)角矩陣，而U是單位上三角矩陣。而且R=DU的列構(gòu)成一組約減基(reducedbasis)關(guān)于約減基的定義如下：

定義2 上三角矩陣R=DU的列被稱為一組約減基，若

其中w是一個(gè)滿足1/4≤w≤1的參數(shù)

把(1)里的R代入，則我們可以得到：

由于Q是正交矩陣，不改變矩陣2-范數(shù)；而Z是單模陣，即整數(shù)向量間F的雙射，因此上面的問題就等價(jià)于

1)條件(1)：矩陣R的對(duì)角元素的絕對(duì)值是要相對(duì)比較大的，在一定意義下對(duì)角元比較占優(yōu)，這樣的性質(zhì)可以讓矩陣更加穩(wěn)定，也更接近于一個(gè)對(duì)角陣。

2)條件(2)：對(duì)角線上的元素不會(huì)減小得太快，也可以認(rèn)為是某種意義下的遞增。眾所周知，矩陣末尾的元素越大，需要列舉的次數(shù)就越少，因此在作矩陣變換的時(shí)候,要盡量把大的元素往矩陣的右下方進(jìn)行置換。

1.1.2 傳統(tǒng)LLL算法

傳統(tǒng)的LLL算法采用向量及子空間投影的方式表述，形式太過復(fù)雜。為便于理解，本文給出和傳統(tǒng)LLL算法數(shù)學(xué)等價(jià)的矩陣形式描述。

設(shè)待約減矩陣為A∈Rm×n，則該算法首先運(yùn)用Gram-Schmidt正交化將A分解如下：

A=QD1/2U

(4)

這里Q∈Rm×n為列正交矩陣，D=diag(d1,d2,…dn)為正對(duì)角陣，U=[ui,j]為對(duì)角元素全為1的上三角陣。若A的分解(4)滿足下列條件，則A的所有列向量構(gòu)成L(A)的一組LLL約減基，或等價(jià)的把A稱為為一個(gè)LLL約減陣。

子過程2(SwapRestore) 對(duì)于分解式中的矩陣D和U，按下式更新D中元素并計(jì)算ξ：

因此

由上式可知，若當(dāng)前矩陣U不滿足條件(6)則可通過調(diào)用子過程2，使其滿足條件(6)。

分析易知，若算法在有限步內(nèi)結(jié)束，則最終獲得的基矩陣一定滿足LLL約減定義。文獻(xiàn)同時(shí)給出了LLL算法的計(jì)算復(fù)雜度：若初始基矩陣A為整數(shù)矩陣，則該算法的復(fù)雜度為O(mn3logD)，其中D為A的所有列向量中最長向量的長度。

原始LLL 算法的主要優(yōu)點(diǎn)為：當(dāng)初始矩陣為整數(shù)或有理數(shù)矩陣時(shí)，算法的所有操作都是有理數(shù)間的四則運(yùn)算，可實(shí)現(xiàn)無誤差運(yùn)算。因此該算法適用于經(jīng)典數(shù)學(xué)理論中的內(nèi)容，如有理多項(xiàng)式的有理分解等。但對(duì)實(shí)數(shù)或復(fù)數(shù)型初始基矩陣，由于Gram-Schmidt 正交化及子過程2，均數(shù)值計(jì)算不穩(wěn)定，該算法在實(shí)際執(zhí)行過程中會(huì)產(chǎn)生較大的計(jì)算誤差，不僅計(jì)算結(jié)果可能不是LLL 的，而且在最壞情況下算法甚至無法終止。

1.2 Seysen算法

1.2.1 對(duì)偶格點(diǎn)空間

設(shè)L為一個(gè)n維實(shí)數(shù)格點(diǎn)空間，則L的對(duì)偶空間L*定義如下：

格點(diǎn)空間與其對(duì)偶格點(diǎn)空間有緊密聯(lián)系。如下給出兩個(gè)基本性質(zhì)：

(L*)*=L,det(L*)=1/det(L)

給定原格點(diǎn)空間上的一個(gè)基矩陣B，則所謂對(duì)偶格點(diǎn)基約減算法即為將格點(diǎn)基約減算法作用于對(duì)偶基矩陣B*。與前文作用于原格點(diǎn)空間的約減算法類似，利用對(duì)偶格點(diǎn)約減算法同樣可以獲得原格點(diǎn)空間中一組約減質(zhì)量較高的基。設(shè)Z*為約法作用于對(duì)偶基矩陣B*求得的相應(yīng)單模變換矩陣，則原格點(diǎn)空間中的對(duì)應(yīng)約減基由下式給出：

1.2.2 Seysen規(guī)約

上述優(yōu)化問題求解十分困難，而Seysen算法提供了一個(gè)近似求解的方法。

不難證明相應(yīng)對(duì)偶基矩陣

注意到，B和C其余列向量不變。因此，執(zhí)行規(guī)約操作后，有：

Seysen 算法的核心是：在每次迭代中使S(B) 得以最大程度下降，即求解如下優(yōu)化問題

不難求出，上述問題最優(yōu)解為：

算法執(zhí)行到S(B)無法繼續(xù)下降為止。

易知，若Seysen算法終止，則得到的基矩陣滿足：

Seysen 算法在大量數(shù)值仿真中的表現(xiàn)優(yōu)于基于 LLL 迭代策略的傳統(tǒng)格基規(guī)約算法，但對(duì) Seysen 算法的理論分析目前尚無進(jìn)展。特殊例子表明，算法在最差情形下具有指數(shù)時(shí)間復(fù)雜度。如何對(duì)該算法進(jìn)行松弛變形，在盡量不犧牲規(guī)約強(qiáng)度的條件下將計(jì)算復(fù)雜度改進(jìn)至多項(xiàng)式時(shí)間是對(duì)該算法改進(jìn)的關(guān)鍵。

2 基于Seysen算法的新型同步格基規(guī)約算法

2.1 對(duì)Seysen 算法的改進(jìn)及分析

當(dāng)前以 LLL 算法為代表的主流格基規(guī)約算法均以最大限度改進(jìn)格基矩陣或其對(duì)偶格基矩陣的基向量長度為目標(biāo)。它們的缺點(diǎn)是僅單純考慮給定格基矩陣的性態(tài)，并未考慮格基矩陣與其對(duì)偶基矩陣的關(guān)聯(lián)。Seysen 算法是當(dāng)前僅有的一類同步格基規(guī)約算法。然而盡管Seysen數(shù)值表現(xiàn)優(yōu)異，但其計(jì)算復(fù)雜度方面的分析目前尚無任何理論結(jié)果。大部分情形下該算法表現(xiàn)優(yōu)異，但個(gè)別情形下該算法效率較低。在最壞情況下，具有指數(shù)階時(shí)間復(fù)雜度。

Seysen算法是基于正交測(cè)量，S(B)盡管基本矩陣和其雙重基礎(chǔ)矩陣,注意兼顧但它不是直觀的幾何意義。新算法打算采用更明顯的幾何意義類型向量正交測(cè)量：

作為新型格基規(guī)約算法的計(jì)算依據(jù)。新算法的設(shè)計(jì)思路為：在每次迭代初始時(shí)，設(shè)計(jì)一類貪婪策略選擇基矩陣 B 的列向量bi,bj并選擇合理整數(shù)步長λ對(duì)bj作尺度規(guī)約將其更新為bj=bj-λbi，以使得該次迭代結(jié)束后正交度量W1(B)或W2(B)得以最大程度下降。新算法期望具有多項(xiàng)式計(jì)算復(fù)雜度。首先給出新型規(guī)約基定義如下：

2.2 改進(jìn)型Seysen 規(guī)約算法的計(jì)算復(fù)雜度分析

由Cauchy-Schwarz不等式而知：

因此，在算法迭代過程中，上式始終成立。

接下來，給出程序最外層while循環(huán)的執(zhí)行次數(shù)上界當(dāng)同步規(guī)約條件不滿足，即

時(shí)，執(zhí)行規(guī)約操作，并進(jìn)入下次while循環(huán)。不難得出，當(dāng)執(zhí)行完一次規(guī)約操作后，得到新的基矩陣B′滿足：

3 數(shù)值結(jié)果比較

本節(jié)，我們通過數(shù)值實(shí)驗(yàn)比較LLL算法、原Seysen算法和本文提出的改進(jìn)Seysen算法的規(guī)約質(zhì)量和執(zhí)行效率，使用軟件為MATLAB 2012b。

在多天線系統(tǒng)中，信道矩陣通常為方陣，其元素服從獨(dú)立同分布的標(biāo)準(zhǔn)正態(tài)分布。為了求解各類算法的平均規(guī)約質(zhì)量和執(zhí)行效率，先利用MATLAB生成一系列隨機(jī)矩陣，其階數(shù)范圍為1～50階。對(duì)每個(gè)階數(shù)，生成1000個(gè)測(cè)試用隨機(jī)矩陣，再分別將LLL算法(w=0.99)，原始Seysen算法、改進(jìn)Seysen算法(w分別取0.99，0.95，0.9)得到對(duì)應(yīng)的LLL和Seysen規(guī)約矩陣。最后，通過統(tǒng)計(jì)規(guī)約矩陣平均正交度和算法平均cpu執(zhí)行時(shí)間，比較各算法的規(guī)約質(zhì)量和執(zhí)行效率。

對(duì)于各階信道矩陣，經(jīng)LLL算法、原始Seysen算法和改進(jìn)Seysen算法作用得到的規(guī)約矩陣的平均正交度如圖1。

圖1表明，隨著矩陣階數(shù)的增大，各類算法求得的規(guī)約矩陣的Seysen正交度S(B)的值越來越高。對(duì)各階矩陣，原Seysen算法規(guī)約質(zhì)量最高，改進(jìn)Seysen算法次之，而LLL算法對(duì)格基正交度的改善效果最差。當(dāng)規(guī)約參數(shù)w取為0.99時(shí)，改進(jìn)Seysen算法與原Seysen算法規(guī)約質(zhì)量相當(dāng)，隨著w的減小，改進(jìn)Seysen算法的對(duì)格基正交度的改善效果降低。

圖2比較了各類算法的平均運(yùn)行時(shí)間。該圖表明，隨著矩陣階數(shù)的增加，各類算法的平均運(yùn)行時(shí)間逐漸增加。對(duì)各階矩陣，LLL算法運(yùn)行速度最快，改進(jìn)Seysen算法次之，原Seysen算法最慢。當(dāng)規(guī)約參數(shù)w取為0.99時(shí)，改進(jìn)Seysen算法與原Seysen算法運(yùn)行時(shí)間相當(dāng)，隨著w的減小，改進(jìn)Seysen算法需要的運(yùn)行時(shí)間逐漸降低。

圖1 LLL算法(w=0.99)、原Seysen算法、改進(jìn)Seysen算法(w分別取0.99，0.95，0.9)規(guī)約矩陣的平均正交度Fig.1 LLL algorithm (w = 0.99),the original Seysen algorithm, improved Seysen algorithm (w,respectively,take 0.99,0.95,0.9) protocol matrix of the average degree of orthogonality

圖2 LLL算法(w=0.99)、原Seysen算法、改進(jìn)Seysen算法(w分別取0.99，0.95，0.9)的平均運(yùn)行時(shí)間Fig.2 LLL algorithm (w = 0.99),the original Seysen algorithm, improved Seysen algorithm (w,respectively,take 0.99,0.95,0.9) the average run time

數(shù)值結(jié)果表明，當(dāng)w=0.99時(shí)，改進(jìn)Seysen算法與原Seysen算法數(shù)值表現(xiàn)一致，其規(guī)約質(zhì)量優(yōu)于LLL算法，但需要的運(yùn)行時(shí)間LLL算法多。隨著規(guī)約參數(shù)w的減少，改進(jìn)Seysen算法的運(yùn)行時(shí)間得以改善，但會(huì)導(dǎo)致規(guī)約質(zhì)量降低。在實(shí)際應(yīng)用中，應(yīng)根據(jù)實(shí)際需要選擇合適的規(guī)約參數(shù)w。

4 總結(jié)

本文首先論述了傳統(tǒng)LLL算法和Seysen算法，其次提出了一種基于Seysen算法的改進(jìn)型Seysen算法，爾后對(duì)比傳統(tǒng)LLL算法、Seysen算法與改進(jìn)型Seysen算法得出結(jié)論：這種改進(jìn)型Seysen算法不論在算法復(fù)雜度，還是在其約減能力方面都要優(yōu)于傳統(tǒng)LLL算法。既然傳統(tǒng)的LLL算法可以應(yīng)用到密碼學(xué)、信號(hào)處理等實(shí)際應(yīng)用中，那么本文提出的新算法也可以勝任。

現(xiàn)在的基于Seysen算法的新型格基約減算法雖然已經(jīng)給出，但仍存在一定的缺陷。在普通的正交度量檢驗(yàn)中，本文提出的改進(jìn)型Seysen算法的規(guī)約質(zhì)量遜于Seysen算法。需要進(jìn)一步的優(yōu)化。