R 中的 Toeplitz 矩阵向量乘法
Toeplitz Matrix-Vector multiplication in R
我有一个 n x n 对称托普利茨矩阵 T
,一个长度为 n 的向量 v
,我想快速计算矩阵向量乘积 T%*%v
。 R 中是否有一个包可以使用计算 T%*%v
的快速傅里叶变换方法(或其他方法,如果存在的话)?例如,Matlab 有 Toeplitzmult 包。
下面的函数有效。请注意,ifft()
函数需要 pracma
库。
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) )
}
对于大小为 1000 的 vector/matrix,toepmult
函数占用的时间约为 A%*%v
所用时间的 18%。
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
对于大小为 10,000 的 vector/matrix,toepmult
函数占用的时间约为 A%*%v
所用时间的 2.5%。
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
我有一个 n x n 对称托普利茨矩阵 T
,一个长度为 n 的向量 v
,我想快速计算矩阵向量乘积 T%*%v
。 R 中是否有一个包可以使用计算 T%*%v
的快速傅里叶变换方法(或其他方法,如果存在的话)?例如,Matlab 有 Toeplitzmult 包。
下面的函数有效。请注意,ifft()
函数需要 pracma
库。
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) )
}
对于大小为 1000 的 vector/matrix,toepmult
函数占用的时间约为 A%*%v
所用时间的 18%。
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
对于大小为 10,000 的 vector/matrix,toepmult
函数占用的时间约为 A%*%v
所用时间的 2.5%。
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