關(guān)于偽余式與子結(jié)式的矩陣計(jì)算

金 萌

(北京航空航天大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院， 信息、數(shù)學(xué)與行為教育部重點(diǎn)實(shí)驗(yàn)室， 北京 100191)

0 引言

偽余式的計(jì)算是計(jì)算機(jī)代數(shù)中的基本工具之一，是解多項(xiàng)式方程組的三角分解方法中的基本運(yùn)算.文獻(xiàn)[1]給出了改進(jìn)算法,李永彬提出了一種利用構(gòu)造矩陣和高斯消去法來計(jì)算偽余式的算法NewPrem[2],NewPrem在計(jì)算多元多項(xiàng)式的偽余式時(shí)比Maple中已有的算法(prem)效率更高.由于偽余式與特定的矩陣是有聯(lián)系的，我們?cè)噲D用線性代數(shù)中的Dodgson變換來計(jì)算偽余式.子結(jié)式和多項(xiàng)式余式序列是多項(xiàng)式代數(shù)中計(jì)算最大公因子的重要工具之一,關(guān)于子結(jié)式的研究既有理論上也有算法上的改進(jìn)工作.例如Docus L給出了一種優(yōu)化子結(jié)式算法[3]，優(yōu)化策略基于多項(xiàng)式余式序列的計(jì)算；Abdeljaoued J 等研究了子結(jié)式的多種表示形式[4，5]；Akritsa A G等提出了一種用矩陣三角化計(jì)算子結(jié)式的算法[6]；李給出了一種用矩陣構(gòu)造子結(jié)式的新算法[7].文獻(xiàn)[2]中的結(jié)論是促使我們研究用線性代數(shù)計(jì)算偽余式和子結(jié)式的動(dòng)機(jī).

本文的目標(biāo)之一是基于李的思想構(gòu)造一種新的偽余式算法并在Maple中實(shí)現(xiàn)；另一目標(biāo)是對(duì)已有的幾種子結(jié)式矩陣構(gòu)造算法給出一種統(tǒng)一的描述并將其實(shí)現(xiàn).

1 行列式多項(xiàng)式與偽余式

設(shè)R為帶單位元的惟一析因整環(huán)，而F,G∈R[x]為次數(shù)分別為m和n的一元多項(xiàng)式：

(1)

定理1[2]設(shè)F,G∈R[x]如式(1) 所示，則prem(G,F,x)=(-1)ndet(A)，其中A為(n+1)×(n+1)階矩陣，第1行元素為G的系數(shù)，最后m-1行元素為1和-x，中間n-m+1行元素為F的系數(shù)，空白處為零，如下所示

上述定理給出了多項(xiàng)式和矩陣行列式之間的一個(gè)聯(lián)系，這一聯(lián)系可以推廣到多項(xiàng)式與行列式多項(xiàng)式之間，首先需要定義一組多項(xiàng)式的矩陣.

并記為mat(F1,…，F(xiàn)t).對(duì)于任意一組多項(xiàng)式F1,…，F(xiàn)t，命d:=1+maxi{deg(Fi)}，定義F1,…，F(xiàn)t的矩陣為M=(Mij)∈Rt×d，其中當(dāng)deg(Fi)

以上是由多項(xiàng)式組定義矩陣，另外我們也可對(duì)矩陣定義多項(xiàng)式組.

定義2設(shè)t和d為正整數(shù)且t≤d，給定矩陣M=(Mij)∈Rt×d，定義M(j)為

(2)

下述定理描述了兩個(gè)一元多項(xiàng)式的偽余式與行列式多項(xiàng)式之間的聯(lián)系.

定理2[8]設(shè)F,G∈R[x]如式(1)所示，則

prem(G,F,x)=detpol(xn-mF,…,xF,F,G)

稱矩陣mat(xn-mF,…,xF,F,G)為G與F的偽余矩陣，并記為matprem(G,F).

現(xiàn)在我們回顧一下線性代數(shù)中的Dodgson 變換，見算法1.

算法1(Dodgson)

輸入：n×n階矩陣M=(Mij)∈Rn×n，輸出：n×n階矩陣M′滿足條件(3)和(4).

注意，若算法1的輸入矩陣M的所有主子式都非零，則不需要改變主元，此時(shí)S3和S5.1.1.2可以省略.另外，輸出矩陣M′具有如下形式：

(3)

Dodgson變換的一個(gè)重要性質(zhì)是：當(dāng)1≤k

(4)

(5)

利用命題1的證明我們可以構(gòu)造算法計(jì)算偽余式prem(G,F,x)，見算法2.

算法2(DetMatPrem)

輸入：一元多項(xiàng)式F,G∈R[x]，輸出：包含偽余式prem(G,F,x)系數(shù)的數(shù)組[seq(a[m+1-j]，j=0..n-1)].

S1.命m:=deg(F,x);n:=deg(G,x).

S2.若n

S3. 將F，G的系數(shù)按照次數(shù)降序表示為數(shù)組，即命a:=Array(1..n+1,[seq(coeff(G,x,n+1-i),i=1..n+1)]);b:=Array(1..n+1,[seq(coeff(F,x,n+1-i),i=1..n+1)]);(其中Array，seq和coeff都是Maple函數(shù)).

S4. 對(duì)每一1≤k≤m-n+1執(zhí)行下列步驟：S4.1. 對(duì)每一k+1≤i≤m+1執(zhí)行下列步驟：S4.1.1.a[i]:=b[1]a[i]-b[i-k+1]a[k].

2 行列式多項(xiàng)式序列

設(shè)t和d為正整數(shù)且t≤d，對(duì)于矩陣M=(Mij)∈Rt×d，定義Mi×di為M的包含前i行前di列元素的子矩陣，其中1≤i≤t.記Jn為次對(duì)角線上元素為1其他位置元素為零的n階方陣.

定義3設(shè)t，d，M如上所示，定義M關(guān)于L=[(i1,di1),…,(ir,dir)]的行列式多項(xiàng)式序列為：{detpol(Mi×di)：(i,di)∈L},其中1≤i1<…

根據(jù)[8]，G與F的第i個(gè)子結(jié)式等于subresi(G,F,x)=detpol(mat(xm-i-1G,…,xG,G,xn-i-1F,…,xF,F)),0≤i

將mat(xm-1G,…,xG,G,xn-1F,…,xF,F)記為M，又將M的行重新排序得到如下矩陣

M′=mat(xn-1F,xn-2F,…,xm-1F,xm-1G,xm-2F,xm-2G,…,F,G)

(6)

易證M′關(guān)于L=[(k,(m+n+k)/2):k=n-m+2,n-m+4,…,n-m+2m]的行列式多項(xiàng)式序列等于G與F的子結(jié)式序列{subresi(G,F,x):i=0,…,m-1}.

(7)

另外，對(duì)于情形(1)和(3)，設(shè)detpol(Mi×di)關(guān)于x的系數(shù)位于第i′行，則

推論2[6]設(shè)F，G∈R[x]如(1)所示，并假定deg(G)=n≥m=deg(F).又設(shè)M,L如(6)所示，則M關(guān)于L的行列式多項(xiàng)式序列，也即G與F的子結(jié)式序列{subresi(G,F,x)：i=0,…,m-1}可以通過算法1輸出的M′得到.(1)若M的所有主子式都不為零，則

上述定理及推論中使用的是Sylvester矩陣的變形，實(shí)際上我們同樣可以將Bezout矩陣應(yīng)用Dodgson變換來計(jì)算子結(jié)式.下面我們介紹Bezout矩陣與混合Bezout矩陣的定義并證明如何應(yīng)用Dodgson變換來計(jì)算子結(jié)式序列.

定義4設(shè)F，G∈R[x]如(1)所示，定義G與F的Bezout矩陣為(Bij),0≤i,j≤n-1, 其中Bij為式(G(x)F(y)-G(y)F(x))/(x-y)中項(xiàng)xiyj的系數(shù)，并記為Bez(G,F).

定義5設(shè)F，G∈R[x]如(1)所示，并假定deg(G)=n≥m=deg(F).稱按照如下方式構(gòu)造的矩陣M=(Mij)為G與F的混合Bezout矩陣，并記為HBez(G,F)：(1)對(duì)于1≤i≤m,1≤j≤n,Mij等于多項(xiàng)式Km-i+1關(guān)于xn-j的系數(shù)，其中Km-i+1等于(gnxm-i+…+gn-m+i)(fi-1xn-m+i-1+…+f0xn-m)-(gn-m+i-1xn-m+i-1+…+g0)(fmxm-i+…+fi);對(duì)于m+1≤i≤n,1≤j≤n，Mij等于多項(xiàng)式xn-iF(x)關(guān)于xn-j的系數(shù).

L=[(n-m+1,n),(n-m+2,n),…,(n,n)]

(8)

證明：只需要證明第2種情形，情形(1)可類似證明.對(duì)于i=n-m+1,…,n+m，考慮矩陣Hi×n的行列式多項(xiàng)式,易證

(9)

若H的所有主子式都不為零，即det(Mi×i)≠0，1≤i

下面我們給出計(jì)算多項(xiàng)式G與F的行列式多項(xiàng)式序列的算法，即算法3.

算法3(DetPolSeq)

輸入：一元多項(xiàng)式F，G∈R[x]滿足條件deg(G)≥deg(F)，輸出：G與F的行列式多項(xiàng)式序列DPS.

S1.命m:=deg(F,x);n:=deg(G,x).

S2.構(gòu)造矩陣M(M可以是式(6)或推論3中的B,H)及相應(yīng)的L.

S3. 命M′：=Dodgson(M).

S4. 根據(jù)式(7)或(9)計(jì)算行列式多項(xiàng)式序列DPS.

3 實(shí)驗(yàn)結(jié)果

3.1 偽余式的計(jì)算

我們通過實(shí)驗(yàn)比較了3種計(jì)算偽余式的算法：Maple命令prem、李永彬的算法NewPrem以及本文給出的算法DetMatPrem.實(shí)驗(yàn)是在一臺(tái)CPU為3.2 GHz，內(nèi)存512 MB的Pentium 4機(jī)器上完成的，實(shí)驗(yàn)結(jié)果如表1所示.表1中的10個(gè)例子比較長，這里不再給出，而只給出生成多項(xiàng)式的Maple命令：

> G:=randpoly(x,degree=d1,coeffs = proc() randpoly([y,z], degree=d3) end proc);

> F:=randpoly(x,degree=d2,coeffs = proc() randpoly([y,z], degree=d3) end proc);

其中在例1～3中，命d1:= 30，d2:= 8，d3:= 6; 例4～6中命d1:= 30，d2:= 10，d3:= 10；例7～9中命d1:= 30，d2:= 20，d3:= 20; 例10中命d1:= 40，d2:= 20，d3:= 10.

表1 偽余式算法比較

需要說明的是上述3種算法的輸出多項(xiàng)式都不一定是完全展開的，即沒使用Maple命令exapnd.如果使用該命令，那么用時(shí)將更多，比如例7，前兩種算法在600 s內(nèi)均沒有輸出，而DetMatPrem用時(shí)僅為132.860 s.由表1可以看出，算法DetMatPrem的效率通常是最高的，對(duì)于例3和例7，雖然效率低于NewPrem，但優(yōu)于prem.

3.2 子結(jié)式序列的計(jì)算

我們比較了4種子結(jié)式算法：李永彬的SubResLi、Docus的SubResDocus以及基于(6)的算法DetPolSeq1和基于推論3中的矩陣H的算法DetPolSeq2.實(shí)驗(yàn)結(jié)果(時(shí)間單位為s)如表2所示，表2中的8個(gè)例子由如下方式生成：

例11～15:

> G:=randpoly(x,degree=d1,coeffs = proc() randpoly([y,z], degree=d3) end proc);

> F:=randpoly(x,degree=d2,coeffs = proc() randpoly([y,z], degree=d3) end proc);

例16～18:

> G:=randpoly(x,degree=d1,coeffs = proc() randpoly([y,z,w], degree=d3) end proc);

> F:=randpoly(x,degree=d2,coeffs = proc() randpoly([y,z,w], degree=d3) end proc);

其中例11、12中命d1:= 7, d2:= 7, d3:= 3；在例13～15中命 d1:= 8, d2:= 4, d3:= 4；例16中命d1:= 5, d2:= 3, d3:= 3；例17中命d1:= 6, d2:= 3, d3:= 3；例18中命d1:= 7, d2:= 3, d3:= 3.

表2 子結(jié)式算法比較

由表2容易看出，當(dāng)參數(shù)個(gè)數(shù)為2且全次數(shù)不大時(shí)，算法DetPolSeq1和DetPolSeq2比SubResLi和SubResDocus更高效，當(dāng)參數(shù)個(gè)數(shù)為3時(shí)DetPolSeq1是最高效的，盡管Sylvester矩陣比Bezout矩陣復(fù)雜.

4 結(jié)束語

本文研究了偽余式、子結(jié)式與矩陣行列式之間的聯(lián)系并給出了行列式多項(xiàng)式序列的概念，對(duì)用不同類型矩陣構(gòu)造子結(jié)式的算法給出了統(tǒng)一描述，提出了新的偽余式算法DetMatPrem和子結(jié)式算法DetPolSeq并在Maple中實(shí)現(xiàn)，通過多個(gè)隨機(jī)生成的例子將已有的幾種算法進(jìn)行了比較，實(shí)驗(yàn)證明本文提出的算法是高效的.

參考文獻(xiàn)

[1] Wang D. A generalized algorithm for computing characteristic sets[C]. Computer Mathematics: Proceedings of the Fifth Asian Symposium (ASCM 2001), Matsuyama, Japan, 2001.

[2] Li Y B. An alternative algorithm for computing the pseudo-remainder of multivariate polynomials[J]. Applied Mathematics and Computation， 2006, 173(1):484-492.

[3] Ducos L. Optimizations of the subresultant algorithm[J]. Journal of Pure and Applied Algebra. 2000, 145(2): 149-163.

[4]Abdeljaoued J, Diaz-Toca G M, Gonzalez-Vega L. Bézout matrices, subresultants and parameters[C]. MACIS 2007, 2007.

[5] Hou X, Wang D. Subresultants with the Bézout matrix[C]. In:Computer Mathematics-Proceedings of the Fourth Asian Symposium(ASCM 2000), Singapore New Jersey, 2000: 19-28.

[6] Akritas A G, Akritas E K, Malaschonok G I. Matrix computation of subresultant polynomial remainder sequences in integral domains[J]. Reliable Computing,1995, 1(4): 375-381.

[7] Li Y B. A new approach for constructing subresultants[J]. Applied Mathematics and Computation, 2006, 183(1):471-476.

[8] Mishra B. Algorithmic Algebra[M]. Springer, 1993.

[9]Von zur Gathen J, Lucking T. Subresultants revisited[J]. Theoretical Computer Science, 2003, 297(1-3): 199-239.