Right, there are many tricks for special cases, even when the matrix is not sparse. One example is Toeplitz-Matrix multiplication as described in https://math.m

Right, there are many tricks for special cases, even when the matrix is not sparse. One example is Toeplitz-Matrix multiplication as described in https://math.mit.edu/icg/resources/teaching/18.085-spring2015/toeplitz.pdf https://math.mit.edu/icg/resources/teaching/18.085-spring201... 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) #TRUE