Calcul rapide

A priori, le nombre d'additions de nombres complexes effectuées pour calculer la transformée d'HADAMARD d'une fonction $f\in\ensuremath{\matheu{F}}(m)$ est en $O(2^{2m})$.

Cependant, en notant $H_{2^m}$ la matrice de $h_{2^m}$ dans la base $\ensuremath{\matheu{B}}$, on peut remarquer que

$$H_2 = \begin{pmatrix} 1& 1\\ 1&-1 \end{pmatrix},\ H_4 = \b... ... 1 \end{pmatrix} = \begin{pmatrix} H_2& H_2\\ H_2&-H_2 \end{pmatrix} \ ,$$

et plus généralement, $H_{2^{m+1} = \begin{pmatrix} H_{2^m}& H_{2^m}\\ H_{2^m}&-H_{2^m} \end{pmatrix}}$, soit $H_{2^{m+1}}=H_2 \otimes H_{2^m}$ où $\otimes$ est le produit de Kronecker.

Ainsi, le calcul de $H_{2^{m+1}}$ est ramené au calcul de $H_{2^m}$.