spyrit.core.torch.fwht

spyrit.core.torch.fwht(x, order=True, dim=-1)

Fast Walsh-Hadamard transform of x

Args:

x (np.ndarray): -by-n input signal, where n is a power of two.

order (bool, optional): True for sequency (default), False for natural. If a list, it defines the permutation indices to use. Default is True.

dim (int, optional): The dimension along which to apply the transform. Default is -1.

Returns:

np.ndarray: n-by-1 transformed signal

Example 1:

Fast sequency-ordered (i.e., Walsh) Hadamard transform

>>> import torch
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = torch.tensor([1, 3, 0, -1, 7, 5, 1, -2])
>>> x = x[None,:]
>>> y = wh.fwht_torch(x)
>>> print(y)

Example 2:

Fast Hadamard transform

>>> import torch
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = torch.tensor([1, 3, 0, -1, 7, 5, 1, -2])
>>> x = x[None,:]
>>> y = wh.fwht_torch(x, False)
>>> print(y)

Example 3:

Permuted fast Hadamard transform

>>> import numpy as np
>>> import torch
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = torch.tensor([1, 3, 0, -1, 7, 5, 1, -2])
>>> ind = [1, 0, 3, 2, 7, 4, 5, 6]
>>> y = wh.fwht_torch(x, ind)
>>> print(y)

Example 4:

Comparison with the numpy transform

>>> import numpy as np
>>> import torch
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = np.array([1, 3, 0, -1, 7, 5, 1, -2])
>>> y_np = wh.fwht(x)
>>> x_torch = torch.from_numpy(x).to(torch.device('cuda:0'))
>>> y_torch = wh.fwht_torch(x_torch)
>>> print(y_np)
>>> print(y_torch)

Example 5:

Computation times for a signal of length 2**12

>>> import timeit
>>> import torch
>>> import numpy as np
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = np.random.rand(2**12,1)
>>> t = timeit.timeit(lambda: wh.fwht(x,False), number=200)
>>> print(f"Fast Hadamard transform numpy CPU (200x): {t:.4f} seconds")
>>> x_torch = torch.from_numpy(x)
>>> t = timeit.timeit(lambda: wh.fwht_torch(x_torch,False), number=200)
>>> print(f"Fast Hadamard transform pytorch CPU (200x): {t:.4f} seconds")
>>> x_torch = torch.from_numpy(x).to(torch.device('cuda:0'))
>>> t = timeit.timeit(lambda: wh.fwht_torch(x_torch,False), number=200)
>>> print(f"Fast Hadamard transform pytorch GPU (200x): {t:.4f} seconds")

Example 6:

CPU vs GPU: Computation times for 512 signals of length 2**12

>>> import timeit
>>> import torch
>>> import spyrit.misc.walsh_hadamard as wh
>>> x_cpu = torch.rand(512,2**12)
>>> t = timeit.timeit(lambda: wh.fwht_torch(x_cpu,False), number=10)
>>> print(f"Fast Hadamard transform pytorch CPU (10x): {t:.4f} seconds")
>>> x_gpu = x_cpu.to(torch.device('cuda:0'))
>>> t = timeit.timeit(lambda: wh.fwht_torch(x_gpu,False), number=10)
>>> print(f"Fast Hadamard transform pytorch GPU (10x): {t:.4f} seconds")

Example 7:

Repeating the Walsh-ordered transform using input indices is faster

>>> import timeit
>>> import torch
>>> import spyrit.misc.walsh_hadamard as wh
>>> x = torch.rand(256,2**12).to(torch.device('cuda:0'))
>>> t = timeit.timeit(lambda: wh.fwht_torch(x), number=100)
>>> print(f"No indices as inputs (100x): {t:.3f} seconds")
>>> ind = wh.sequency_perm_ind(x.shape[-1])
>>> t = timeit.timeit(lambda: wh.fwht_torch(x,ind), number=100)
>>> print(f"With indices as inputs (100x): {t:.3f} seconds")