改进的高斯消元法在伪余伪除算法

改进的高斯消元法在伪余伪除算法

0伪除运算算法伪除是计算机代代相传中最常用的计算之一，在计算许多消去方法中起着重要作用。在吴法的计算功能列的情况下，特别是在计算特征列时，重复伪除操作方法计算伪有所除的函数，以达到消元的目的。文献通过只计算一种新型矩阵的行列式的伪除算法(newprem)。本文在改进了newprem中利用高斯消元法的方式,尽量可能地克服过原算法中程膨胀,消除冗余运算。1明确jhf线l-mf,xk的伪余设R是一个唯一分解整环,关于n个变元x1,…,xn系数取值范围在R的多项式环为R或简写为R[X]。对于任意给定的R[X]上的两个多项式G和F和变元xk,把G和F看作关于xk的单变元多项式,那么G和F可以写成:G=G0xmkmk+G1xm-1km−1k+…+GmF=F0xnknk+F1xn-1kn−1k+…+Fn其中m:=deg(G,x),n:=deg(F,x),Fi,Gi∈R。F0是F的导系数,用lc(F,xk)来表示或简写为I,即I=coef(F,xdeg(F,xk)kdeg(F,xk)k)。如果F≠0而且m≥n,那么G对F的伪余perm(G,F,xk)可以用如下方法来计算。首先令R=G,然后重复以下步骤直到r=deg(R,xk)<n:R←IR-R0xr-nkF其中R0=lc(R,xk),因为r在每个循环中都严格下降,所以该程序必定终止。最后得到两个R[X]中的多项式Q和R满足下列关系:IqG=QF+R(1)这里q=max(l-m+1,0),deg(R,xk)<m,deg(Q,xk)=max(l-m,-1)称(1)式为伪余公式,Q为G对F关于xk的伪商,R为G对F关于xk的伪余式,分别记为pquo(G,F,xk)与prem(G,F,xk)。事实上,(1)式中多项式Q与R由G和F唯一确定。以上算法,在现在流行的计算机代数系统Maple中由prem来实现。2辅助算法的更实用性文献中构造了一种新型的矩阵(即下文中的(2)),可以通过计算此矩阵的行列式的值来得到伪余式。但是文献中的newprem算法在计算行列式的值时,采用了一般的高斯消元,对这个特殊问题,效率较低,并且存在着冗余运算,使得程序并不实用。本文针对原算法的缺陷,作了针对性的改进,提出一个更为实用的算法newprem2。[G0G1⋯Gn⋯Gm-1GmF0F1⋯Fn-1FnF0F1⋯Fn-1Fn⋮⋮F0F1⋯Fn-1Fn1-xk⋮⋮⋯1-xk〗(2)⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢G0F0⋮⋮⋯G1F1F0⋯⋯F1GnFn−1⋯F0⋯FnFn−1F11Fn⋯−xkGm−1Fn−11Gm⋮Fn⋮−xk〗(2)首先,介绍一种介于一般高斯消元和不带分式高斯消元之间的高斯消元方法,称之为GCD高斯消元。具体算法如下:det矩阵的计算步骤1对第i(i=1,…,m-n+2)列选择一个主行;步骤2交换主行和非主行的位置使得主行位于第i行;步骤3对Ai,j元素不为零的非主行(j=2,…,m+1)做:temp:=gcd(Ai,i,Ai,j)colj:=Aj,i/tempcoli:=Ai,i/tempAi…m+1,j:=coli×Ai…m+1,j-colj×Ai…m+1,iAi,i:=tempGCD高斯消元与一般高斯消元不同之处在于,GCD高斯消元尽量克服一般高斯消元符号计算膨胀问题,使得每一行没有多余因子也没有分式,计算效率得到提升。可以发现GCD高斯消元没有改变(2)行列式的值,由于(2)矩阵结构的特殊性,我们可以发现选择主行后只有一个非主行。GCD高斯消元使得非主行扩大coli倍,同时使主行缩小coli倍,而且只有一个非主行,所以行列式的值不变。算法newprem中,将(2)整体进行高斯消元(详见文献)。而实际上,要对以上矩阵的前m-n+2行进行高斯消元即可得到如下矩阵A。[A1,1A1,2A1,m+1A2,2A2,m+1A3,3⋮⋮Am-n+2,m-n+2Am-n+2,m+11-xk⋮⋮⋯1-xk〗(3)显然,矩阵(3)行列式的值与(2)的行列式的值是相等的,而det(A)可以用如下公式来计算:det(A)=m-n+1∏i=1Ai,im+1∑j=m-n+2(Am-n+2,jx(m+1-j)k)(4)通过这一简化,当n较大时,可以节省很多运算量。newprem2算法的简要描述:计算0.2%c输入:G,F和xk输出:G对F关于xk的伪余式步骤1如果deg(G,xk)=0或deg(F)=0,返回0;步骤2如果deg(G,xk)<deg(F,xk),返回F;步骤3根据deg(G,xk)和deg(F,xk)构造矩阵(2),然后对前m-n+2行进行GCD高斯消元,再通过(4)式计算矩阵(2)的行列式的值,返回行列式的值。3up-法2,主要有做无假设备的小关键因子普在Maple10.0上,实现了newprem2。实验结果显示,newprem2的计算效率优于newprem。对于规模较小的问题,newprem2与prem相比没有明显优势,甚至更慢一些。对于规模较大问题,newprem2优势明显,所需计算时间一般均少于prem和newprem,对有些问题甚至只有几十分之一。但当在进行多项式次数相近的伪除时,newprem2和newprem都没有太大的优势。下面通过平均统计结果和几个例子来显示newprem2的高效性。我们随机产生的100对多项式计算它们的伪余式(次数分别为50次和8次),newprem2用了161s计算所有的结果,而prem用了308s,newprem用了403s。继续沿用中的例子,比较三个算法所花时间。4rem2的实验结果本文针对中算法的缺陷,采用一种介于一般高斯消元和不带分式高斯消元之间的高斯消元方法来计算矩阵(2)的行列式的值,克服了中间过程膨胀,并且消除了冗余计算,得到了一个效率明显提升,算法效率优于newprem的算法newprem2。通过理论分析及实验结果