4-Way Toom Cook Interpolation Matrices

[Josh Liu]

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 ----