通常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 件のコメント:
コメントを投稿