Making a circulant matrix from a given vector in a memory efficient way

I’d like to make a circulant matrix from a given vector of dimension N in a way such that the operation and the resulting matrix consume only O(N) memory cost. Higher dimensional generalization of this operation is needed for a certain variant of Transformer I’m trying to investigate. A naive approach is to apply ‘expand’ to the original vector and then to apply ‘view’ and ‘slice’ alternately. However, this doesn’t work, as ‘view’ demands the input to be contiguous. Is there any viable way you can think of?

it’s not really possible with the strided arrays ( pytorch, numpy and many other scientific computing framework adopts this approach.

1 Like

Thank you so much for your reply. I guess I’ll give up my current attempt and look for another direction.

1 Like

what’s the exact use case? i might be able to help.

Finally, I’ve noticed that my approach of bidirectional language model was unnecessarily complicated, which required the use of circulant matrix for managing the cache of Transformer. I’m sorry.

No worries! Good luck with your project!

A bit late but here is a generic function for pytorch tensors, getting the circulant matrix for one dimension. It’s based on unfold operation.

def circulant(tensor, dim):
    """get a circulant version of the tensor along the {dim} dimension.
    The additional axis is appended as the last dimension.
    E.g. tensor=[0,1,2], dim=0 --> [[0,1,2],[2,0,1],[1,2,0]]"""
    S = tensor.shape[dim]
    tmp =[tensor.flip((dim,)), torch.narrow(tensor.flip((dim,)), dim=dim, start=0, length=S-1)], dim=dim)
    return tmp.unfold(dim, S, 1).flip((-1,))