winograd

import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0Awith%20app.setup%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20from%20scipy.signal%20import%20correlate2d%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Winograd%20%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF%E3%81%AE%E6%9C%80%E5%B0%8F%E4%BE%8B%0A%0A%20%20%20%204%C3%974%20%E3%81%AE%E5%85%A5%E5%8A%9B%E3%81%A8%203%C3%973%20%E3%81%AE%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%AB%E3%81%AB%E5%AF%BE%E3%81%97%E3%81%A6%E3%80%81%E9%80%9A%E5%B8%B8%E3%81%AE%E7%9B%B8%E4%BA%92%E7%9B%B8%E9%96%A2%E3%81%A8%0A%20%20%20%20Winograd%20%E6%9C%80%E5%B0%8F%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF%E3%83%AA%E3%83%B3%E3%82%B0%20%60F(2%C3%972%2C%203%C3%973)%60%20%E3%82%92%E6%AF%94%E8%BC%83%E3%81%97%E3%81%BE%E3%81%99%E3%80%82%0A%20%20%20%20%E6%B7%B1%E5%B1%A4%E5%AD%A6%E7%BF%92%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA%E3%81%AE%20%60conv2d%60%20%E3%81%AF%E4%BF%A1%E5%8F%B7%E5%87%A6%E7%90%86%E3%81%AE%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF%E3%81%A7%E3%81%AF%E3%81%AA%E3%81%8F%0A%20%20%20%20%E7%9B%B8%E4%BA%92%E7%9B%B8%E9%96%A2%E3%81%A8%E3%81%97%E3%81%A6%E5%AE%9F%E8%A3%85%E3%81%95%E3%82%8C%E3%82%8B%E3%81%93%E3%81%A8%E3%81%8C%E5%A4%9A%E3%81%84%E3%81%9F%E3%82%81%E3%80%81%E3%81%93%E3%81%93%E3%81%A7%E3%82%82%0A%20%20%20%20%60scipy.signal.correlate2d%60%20%E3%82%92%E5%9F%BA%E6%BA%96%E3%81%AB%E3%81%97%E3%81%BE%E3%81%99%E3%80%82%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20input_matrix%20%3D%20np.array(%0A%20%20%20%20%20%20%20%20%5B%5B1.0%2C%202.0%2C%203.0%2C%204.0%5D%2C%20%5B5.0%2C%206.0%2C%207.0%2C%208.0%5D%2C%20%5B9.0%2C%2010.0%2C%2011.0%2C%2012.0%5D%2C%20%5B13.0%2C%2014.0%2C%2015.0%2C%2016.0%5D%5D%0A%20%20%20%20)%0A%20%20%20%20kernel%20%3D%20np.array(%5B%5B1.0%2C%200.0%2C%20-1.0%5D%2C%20%5B1.0%2C%200.0%2C%20-1.0%5D%2C%20%5B1.0%2C%200.0%2C%20-1.0%5D%5D)%0A%20%20%20%20standard_output%20%3D%20correlate2d(input_matrix%2C%20kernel%2C%20mode%3D%22valid%22)%0A%20%20%20%20return%20input_matrix%2C%20kernel%2C%20standard_output%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20g_matrix%20%3D%20np.array(%5B%5B1.0%2C%200.0%2C%200.0%5D%2C%20%5B0.5%2C%200.5%2C%200.5%5D%2C%20%5B0.5%2C%20-0.5%2C%200.5%5D%2C%20%5B0.0%2C%200.0%2C%201.0%5D%5D)%0A%20%20%20%20b_matrix%20%3D%20np.array(%5B%5B1.0%2C%200.0%2C%20-1.0%2C%200.0%5D%2C%20%5B0.0%2C%201.0%2C%201.0%2C%200.0%5D%2C%20%5B0.0%2C%20-1.0%2C%201.0%2C%200.0%5D%2C%20%5B0.0%2C%201.0%2C%200.0%2C%20-1.0%5D%5D)%0A%20%20%20%20a_matrix%20%3D%20np.array(%5B%5B1.0%2C%201.0%2C%201.0%2C%200.0%5D%2C%20%5B0.0%2C%201.0%2C%20-1.0%2C%20-1.0%5D%5D)%0A%20%20%20%20return%20a_matrix%2C%20b_matrix%2C%20g_matrix%0A%0A%0A%40app.cell%0Adef%20_(a_matrix%2C%20b_matrix%2C%20g_matrix%2C%20input_matrix%2C%20kernel)%3A%0A%20%20%20%20transformed_kernel%20%3D%20g_matrix%20%40%20kernel%20%40%20g_matrix.T%0A%20%20%20%20transformed_input%20%3D%20b_matrix%20%40%20input_matrix%20%40%20b_matrix.T%0A%20%20%20%20hadamard_product%20%3D%20transformed_kernel%20*%20transformed_input%0A%20%20%20%20winograd_output%20%3D%20a_matrix%20%40%20hadamard_product%20%40%20a_matrix.T%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20hadamard_product%2C%0A%20%20%20%20%20%20%20%20transformed_input%2C%0A%20%20%20%20%20%20%20%20transformed_kernel%2C%0A%20%20%20%20%20%20%20%20winograd_output%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20hadamard_product%2C%0A%20%20%20%20standard_output%2C%0A%20%20%20%20transformed_input%2C%0A%20%20%20%20transformed_kernel%2C%0A%20%20%20%20winograd_output%2C%0A)%3A%0A%20%20%20%20comparison%20%3D%20pd.DataFrame(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22standard%22%3A%20standard_output.reshape(-1)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22winograd%22%3A%20winograd_output.reshape(-1)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22abs_error%22%3A%20np.abs(standard_output%20-%20winograd_output).reshape(-1)%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20index%3D%5B%22(0%2C0)%22%2C%20%22(0%2C1)%22%2C%20%22(1%2C0)%22%2C%20%22(1%2C1)%22%5D%2C%0A%20%20%20%20)%0A%20%20%20%20transform_shapes%20%3D%20pd.DataFrame(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22array%22%3A%20%5B%22GgG%E1%B5%80%22%2C%20%22BdB%E1%B5%80%22%2C%20%22elementwise%20product%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22shape%22%3A%20%5Btuple(transformed_kernel.shape)%2C%20tuple(transformed_input.shape)%2C%20tuple(hadamard_product.shape)%5D%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%20%20%20%20return%20comparison%2C%20transform_shapes%0A%0A%0A%40app.cell%0Adef%20_(comparison%2C%20transform_shapes)%3A%0A%20%20%20%20mo.vstack(%5Btransform_shapes%2C%20comparison%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(comparison)%3A%0A%20%20%20%20print(f%22allclose%3D%7Bnp.allclose(comparison%5B'standard'%5D%2C%20comparison%5B'winograd'%5D)%7D%22)%0A%20%20%20%20print(f%22max_abs_error%3D%7Bcomparison%5B'abs_error'%5D.max()%3A.6f%7D%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A