2つのテプリッツ行列の積は？

Question

Toeplitz行列と正しい長さのベクトルの積のアルゴリズムはよく知られています。循環行列に入れ、ベクトル（それに続くゼロ）を乗算し、先頭のn要素を返します。製品。

私は、同じサイズの2つのテプリッツ行列を乗算するための最良（時間的に）のアルゴリズムを見つけるのに問題があります。

誰も私にこのアルゴリズムを教えてもらえますか？

Answer 1

ここにO（n^2）時間アルゴリズムがあります。

プロダクトマトリックスの対角線の1つを計算するには、ロックステップでスライドしている長さ - （2n-1）リストの長さnのウィンドウにわたってドット積を計算する必要があります。 2つの連続するエントリ間の差は、時間O（1）において計算することができる。例えば

、1,1エントリはeo + fm + gl + hk + ijある

e f g h i o p q r s 
d e f g h m o p q r 
c d e f g l m o p q 
b c d e f k l m o p 
a b c d e j k l m o 

の積を考えます。 2,2エントリはdp + eo + fm + gl + hk、または1,1エントリからijプラスdpを引いたものです。 3,3エントリはcq + dp + eo + fm + gl、または2,2エントリマイナスhkプラスcqです。 4,4エントリはなどです。

これを浮動小数点で実装する場合は、catastrophic cancellationに注意してください。