Merge branch 'features/JAL-2446NCList' into features/JAL-2574findFeaturesByColumn
[jalview.git] / 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].divide(i, 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 }