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