src/jalview/math/SparseMatrix.java

   1 package jalview.math;
   2
   3 import jalview.ext.android.SparseDoubleArray;
   4
   5 /**
   6  * A variant of Matrix intended for use for sparse (mostly zero) matrices. This
   7  * class uses a SparseDoubleArray to hold each row of the matrix. The sparse
   8  * array only stores non-zero values. This gives a smaller memory footprint, and
   9  * fewer matrix calculation operations, for mostly zero matrices.
  10  *
  11  * @author gmcarstairs
  12  */
  13 public class SparseMatrix extends Matrix
  14 {
  15   /*
  16    * we choose columns for the sparse arrays as this allows
  17    * optimisation of the preMultiply() method used in PCA.run()
  18    */
  19   SparseDoubleArray[] sparseColumns;
  20
  21   /**
  22    * Constructor given data in [row][column] order
  23    *
  24    * @param v
  25    */
  26   public SparseMatrix(double[][] v)
  27   {
  28     rows = v.length;
  29     if (rows > 0)
  30     {
  31       cols = v[0].length;
  32     }
  33     sparseColumns = new SparseDoubleArray[cols];
  34
  35     /*
  36      * transpose v[row][col] into [col][row] order
  37      */
  38     for (int col = 0; col < cols; col++)
  39     {
  40       SparseDoubleArray sparseColumn = new SparseDoubleArray();
  41       sparseColumns[col] = sparseColumn;
  42       for (int row = 0; row < rows; row++)
  43       {
  44         double value = v[row][col];
  45         if (value != 0d)
  46         {
  47           sparseColumn.put(row, value);
  48         }
  49       }
  50     }
  51   }
  52
  53   /**
  54    * Answers the value at row i, column j
  55    */
  56   @Override
  57   public double getValue(int i, int j)
  58   {
  59     return sparseColumns[j].get(i);
  60   }
  61
  62   /**
  63    * Sets the value at row i, column j to val
  64    */
  65   @Override
  66   public void setValue(int i, int j, double val)
  67   {
  68     if (val == 0d)
  69     {
  70       sparseColumns[j].delete(i);
  71     }
  72     else
  73     {
  74       sparseColumns[j].put(i, val);
  75     }
  76   }
  77
  78   @Override
  79   public double[] getColumn(int i)
  80   {
  81     double[] col = new double[height()];
  82
  83     SparseDoubleArray vals = sparseColumns[i];
  84     for (int nonZero = 0; nonZero < vals.size(); nonZero++)
  85     {
  86       col[vals.keyAt(nonZero)] = vals.valueAt(nonZero);
  87     }
  88     return col;
  89   }
  90
  91   @Override
  92   public MatrixI copy()
  93   {
  94     double[][] vals = new double[height()][width()];
  95     for (int i = 0; i < height(); i++)
  96     {
  97       vals[i] = getRow(i);
  98     }
  99     return new SparseMatrix(vals);
 100   }
 101
 102   @Override
 103   public MatrixI transpose()
 104   {
 105     double[][] out = new double[cols][rows];
 106
 107     /*
 108      * for each column...
 109      */
 110     for (int i = 0; i < cols; i++)
 111     {
 112       /*
 113        * put non-zero values into the corresponding row
 114        * of the transposed matrix
 115        */
 116       SparseDoubleArray vals = sparseColumns[i];
 117       for (int nonZero = 0; nonZero < vals.size(); nonZero++)
 118       {
 119         out[i][vals.keyAt(nonZero)] = vals.valueAt(nonZero);
 120       }
 121     }
 122
 123     return new SparseMatrix(out);
 124   }
 125
 126   /**
 127    * Answers a new matrix which is the product in.this. If the product contains
 128    * less than 20% non-zero values, it is returned as a SparseMatrix, else as a
 129    * Matrix.
 130    * <p>
 131    * This method is optimised for the sparse arrays which store column values
 132    * for a SparseMatrix. Note that postMultiply is not so optimised. That would
 133    * require redundantly also storing sparse arrays for the rows, which has not
 134    * been done. Currently only preMultiply is used in Jalview.
 135    */
 136   @Override
 137   public MatrixI preMultiply(MatrixI in)
 138   {
 139     if (in.width() != rows)
 140     {
 141       throw new IllegalArgumentException("Can't pre-multiply " + this.rows
 142               + " rows by " + in.width() + " columns");
 143     }
 144     double[][] tmp = new double[in.height()][this.cols];
 145
 146     long count = 0L;
 147     for (int i = 0; i < in.height(); i++)
 148     {
 149       for (int j = 0; j < this.cols; j++)
 150       {
 151         /*
 152          * result[i][j] is the vector product of
 153          * in.row[i] and this.column[j]
 154          * we only need to use non-zero values from the column
 155          */
 156         SparseDoubleArray vals = sparseColumns[j];
 157         boolean added = false;
 158         for (int nonZero = 0; nonZero < vals.size(); nonZero++)
 159         {
 160           int myRow = vals.keyAt(nonZero);
 161           double myValue = vals.valueAt(nonZero);
 162           tmp[i][j] += (in.getValue(i, myRow) * myValue);
 163           added = true;
 164         }
 165         if (added && tmp[i][j] != 0d)
 166         {
 167           count++; // non-zero entry in product
 168         }
 169       }
 170     }
 171
 172     /*
 173      * heuristic rule - if product is more than 80% zero
 174      * then construct a SparseMatrix, else a Matrix
 175      */
 176     if (count * 5 < in.height() * cols)
 177     {
 178       return new SparseMatrix(tmp);
 179     }
 180     else
 181     {
 182       return new Matrix(tmp);
 183     }
 184   }
 185
 186   @Override
 187   protected double divideValue(int i, int j, double divisor)
 188   {
 189     if (divisor == 0d)
 190     {
 191       return getValue(i, j);
 192     }
 193     double v = sparseColumns[j].divide(i, divisor);
 194     return v;
 195   }
 196
 197   @Override
 198   protected double addValue(int i, int j, double addend)
 199   {
 200     double v = sparseColumns[j].add(i, addend);
 201     return v;
 202   }
 203
 204   /**
 205    * Returns the fraction of the whole matrix size that is actually modelled in
 206    * sparse arrays (normally, the non-zero values)
 207    *
 208    * @return
 209    */
 210   public float getFillRatio()
 211   {
 212     long count = 0L;
 213     for (SparseDoubleArray col : sparseColumns)
 214     {
 215       count += col.size();
 216     }
 217     return count / (float) (height() * width());
 218   }
 219 }