Fast Fourier transform
Fast Fourier transform algorithms utilize the symmetries of the matrix to reduce the time of multiplying a vector by this matrix, from the usual formula_15. Similar techniques can be applied for multiplications by matrices such as Hadamard matrix and the Walsh matrix.