rToO February 2016

Is there a (fast enough) workaround for multiplying matrices exceeding memory limit?

I have have two distance matrices d_X: n x n and d_Y: m x m.

set.seed(1)
n <- 2
m <- 3
d_X <- as.matrix(dist(runif(n)))
d_Y <- as.matrix(dist(runif(m)))

From matrices d_X and d_Y matrix G: nm x nm is formed:

G <- matrix(nrow = n*m,ncol = n*m)
for(i in 1:n) {
      for (j in 1:m) {
            for(ii in 1:n) {
                  for(jj in 1:m) {
                        G[(i-1)*m+j,(ii-1)*m+jj] = abs(d_X[i, ii] - d_Y[j, jj])
                  }
            }
      }
}

There is also matrix U: nm*1:

U <- runif(m*n)

My goal is to calculate G%*%U. Now, when n and m are 200, we need 6GB to allocate G. Since G is symmetric we could save half the space needed by restoring it properly.

In practice n and m sizes are up to 5000 which makes allocating G impossible. Since I only need the value of G%*%U, it would be sufficient to calculate it piece by piece. I'm struggling to find an effective way to do it.

*Time also matters

Since I have to run these calculations thousands of times, it is also important, that computing G%*%U takes reasonable time. I have used following function to speed up computing G in cases where n and m are less than a hundred:

Rcpp::cppFunction('NumericMatrix G_mat(NumericMatrix d_X, NumericMatrix d_Y) {
                  NumericMatrix G(d_X.nrow()*d_Y.nrow(),d_X.nrow()*d_Y.nrow());
                  for (int i = 0; i <d_X.nrow(); i++) {
                  for (int j = 0; j < d_Y.nrow(); j++) {
                  for (int ii = 0; ii < d_X.nrow(); ii++) {
                  for (int jj = 0; jj < d_Y.nrow(); jj++) {
                  G(i*d_Y.nrow()+j,ii*d_Y.nrow()+jj) = fabs(d_X(i, ii) - d_Y(j, jj));
                  };
           

Answers


teucer February 2016

Maybe this

A <- numeric(m*n)
for(i in 1:n) {
  for (j in 1:n) {
    A[((i-1)*m+1):(i*m)]= A[((i-1)*m+1):(i*m)] + abs(d_Y-d_X[i,j])%*%U[((j-1)*m+1):(j*m)]
  }
}

Post Status

Asked in February 2016
Viewed 2,704 times
Voted 13
Answered 1 times

Search




Leave an answer