# 4-Way Toom Cook Interpolation Matrices

Josh Liu zliu2 at student.gsu.edu
Mon Oct 4 20:19:58 CEST 2004

Attached below are matrices that can be used to interpolate the point
products of a 4-Way Toom-Cook. The points are evaluated at
{0,1/4,1/2,1,2,4,inf}. I want to know if there are better matrices to
do the same thing. I have posted this message on the gmp-devel list two
months ago but I received no replies. I would be most grateful if
anyone can come up with better interpolation matrices than these. Thank
you.

P.S. Are there algorithms that generate optimal interpolation matrices
given the costs of certain arithmetic operations?

---- Begin interpolation_transformations.tex ----

% interpolation_transformations.tex

$$W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 4096& 1024& 256& 64& 16& 4& 1\cr 64& 32& 16& 8& 4& 2& 1\cr 1& 1& 1& 1& 1& 1& 1\cr 1& 2& 4& 8& 16& 32& 64\cr 1& 4& 16& 64& 256& 1024& 4096\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_0 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr -4096& 1& 0& 0& 0& 0& -1\cr -64& 0& 1& 0& 0& 0& -1\cr -1& 0& 0& 1& 0& 0& -1\cr -1& 0& 0& 0& 1& 0& -64\cr -1& 0& 0& 0& 0& 1& -4096\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_1 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& -1& 0\cr 0& 0& 1& 0& -1& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 1& 0& 1& 0& 0\cr 0& 1& 0& 0& 0& 1& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_2 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0& 0\cr 0& 0& 1& 0& 0& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 0& -16& 1& 0& 0\cr 0& 0& 0& -128& 0& 1& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_3 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1& -20& 0& 0& 0& 0\cr 0& -1& 34& 0& 0& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 0& 50& -1& 0\cr 0& 0& 0& 0& -36& 1& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_4 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1/4& 0& 0& 0& 0& 0\cr 0& 0& 1/8& 0& 0& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 0& 1/8& 0& 0\cr 0& 0& 0& 0& 0& 1/4& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_5 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1/105& 0& 0& 0& 0& 0\cr 0& 0& 1/21& 0& 0& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 0& 1/7& 0& 0\cr 0& 0& 0& 0& 0& 1/63& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_6 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 1& 0\cr 0& 0& 1& 0& 1& 0& 0\cr 0& 0& 0& 1& 1& 1& 0\cr 0& 0& -1& 0& 1& 0& 0\cr 0& -1& 0& 0& 0& 1& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_7 = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1/2& 0& 0& 0& 0& 0\cr 0& 0& 1/2& 0& 0& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 0& 1/2& 0& 0\cr 0& 0& 0& 0& 0& 1/2& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1024& 256& 64& 16& 4& 0\cr 0& 32& 16& 8& 4& 2& 0\cr 0& 1& 1& 1& 1& 1& 0\cr 0& 2& 4& 8& 16& 32& 0\cr 0& 4& 16& 64& 256& 1024& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_1 \cdot A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1020& 240& 0& -240& -1020& 0\cr 0& 30& 12& 8& -12& -30& 0\cr 0& 1& 1& 1& 1& 1& 0\cr 0& 34& 20& 16& 20& 34& 0\cr 0& 1028& 272& 128& 272& 1028& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_2 \cdot A_1 \cdot A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1020& 240& 0& -240& -1020& 0\cr 0& 30& 12& 8& -12& -30& 0\cr 0& 1& 1& 1& 1& 1& 0\cr 0& 18& 4& 0& 4& 18& 0\cr 0& 900& 144& 0& 144& 900& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_3 \cdot A_2 \cdot A_1 \cdot A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 420& 0& 0& 0& -420& 0\cr 0& 0& 168& 0& -168& 0& 0\cr 0& 1& 1& 1& 1& 1& 0\cr 0& 0& 56& 0& 56& 0& 0\cr 0& 252& 0& 0& 0& 252& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_4 \cdot A_3 \cdot A_2 \cdot A_1 \cdot A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 105& 0& 0& 0& -105& 0\cr 0& 0& 21& 0& -21 0& 0\cr 0& 1& 1& 1& 1& 1& 0\cr 0& 0& 7& 0& 7& 0& 0\cr 0& 63& 0& 0& 0& 63& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_5 \cdot A_4 \cdot A_3 \cdot A_2 \cdot A_1 \cdot A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& -1& 0\cr 0& 0& 1& 0& -1& 0& 0\cr 0& 1& 1& 1& 1& 1& 0\cr 0& 0& 1& 0& 1& 0& 0\cr 0& 1& 0& 0& 0& 1& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_6 \cdot A_5 \cdot A_4 \cdot A_3 \cdot A_2 \cdot A_1 \cdot A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 2& 0& 0& 0& 0& 0\cr 0& 0& 2& 0& 0& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 0& 2& 0& 0\cr 0& 0& 0& 0& 0& 2& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

$$A_7 \cdot A_6 \cdot A_5 \cdot A_4 \cdot A_3 \cdot A_2 \cdot A_1 \cdot A_0 \cdot W = \pmatrix { 1& 0& 0& 0& 0& 0& 0\cr 0& 1& 0& 0& 0& 0& 0\cr 0& 0& 1& 0& 0& 0& 0\cr 0& 0& 0& 1& 0& 0& 0\cr 0& 0& 0& 0& 1& 0& 0\cr 0& 0& 0& 0& 0& 1& 0\cr 0& 0& 0& 0& 0& 0& 1\cr }$$

--- End interpolation_transformations.tex ----