That paper is light on details but, for example, in R you can define the function for toeplitz multiplication as below. This has given the matrix multiplication part of my code a >100x speedup before.
'%t*%' <- function(A,v){
n <- nrow(A)
x <- as.matrix(c(A[1,], 0, A[1,][n:2]))
p <- c(v, rep(0, n))
h <- as.vector(fft(p)*fft(x))
out <- Re(pracma::ifft(h)[1:n])
return(matrix(out, n))
}
all.equal(A %t*% v, A %*% v) #TRUEAlso, only tangentially related, but if you can change your problem formulation to make the matrix of interest sparse(r), that can be a huge win. Two things that have helped me in the past:
- Rows or columns that have mostly the same (nonzero) coefficient throughout. You can normally do some simple substitution to turn them into zeros.
- Rows or columns that are naturally very similar to each other. You can often replace `y` with `y-x` or replace `x[i]` with `x[i]-x[i+1]` to turn one (or `n-1`) columns "mostly empty."