title: Efficient modification of the rows of a sparse matrix in Java
body: <p>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).  </p>
  
  <p>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.</p>
  
  <p>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 (&lt;10)</p>
  
  <p>I'm currently using the la4j matrix package, but I'm not in any way tied to it.  </p>
  
  <p>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).</p>
  
  <p>Three questions:</p>
  
  <p>1) Is there a better package or better approach to doing this efficiently?</p>
  
  <p>2) Should I not be using a sparse matrix representation for this?</p>
  
  <p>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?</p>
  
  <p>Thanks in advance!</p>
  
  <pre><code>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 &lt; n; i++) {
          Vector row = t.getRow(i);
          double rowSum = row.sum();
          if (rowSum &gt; 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);
          }
      }
  </code></pre>
  
  <p><strong>Update 1</strong></p>
  
  <p>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 <code>getRow</code> and <code>setRow</code> in that method.  Note that m2 (the second multiplicand) and m3 (the result matrix) are not sparse, if that matters.  Thanks in advance!</p>
  
  <pre><code>    boolean[] zeroRows = new boolean[n]; // all values default to false
      for (int i = 0; i &lt; 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 &gt; 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 &lt; a; i++) {
          if (zeroRows[i]) {
              v1 = uniformVector;
          } else {
              v1 = m1.getRow(i);
          }
          m3.setRow(i, v1.multiply(m2));
      }
      return m3;
  }
  </code></pre>
  
  <p><strong>Update 2</strong></p>
  
  <p>I really appreciate all the help from @Vladimir and @mikera.  For what it's worth, the version using <code>la4j</code> with the <code>hackMultiply</code> approach is pretty much identical in time use to the version using <code>vectorz</code> 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.  </p>