Efficient modification of the rows of a sparse matrix in Java

Question

I need to "normalize" a large sparse matrix so that the sum of the entries in each row is 1. For rows that have some non-zero entries, each entry is divided by the row sum. For rows that are all zeros, each entry is replaced by 1/numberOfColumns (making the matrix considerably less sparse).

If it matters, my matrix is square, and symmetric. I'm working first with a "small" test sample, where my matrix is about 32K x 32K in size -- but we ultimately need this to work with much larger matrices. Both time and memory efficiency will be important (with memory a bit more critical than time). Before normalization about 1% of the entries are non-zero.

After normalizing the n x n matrix, it needs to be multiplied by a series of n x k dense matrices, where k is a small number (<10)

I'm currently using the la4j matrix package, but I'm not in any way tied to it.

I've included my normalization code below. It's horribly slow, in my 32K x 32K test case. I know from a bit of experimentation that the piece that takes the most time is re-setting the rows of the T matrix (my t.setRow lines below).

Three questions:

1) Is there a better package or better approach to doing this efficiently?

2) Should I not be using a sparse matrix representation for this?

3) Would it be best to not replace the zero rows but just keep track of which rows were zeros, and then hack the matrix multiplication accordingly?

Thanks in advance!

SparseMatrix t = new CRSMatrix(n, n);

// in between non-zero entries in t are added one at a time


double uniformWeight = (double) 1 / n; // used when the rowSum is zero
    for (int i = 0; i < n; i++) {
        Vector row = t.getRow(i);
        double rowSum = row.sum();
        if (rowSum > 0) {
            row = row.divide(rowSum);
            t.setRow(i,row);
        } else {
            row.assign(uniformWeight); // Assigns all elements of this vector to given value
            t.setRow(i, row);
        }
    }

Update 1

Here's what I tried that did speed things up quite a bit. I haven't tried Vladimir's suggestions yet but I will add those when I get back to this project next week. Now I am keeping a boolean array of which rows are zero rows, and should be treated as uniform rows during the matrix multipication, which is now done with my hackMultiply method. I would appreciate Vladimir's (or others') additional advice on avoiding the getRow and setRow in that method. Note that m2 (the second multiplicand) and m3 (the result matrix) are not sparse, if that matters. Thanks in advance!

    boolean[] zeroRows = new boolean[n]; // all values default to false
    for (int i = 0; i < n; i++) {
        Vector row = t.getRow(i);  // haven't had a chance to try Vladimir's 
        double rowSum = row.sum(); // improvements here yet
        if (rowSum > 0) {
            row = row.divide(rowSum);  // or here
            t.setRow(i,row);           // ...
        } else {
            // instead of setting to uniform weight, just keep track
            zeroRows[i] = true;
        }
    }

/**
 * Multiplies the given matrices m1 (Sparse) and m2, with the following modifications
 * For every row in m1 for which the corrresponding entry in zeroRows is true
 * use uniformVector instead of the actual contents of the row for the multiplication
 * (Meant for the case when the replaced rows are all zeros, and we don't want 
 * to actually replace them in the SparseMatrix because then it wouldn't be sparse 
 * anymore.)
 * 
 * @param m1 First multiplicand
 * @param m2 Second multiplicand
 * @param zeroRows boolean array indicating which rows of m1 should be logically replaced by uniformVector
 * @param uniformVector vector to replace all the zeroRows with during the multiplication
 * @return the result of the hacked multiplication
 */
public static Matrix hackMultiply(SparseMatrix m1, Matrix m2, boolean[] zeroRows, Vector uniformVector) {
// for "efficiency" I'm assuming I get passed in things of appropriate sizes, no checking
    int a = m1.rows();
    int b = m2.columns();
    int c = m1.columns(); // must == m2.rows() for the matrix multiplication to work
    Matrix m3 = new Basic2DMatrix(a,b);
    Vector v1;
    for (int i = 0; i < a; i++) {
        if (zeroRows[i]) {
            v1 = uniformVector;
        } else {
            v1 = m1.getRow(i);
        }
        m3.setRow(i, v1.multiply(m2));
    }
    return m3;
}

Update 2

I really appreciate all the help from @Vladimir and @mikera. For what it's worth, the version using la4j with the hackMultiply approach is pretty much identical in time use to the version using vectorz version 0.26.0. It looks like the upgrades in 0.27.0 will give it a slight edge, but I haven't tried it yet. For memory use, the la4j version with the hack is considerably better than the vectorz version, at least the way I have the code written right now. I suspect the 0.27.0 release may help there as well.

Answer 1

If you're not tied to la4j, the Vectorz package (which I maintain) has some tools to do these kinds of operations very efficiently. This is possible because of two features:

• Sparse storage of data
• Lightweight mutable "views", so you can mutate rows of a matrix as vectors in-place

The strategy I would use is:

• Create a VectorMatrixMN to store a matrix as a collection of sparse vector rows
• Use a SparseIndexedVector for each row, which is an efficient format for mostly-zero data

Normalising the rows of the matrix can then be done with the following code:

VectorMatrixMN m = ....

for (int i=0; i<SIZE; i++) {
    AVector row=m.getRow(i);
    double sum=row.elementSum();
    if (sum>0) {
        row.divide(sum);
    } else {
        m.setRow(i, new RepeatedElementVector(SIZE,1.0/SIZE));
    }
}

Note that this code is modifying the rows in-place, so you don't need to do anything like "setRow" to get the data back in the matrix.

Using this configuration with a 32,000 x 32,000 sparse matrix and a density of 100 non-zero values per row, I timed this at less than 32ms to normalise the whole matrix with this code (i.e. about 10ns per non-zero element == 0.03ns per matrix element : so you are clearly getting big benefits by exploiting the sparsity).

You could also optionally use a ZeroVector for rows that are all-zero (these will be even faster, but impose some extra constraints since ZeroVectors are immutable.....)

EDIT:

I've coded a complete example that demonstrates using sparse matrices for a use case very similar to this question:

• https://github.com/mikera/vectorz/blob/develop/src/test/java/example/SparseMatrix.java

Answer 2

I'm the author of the la4j library. I do see several places of improvement in your code. Here is my advice:

Calling getRow (as well as setRow) is always a bad idea (especially for sparse matrices), since it launches a full-copying of the matrix row. I would suggest you to avoid such calls. Thus, w/o getRow/setRow code should looks like:

SparseMatrix t = new CRSMatrix(n, n);

double uniformWeight = (double) 1 / n; // used when the rowSum is zero
for (int i = 0; i < n; i++) {
  double rowSum = t.foldRow(i, Matrices.asSumAccumulator(0.0));
  if (rowSum > 0.0) {
    MatrixFunction divider = Matrices.asDivFunction(rowSum);
    for (int j = 0; j < n; j++) {
      // TODO: I should probably think about `updateRow` method
      //       in order to avoid this loop
      t.update(i, j, divider);
    }
  } else {
    for (int j = 0; j < n; j++) {
      t.set(i, j, uniformWeight);
    }
  }
}

Please, try this. I didn't compile it, but it should work.

Update

Using a boolean array in order to keep track of the same rows is a fantastic idea. The main bottle-neck here is the loop:

for (int j = 0; j < n; j++) {
  t.set(i, j, uniformWeight);
}

Here we're completely ruining the performance/footprint of the sparse matrice since assigning the entire row to the same value. So, I would say, combining these two ideas together: avoid getRow/setRow + extra array with flags (I would use BitSet instead, it is much efficien in terms of footprint) should give you an awesome performance.

Thank you for using the la4j library, and please, report any issues with performance/functional to mail-list, or GitHub page. All references are available here: http://la4j.org.