2010年1月11日月曜日

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は他にも計算方法があるらしいので、そのうち検討してみたいです。





0 件のコメント:

コメントを投稿