3つ以上のGCDに関する一考察

通常GCDは二つの多項式f,gに大してもとめてgcd(f,g)=dと求めるわけなんだけれども。信号処理において欲しいのは実はgcd(f1,f2,....,fn)だよね。

この処理は上の論文の応用で実装できます。ただし、ちょっと問題があります。なので、あまりgcd(f1,f2...fn)などの当然の応用が言及されてないのでしょう。後の人のためにメモがてら。。。

上の論文ではf=f',g=g'Dと言う風にgcdであるDを仮定してg'f=f'gを解きます。その結果f/f'=Dというgcdを得ます。

同じようにf,g,hにおいてg'h'f=f'h'g=f'g'hを解くことができます。この時のgaussにかけるべき行列（シルベスタ行列）はf,g,hのそれぞれのシルベスタ行列をF,G,Hとして、0を0行列として

|F|F|0|

|G|0|G|

|0|H|H|

というふうにすればいいです。ただし||は行列の一部を示すものと思ってください。ちなみにgcd(g,h)の場合は

|G|

|H|

となります。

この時f'g'がが求まるのでD^2=GH/f'g'が求まります。

ただし、これをn乗に増やすことを考えるとf2'f3'....fn'という式があまりにも大きく、演算メモリがどんどん増える事に加え、Dのn乗が求まるので、それからDを得るために力技で計算してると誤差伝搬的にやばげです。

これらを解決するには別のアプローチが必要っぽいですね。近似GCDは他にも計算方法があるらしいので、そのうち検討してみたいです。