Jim Slonder - 1 year ago 170
R Question

# Toeplitz Matrix-Vector multiplication in R

I have a n x n symmetrix toeplitz matrix

`T`
, a vector
`v`
of length n, and I would like to compute the matrix-vector product
`T%*%v`
quickly. Is there a package in R that can use the fast fourier transform method of computing
`T%*%v`
(or some other method if one exists)? For example, Matlab has the Toeplitzmult package.

The function below works. Note that the `ifft()` function requires the `pracma` library.

``````toepmult <- 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) )
}
``````

For a vector/matrix of size 1000, the `toepmult` function takes about 18% of the time `A%*%v` takes.

``````A <- toeplitz(runif(1000))
v <- runif(1000)
microb(A%*%v,toepmult(A,v),times=1000)
#Unit: microseconds
#           expr      min       lq      mean   median        uq      max neval
#        A %*% v 1515.858 1597.345 1809.3517 1693.533 1957.4350 3868.788  1000
# toepmult(A, v)  185.901  215.395  331.2928  298.435  347.7335 4611.285  1000
#[[1]]
#           [,1]      [,2]
#median 1693.533   298.435
#ratio     1.000     0.176
#diff      0.000 -1395.098
``````

For a vector/matrix of size 10,000, the `toepmult` function takes about 2.5% of the time `A%*%v` takes.

``````A <- toeplitz(runif(10000))
v <- runif(10000)
microb(A%*%v,toepmult(A,v),times=1000)
#Unit: milliseconds
#           expr        min         lq       mean     median         uq      max neval
#        A %*% v 145.834304 160.395663 181.842779 170.396014 186.221449 495.2003  1000
# toepmult(A, v)   2.802058   4.077408   4.990894   4.322707   4.911103 180.4926  1000
#[[1]]
#          [,1]     [,2]
#median 170.396    4.323
#ratio    1.000    0.025
#diff     0.000 -166.073
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download