矩陣最大線性無關(guān)子塊提取研究

王芳，馬艷麗

(1.安徽外國語學院 公共基礎(chǔ)課教學部，安徽 合肥 231200；2.安徽新華學院 通識教育部，安徽 合肥 230088)

對于求解大型稀疏線性方程組Ax=b，其中A∈Rm×m，x，b∈m×1.文[1]中有以下結(jié)論：

其中，rank(A)=r，A11是矩陣A的一個最大線性無關(guān)子塊，P、Q為相應的置換矩陣，R是任意一個r階的非奇異矩陣.可知，得到M+的關(guān)鍵在于提取矩陣A的一個最大線性無關(guān)子塊A11，本文將給出提取A11及相應的置換矩陣P、Q的算法.

1 相關(guān)定義及引理

定義1 若矩陣A的秩為r，則A必有一個非奇異的子矩陣A11∈Rr×r，稱A11為矩陣A的最大線性無關(guān)子塊.

2 提取A11及相應置換矩陣P,Q的算法

則

故

是齊次線性方程組Λix=0的一個解.其中

算法1：

(1)size(A)=[m,n]，置初始量：m階單位矩陣Im×m,n階單位矩陣In×n，l=2，k=1，s=[1]；

(2)若a11=0，aij≠0，則將Im×m第一行與第i行互換，In×n的第一列與第j列互換，并將互換后的矩陣記作P1與Q1，令A=P1AQ1；

算法2：

(2)置初始量：m階單位矩陣Im×m,n階單位矩陣In×n；

3 數(shù)值實驗

以下數(shù)值實驗均在Intel(R) Core(TM) i5-8265U CPU@1.60GHz 1.80GHz內(nèi)存為8.00 GB的個人計算機上完成，所用軟件為MATLAB R2018a，矩陣來自“Matrix Market”，皆為實數(shù)矩陣.取初始向量x0=0，停機準則為：

數(shù)值實驗2 使用算法2提取以下矩陣的最大線性無關(guān)子塊，其中ε取1.0×10-10，t表示算法2運行時間(單位為秒)，運算結(jié)果見表1..

表1 算法2的運行時間(單位為秒)

數(shù)值實驗3(見文獻[3]) 對于泊松方程

考慮周期邊界條件u(x,0)=u(x,1),u(0,y)=u(1,y),則矩陣A是如下矩陣，其中h=1/m，n=m2，α±=1±dh/2，取m=64，d=10，即得A是4 096×4 096階矩陣.

rank(BBT)=1，rank(CTC)=1，

圖1 數(shù)值實驗2的收斂圖像

4 小 結(jié)

綜上所述，預條件QMR算法與預條件TFQMR算法，預條件GMRES算法是高效的，對于提取大型稀疏矩陣的最大線性無關(guān)子塊A11，算法中ε的取值，對算法有一定的影響.構(gòu)造基于恰當分裂的預條件子時，如果需要提取最大線性無關(guān)子塊A11，代價也是昂貴的.