R help - Feb 2009 - trade-off between speed and storage in matrix multiplications

Dear R-users,

	I coded two equivalent ways to perform (in a simplified version)
some matrix multiplications I would like to use in a more general
framework.
In the first case I used Kronecker product and vectorization of a
certain matrix. This approach takes less time, but, as you may guess, I
run out of memory when dimensions are large.
In the second approach, I profited of sparseness and structure of the
matrices and use outer-functions for performing operations. Here it
takes more time, but I have not problem of memory.

Is there any way to enhance the second approach for speeding-up the
whole process? Or, in computing, this is a well-known trade-off between
speed and storage-spaces which I'm not aware (sorry for that).

Please have a look to the example below.

Needless to say that I'd appreciate any suggestion.

Best,
Carlo Giovanni


# dimensions
m <- 10
n <- 15
# A-matrix
rnA <- runif(m*m)
A <- matrix(rnA, m, m)
# vector
v <- runif(n)
# B-matrix
rnB <- runif(m*n)
B <- matrix(rnB, m, n)

# first solution: vectorize B + kronecker product => faster but storage
issues
system.time(
for(i in 1:100){
    b <- c(B)
    vKron.A <- kronecker(diag(v), A)
    SOL1 <- vKron.A %*% b
})

# second solution: orig. dims + apply + mapply => slower, but w/o
storage issues
system.time(
for(i in 1:100){
    Av <- outer(A, v, FUN="*")
    Av.df1 <- apply(Av, 3, as.data.frame)
    Av.df2 <- lapply(X=Av.df1, FUN=as.matrix, nrow=m, ncol=m)
    SOL2 <- mapply(FUN="%*%", Av.df2, as.data.frame(B)) # as a
matrix
})





----------
This mail has been sent through the MPI for Demographic ...{{dropped:10}}

You might want to compare the performance of your version to the kronecker
method of Matrix (Matrix package) that has appropriate versions for sparse
matrices etc.

-Christos
> -----Original Message-----
> From: r-help-bounces at r-project.org 
> [mailto:r-help-bounces at r-project.org] On Behalf Of Camarda, 
> Carlo Giovanni
> Sent: Monday, February 23, 2009 1:18 PM
> To: r-help at stat.math.ethz.ch
> Subject: [R] trade-off between speed and storage in matrix 
> multiplications
> 
> Dear R-users,
> 
> 	I coded two equivalent ways to perform (in a simplified 
> version) some matrix multiplications I would like to use in a 
> more general framework.
> In the first case I used Kronecker product and vectorization 
> of a certain matrix. This approach takes less time, but, as 
> you may guess, I run out of memory when dimensions are large.
> In the second approach, I profited of sparseness and 
> structure of the matrices and use outer-functions for 
> performing operations. Here it takes more time, but I have 
> not problem of memory.
> 
> Is there any way to enhance the second approach for 
> speeding-up the whole process? Or, in computing, this is a 
> well-known trade-off between speed and storage-spaces which 
> I'm not aware (sorry for that).
> 
> Please have a look to the example below.
> 
> Needless to say that I'd appreciate any suggestion.
> 
> Best,
> Carlo Giovanni
> 
> 
> # dimensions
> m <- 10
> n <- 15
> # A-matrix
> rnA <- runif(m*m)
> A <- matrix(rnA, m, m)
> # vector
> v <- runif(n)
> # B-matrix
> rnB <- runif(m*n)
> B <- matrix(rnB, m, n)
> 
> # first solution: vectorize B + kronecker product => faster 
> but storage issues system.time( for(i in 1:100){
>     b <- c(B)
>     vKron.A <- kronecker(diag(v), A)
>     SOL1 <- vKron.A %*% b
> })
> 
> # second solution: orig. dims + apply + mapply => slower, but 
> w/o storage issues system.time( for(i in 1:100){
>     Av <- outer(A, v, FUN="*")
>     Av.df1 <- apply(Av, 3, as.data.frame)
>     Av.df2 <- lapply(X=Av.df1, FUN=as.matrix, nrow=m, ncol=m)
>     SOL2 <- mapply(FUN="%*%", Av.df2, as.data.frame(B)) # as a
matrix
> })
> 
> 
> 
> 
> 
> ----------
> This mail has been sent through the MPI for Demographic 
> ...{{dropped:10}}
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide 
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
> 
>