I’ve been looking for an equivalent determinant function that computes the determinant of a Vandermonde Matrix. In short, the Vandermonde determinant scales better than a standard determinant due to the fact that the matrix is restricted.
Such a determinant is defined as,
where x is a vector of length n.
I’ve written up a quick function that works, which is,
def vander_det(x: Tensor) -> Tensor:
""""
:param x: A Tensor of size [B,N]
"""
det = 1.
for j in reversed(range(x.shape[-1])):
for i in reversed(range(j)):
det *= (x[:,j] - x[:,i])
return det
Although this works I’ve noticed that it actually scales worse than using torch.linalg.det (most likely due to the use a nested-loop. I was wondering if 1) There already exists a vandermonde-determinant like function within PyTorch (which I’ve missed) or 2) Is there a way to parallelize the nested loop?
I doubt that your nested-loop version scales worse that det(). Your
version scales in time as n**2 (just count the number of times through
the loop), while det() scales as n**3. Of course for moderate values
of n your python-loop version is indeed likely to be much slower than det() because of the python, non-pipelined overhead.
Yes. With a little bit of monkeying around, you can perform the n**2
computation with pure, non-loop tensor operations:
>>> import torch
>>> torch.__version__
'1.9.0'
>>>
>>> _ = torch.manual_seed (2021)
>>>
>>> n = 5
>>>
>>> x = torch.randn (n) # random x
>>>
>>> V = x.unsqueeze (1).expand (n, n)**torch.arange (n) # vandermonde matrix
>>>
>>> torch.det (V) # vandermonde determinant
tensor(2.2679)
>>>
>>> d = x - x.unsqueeze (1) # "outer difference" -- x_j - x_i
>>>
>>> (torch.ones (n, n).tril() + d.triu (1)).prod() # product of upper triangle of d = det (V)
tensor(2.2679)
That’s what I thought but when I tested it the Vandermonde determinant scales bettter initially but for larger N performed worse. The Vandermonde det scaled approximately N**2 but torch.linalg.det scaled better which doesn’t make sense to me because it’s an N**3 operation, although that’s the naive scaling of it as it can be reduced.
What I’m probably doing is calculating the scaling wrong. The TL;DR of that is I just use curve_fit from scipy and fit a function of f = a*x**b. For Vandermonde is was about 2.1 and for torch.linalg.det it was like 1.4 (which doesn’t make sense at all, most likely because I’m calculating the scaling wrong). Perhaps it’d be better to curve_fit to logarithm of the runtime.
