performance - 2 つのテプリッツ行列の積?

Question

テプリッツ行列と正しい長さのベクトルの積のO(n log n)アルゴリズムはよく知られています。それを巡回行列に入れ、ベクトル (およびそれに続くゼロ) を掛けて、n積の一番上の要素を返します。

同じサイズの 2 つの Toeplitz 行列を乗算するための最適な (時間的に) アルゴリズムを見つけるのに苦労しています。

誰でもこれのアルゴリズムを教えてもらえますか?

Answer 1

これは O(n^2) 時間のアルゴリズムです。

積行列の対角線の 1 つを計算するには、ロックステップでスライドする長さ (2n-1) のリストの長さ n のウィンドウで内積を計算する必要があります。連続する 2 つのエントリの差は、時間 O(1) で計算できます。

たとえば、次の積を考えます。

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

1,1 エントリはeo + fm + gl + hk + ijです。2,2 エントリはdp + eo + fm + gl + hk、または 1,1 エントリ マイナスijプラスdpです。3,3 エントリはcq + dp + eo + fm + gl、または 2,2 エントリ マイナスhkプラスcqです。4,4 エントリはbr + cq + dp + eo + fmなどです。

これを浮動小数点で実装する場合は、壊滅的なキャンセルに注意してください。