Closed JIANGJZ closed 4 years ago
Well you need to choose m + n - 2 points, or 14 + 3 - 2 = 15 in your example.
One strategy is to choose simple rational numbers. For each point, also use its opposite and reciprocal.
The first 3 points are usually 0, 1, -1 the next 4 are usually 2, -2, 1/2, -1/2
That gets you to F(6,3), and most of us stop there because of numeric accuracy problems caused by larger numbers.
Here is one possibility for F(14,3): choose 8 more points: 3/2, -3/2, 2/3, -2/3, 5/2, -5/2, 2/5, -2/5
>>> wincnn.showCookToomFilter((0,1,-1,2,-2,Rational(1,2),-Rational(1,2), Rational(3,2), -Rational(3,2), Rational(2,3), -Rational(2,3), Rational(2,5), -Rational(2,5), Rational(5,2), -Rational(5,2)), 14, 3)
AT =
⎡1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0⎤
⎢ ⎥
⎢0 1 -1 2 -2 1/2 -1/2 3/2 -3/2 2/3 -2/3 2/5 -2/5 5/2 -5/2 0⎥
⎢ ⎥
⎢0 1 1 4 4 1/4 1/4 9/4 9/4 4/9 4/9 4/25 4/25 25/4 25/4 0⎥
⎢ ⎥
⎢0 1 -1 8 -8 1/8 -1/8 27/8 -27/8 8/27 -8/27 8/125 -8/125 125/8 -125/8 0⎥
⎢ ⎥
⎢ 81 81 16 16 16 16 625 625 ⎥
⎢0 1 1 16 16 1/16 1/16 ── ── ── ── ─── ─── ─── ─── 0⎥
⎢ 16 16 81 81 625 625 16 16 ⎥
⎢ ⎥
⎢ 243 -243 32 -32 32 -32 3125 -3125 ⎥
⎢0 1 -1 32 -32 1/32 -1/32 ─── ───── ─── ──── ──── ──── ──── ────── 0⎥
⎢ 32 32 243 243 3125 3125 32 32 ⎥
⎢ ⎥
⎢ 729 729 64 64 64 64 15625 15625 ⎥
⎢0 1 1 64 64 1/64 1/64 ─── ─── ─── ─── ───── ───── ───── ───── 0⎥
⎢ 64 64 729 729 15625 15625 64 64 ⎥
⎢ ⎥
⎢ 2187 -2187 128 -128 128 -128 78125 -78125 ⎥
⎢0 1 -1 128 -128 1/128 -1/128 ──── ────── ──── ───── ───── ───── ───── ─────── 0⎥
⎢ 128 128 2187 2187 78125 78125 128 128 ⎥
⎢ ⎥
⎢ 6561 6561 256 256 256 256 390625 390625 ⎥
⎢0 1 1 256 256 1/256 1/256 ──── ──── ──── ──── ────── ────── ────── ────── 0⎥
⎢ 256 256 6561 6561 390625 390625 256 256 ⎥
⎢ ⎥
⎢ 19683 -19683 512 -512 512 -512 1953125 -1953125 ⎥
⎢0 1 -1 512 -512 1/512 -1/512 ───── ─────── ───── ───── ─────── ─────── ─────── ───────── 0⎥
⎢ 512 512 19683 19683 1953125 1953125 512 512 ⎥
⎢ ⎥
⎢ 59049 59049 1024 1024 1024 1024 9765625 9765625 ⎥
⎢0 1 1 1024 1024 1/1024 1/1024 ───── ───── ───── ───── ─────── ─────── ─────── ─────── 0⎥
⎢ 1024 1024 59049 59049 9765625 9765625 1024 1024 ⎥
⎢ ⎥
⎢ 177147 -177147 2048 -2048 2048 -2048 48828125 -48828125 ⎥
⎢0 1 -1 2048 -2048 1/2048 -1/2048 ────── ──────── ────── ────── ──────── ──────── ──────── ────────── 0⎥
⎢ 2048 2048 177147 177147 48828125 48828125 2048 2048 ⎥
⎢ ⎥
⎢ 531441 531441 4096 4096 4096 4096 244140625 244140625 ⎥
⎢0 1 1 4096 4096 1/4096 1/4096 ────── ────── ────── ────── ───────── ───────── ───────── ───────── 0⎥
⎢ 4096 4096 531441 531441 244140625 244140625 4096 4096 ⎥
⎢ ⎥
⎢ 1594323 -1594323 8192 -8192 8192 -8192 1220703125 -1220703125 ⎥
⎢0 1 -1 8192 -8192 1/8192 -1/8192 ─────── ───────── ─────── ─────── ────────── ────────── ────────── ──────────── 1⎥
⎣ 8192 8192 1594323 1594323 1220703125 1220703125 8192 8192 ⎦
G =
⎡ 1 0 0 ⎤
⎢ ⎥
⎢ -32 -32 -32 ⎥
⎢ ──── ──── ──── ⎥
⎢ 441 441 441 ⎥
⎢ ⎥
⎢ -32 32 -32 ⎥
⎢ ──── ─── ──── ⎥
⎢ 441 441 441 ⎥
⎢ ⎥
⎢ -5/24192 -5/12096 -5/6048 ⎥
⎢ ⎥
⎢ -5/24192 5/12096 -5/6048 ⎥
⎢ ⎥
⎢ -640 -320 -160 ⎥
⎢ ───── ───── ───── ⎥
⎢ 189 189 189 ⎥
⎢ ⎥
⎢ -640 320 -160 ⎥
⎢ ───── ─── ───── ⎥
⎢ 189 189 189 ⎥
⎢ ⎥
⎢ 64 96 144 ⎥
⎢ ───── ───── ───── ⎥
⎢ 19019 19019 19019 ⎥
⎢ ⎥
⎢ 64 -96 144 ⎥
⎢ ───── ───── ───── ⎥
⎢ 19019 19019 19019 ⎥
⎢ ⎥
⎢ 4782969 1594323 531441 ⎥
⎢ ─────── ─────── ─────── ⎥
⎢ 4868864 2434432 1217216 ⎥
⎢ ⎥
⎢ 4782969 -1594323 531441 ⎥
⎢ ─────── ───────── ─────── ⎥
⎢ 4868864 2434432 1217216 ⎥
⎢ ⎥
⎢6103515625 1220703125 244140625⎥
⎢────────── ────────── ─────────⎥
⎢2052787968 1026393984 513196992⎥
⎢ ⎥
⎢6103515625 -1220703125 244140625⎥
⎢────────── ──────────── ─────────⎥
⎢2052787968 1026393984 513196992⎥
⎢ ⎥
⎢ 64 160 400 ⎥
⎢ ─────── ─────── ─────── ⎥
⎢ 8018703 8018703 8018703 ⎥
⎢ ⎥
⎢ 64 -160 400 ⎥
⎢ ─────── ─────── ─────── ⎥
⎢ 8018703 8018703 8018703 ⎥
⎢ ⎥
⎣ 0 0 1 ⎦
BT =
⎡ -12919 260351 -2290717 2290717 -260351 12919 ⎤
⎢1 0 ─────── 0 ────── 0 ───────── 0 ─────── 0 ──────── 0 ───── 0 -1 0⎥
⎢ 900 3600 14400 14400 3600 900 ⎥
⎢ ⎥
⎢ -12019 -12019 8491 8491 -480539 -480539 8491 8491 -12019 -12019 ⎥
⎢0 1 1 ─────── ─────── ──── ──── ──────── ──────── ──── ──── ─────── ─────── 1 1 0⎥
⎢ 900 900 144 144 4800 4800 144 144 900 900 ⎥
⎢ ⎥
⎢ 12019 -12019 -8491 8491 480539 -480539 -8491 8491 12019 -12019 ⎥
⎢0 -1 1 ───── ─────── ────── ──── ────── ──────── ────── ──── ───── ─────── -1 1 0⎥
⎢ 900 900 144 144 4800 4800 144 144 900 900 ⎥
⎢ ⎥
⎢ -6347 -6347 247657 247657 -34051 -34051 111247 111247 -9319 -9319 ⎥
⎢0 1/2 1/4 ────── ────── ────── ────── ─────── ─────── ────── ────── ────── ────── 2 1 0⎥
⎢ 900 1800 7200 14400 480 960 1800 3600 450 900 ⎥
⎢ ⎥
⎢ 6347 -6347 -247657 247657 34051 -34051 -111247 111247 9319 -9319 ⎥
⎢0 -1/2 1/4 ──── ────── ──────── ────── ───── ─────── ──────── ────── ──── ────── -2 1 0⎥
⎢ 900 1800 7200 14400 480 960 1800 3600 450 900 ⎥
⎢ ⎥
⎢ -9319 -9319 111247 111247 -34051 -34051 247657 247657 -6347 -6347 ⎥
⎢0 2 4 ────── ────── ────── ────── ─────── ─────── ────── ────── ────── ────── 1/2 1 0⎥
⎢ 450 225 1800 900 480 240 7200 3600 900 450 ⎥
⎢ ⎥
⎢ 9319 -9319 -111247 111247 34051 -34051 -247657 247657 6347 -6347 ⎥
⎢0 -2 4 ──── ────── ──────── ────── ───── ─────── ──────── ────── ──── ────── -1/2 1 0⎥
⎢ 450 225 1800 900 480 240 7200 3600 900 450 ⎥
⎢ ⎥
⎢ -1391 -1391 5291 5291 -207493 -207493 32461 32461 -5447 -5447 ⎥
⎢0 2/3 4/9 ────── ────── ──── ──── ──────── ──────── ───── ───── ────── ────── 3/2 1 0⎥
⎢ 150 225 120 180 2400 3600 480 720 300 450 ⎥
⎢ ⎥
⎢ 1391 -1391 -5291 5291 207493 -207493 -32461 32461 5447 -5447 ⎥
⎢0 -2/3 4/9 ──── ────── ────── ──── ────── ──────── ─────── ───── ──── ────── -3/2 1 0⎥
⎢ 150 225 120 180 2400 3600 480 720 300 450 ⎥
⎢ ⎥
⎢ -5447 -5447 32461 32461 -207493 -207493 5291 5291 -1391 -1391 ⎥
⎢0 3/2 9/4 ────── ────── ───── ───── ──────── ──────── ──── ──── ────── ────── 2/3 1 0⎥
⎢ 300 200 480 320 2400 1600 120 80 150 100 ⎥
⎢ ⎥
⎢ 5447 -5447 -32461 32461 207493 -207493 -5291 5291 1391 -1391 ⎥
⎢0 -3/2 9/4 ──── ────── ─────── ───── ────── ──────── ────── ──── ──── ────── -2/3 1 0⎥
⎢ 300 200 480 320 2400 1600 120 80 150 100 ⎥
⎢ ⎥
⎢ -3647 -3647 78001 78001 -28391 -28391 10087 10087 -511 -511 ⎥
⎢0 5/2 25/4 ────── ────── ───── ───── ─────── ─────── ───── ───── ───── ───── 2/5 1 0⎥
⎢ 180 72 1440 576 480 192 360 144 90 36 ⎥
⎢ ⎥
⎢ 3647 -3647 -78001 78001 28391 -28391 -10087 10087 511 -511 ⎥
⎢0 -5/2 25/4 ──── ────── ─────── ───── ───── ─────── ─────── ───── ─── ───── -2/5 1 0⎥
⎢ 180 72 1440 576 480 192 360 144 90 36 ⎥
⎢ ⎥
⎢ -511 -511 10087 10087 -28391 -28391 78001 78001 -3647 -3647 ⎥
⎢0 2/5 4/25 ───── ───── ───── ───── ─────── ─────── ───── ───── ────── ────── 5/2 1 0⎥
⎢ 90 225 360 900 480 1200 1440 3600 180 450 ⎥
⎢ ⎥
⎢ 511 -511 -10087 10087 28391 -28391 -78001 78001 3647 -3647 ⎥
⎢0 -2/5 4/25 ─── ───── ─────── ───── ───── ─────── ─────── ───── ──── ────── -5/2 1 0⎥
⎢ 90 225 360 900 480 1200 1440 3600 180 450 ⎥
⎢ ⎥
⎢ 12919 -260351 2290717 -2290717 260351 -12919 ⎥
⎢0 -1 0 ───── 0 ──────── 0 ─────── 0 ───────── 0 ────── 0 ─────── 0 1⎥
⎣ 900 3600 14400 14400 3600 900 ⎦
FIR filter: AT*((G*g)(BT*d)) =
⎡ d[0]⋅g[0] + d[1]⋅g[1] + d[2]⋅g[2] ⎤
⎢ ⎥
⎢ d[1]⋅g[0] + d[2]⋅g[1] + d[3]⋅g[2] ⎥
⎢ ⎥
⎢ d[2]⋅g[0] + d[3]⋅g[1] + d[4]⋅g[2] ⎥
⎢ ⎥
⎢ d[3]⋅g[0] + d[4]⋅g[1] + d[5]⋅g[2] ⎥
⎢ ⎥
⎢ d[4]⋅g[0] + d[5]⋅g[1] + d[6]⋅g[2] ⎥
⎢ ⎥
⎢ d[5]⋅g[0] + d[6]⋅g[1] + d[7]⋅g[2] ⎥
⎢ ⎥
⎢ d[6]⋅g[0] + d[7]⋅g[1] + d[8]⋅g[2] ⎥
⎢ ⎥
⎢ d[7]⋅g[0] + d[8]⋅g[1] + d[9]⋅g[2] ⎥
⎢ ⎥
⎢ d[10]⋅g[2] + d[8]⋅g[0] + d[9]⋅g[1] ⎥
⎢ ⎥
⎢d[10]⋅g[1] + d[11]⋅g[2] + d[9]⋅g[0] ⎥
⎢ ⎥
⎢d[10]⋅g[0] + d[11]⋅g[1] + d[12]⋅g[2]⎥
⎢ ⎥
⎢d[11]⋅g[0] + d[12]⋅g[1] + d[13]⋅g[2]⎥
⎢ ⎥
⎢d[12]⋅g[0] + d[13]⋅g[1] + d[14]⋅g[2]⎥
⎢ ⎥
⎣d[13]⋅g[0] + d[14]⋅g[1] + d[15]⋅g[2]⎦
Here are some recent publications that examine fast convolution algorithms for longer sequences. They use non-minimal Winograd algorithms to increase numeric stability.
Ju, Caleb, and Edgar Solomonik. "Derivation and Analysis of Fast Bilinear Algorithms for Convolution." arXiv preprint arXiv:1910.13367 (2019). https://arxiv.org/abs/1910.13367
Barabasz, Barbara, and David Gregg. "Winograd convolution for dnns: Beyond linear polynomials." International Conference of the Italian Association for Artificial Intelligence. Springer, Cham, 2019. https://arxiv.org/abs/1905.05233
Thank you very much for your answer.
What still puzzles me is how you choose these 8 more points:
3/2, -3/2, 2/3, -2/3,
5/2, -5/2, 2/5, -2/5
Are there any selection rules?
On Wed, Jul 22, 2020 at 8:21 PM JiangJiazhi notifications@github.com wrote:
Thank you very much for your answer. What still puzzles me is how you choose these 8 more points: 3/2, -3/2, 2/3, -2/3, 5/2, -5/2, 2/5, -2/5 Are there any selection rules?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/andravin/wincnn/issues/24#issuecomment-662800132, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACARRZMLFMYBHXSSSZDWB7TR46UEFANCNFSM4PD652WQ .
"For each point, also use its opposite and reciprocal."
In other words, each number you choose gives you 4 points. n/d also gives you -n/d, d/n, and -d/n
So the question then becomes how to you choose n and d?
Conventional wisdom is we want n and d to each be as small as possible.
Also, it bears repeating that F(14,3) is probably not a good choice for any application, because the numeric accuracy will be too low, and large tile sizes can pose efficiency problems as well.
Again, consider using either a smaller tile or a non-minal Winograd algorithm, as explained in the references above.
On Wed, Jul 22, 2020 at 11:15 PM Andrew Lavin aj.lavin@gmail.com wrote:
On Wed, Jul 22, 2020 at 8:21 PM JiangJiazhi notifications@github.com wrote:
Thank you very much for your answer. What still puzzles me is how you choose these 8 more points: 3/2, -3/2, 2/3, -2/3, 5/2, -5/2, 2/5, -2/5 Are there any selection rules?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/andravin/wincnn/issues/24#issuecomment-662800132, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACARRZMLFMYBHXSSSZDWB7TR46UEFANCNFSM4PD652WQ .
"For each point, also use its opposite and reciprocal."
In other words, each number you choose gives you 4 points. n/d also gives you -n/d, d/n, and -d/n
So the question then becomes how to you choose n and d?
Conventional wisdom is we want n and d to each be as small as possible.
OK, I got it. Thank you for your suggestions and answers!
Hello, I have read the issues asked before, but I still can't understand how I should select interpolation points for F(m,n).