2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
7 * Jalview is free software: you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation, either version 3
10 * of the License, or (at your option) any later version.
12 * Jalview is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty
14 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
19 * The Jalview Authors are detailed in the 'AUTHORS' file.
23 import jalview.ext.android.SparseDoubleArray;
26 * A variant of Matrix intended for use for sparse (mostly zero) matrices. This
27 * class uses a SparseDoubleArray to hold each row of the matrix. The sparse
28 * array only stores non-zero values. This gives a smaller memory footprint, and
29 * fewer matrix calculation operations, for mostly zero matrices.
33 public class SparseMatrix extends Matrix
36 * we choose columns for the sparse arrays as this allows
37 * optimisation of the preMultiply() method used in PCA.run()
39 SparseDoubleArray[] sparseColumns;
42 * Constructor given data in [row][column] order
46 public SparseMatrix(double[][] v)
48 super(v.length, v.length > 0 ? v[0].length : 0);
50 sparseColumns = new SparseDoubleArray[cols];
53 * transpose v[row][col] into [col][row] order
55 for (int col = 0; col < cols; col++)
57 SparseDoubleArray sparseColumn = new SparseDoubleArray();
58 sparseColumns[col] = sparseColumn;
59 for (int row = 0; row < rows; row++)
61 double value = v[row][col];
64 sparseColumn.put(row, value);
71 * Answers the value at row i, column j
74 public double getValue(int i, int j)
76 return sparseColumns[j].get(i);
80 * Sets the value at row i, column j to val
83 public void setValue(int i, int j, double val)
87 sparseColumns[j].delete(i);
91 sparseColumns[j].put(i, val);
96 public double[] getColumn(int i)
98 double[] col = new double[height()];
100 SparseDoubleArray vals = sparseColumns[i];
101 for (int nonZero = 0; nonZero < vals.size(); nonZero++)
103 col[vals.keyAt(nonZero)] = vals.valueAt(nonZero);
109 public MatrixI copy()
111 double[][] vals = new double[height()][width()];
112 for (int i = 0; i < height(); i++)
116 return new SparseMatrix(vals);
120 public MatrixI transpose()
122 double[][] out = new double[cols][rows];
127 for (int i = 0; i < cols; i++)
130 * put non-zero values into the corresponding row
131 * of the transposed matrix
133 SparseDoubleArray vals = sparseColumns[i];
134 for (int nonZero = 0; nonZero < vals.size(); nonZero++)
136 out[i][vals.keyAt(nonZero)] = vals.valueAt(nonZero);
140 return new SparseMatrix(out);
144 * Answers a new matrix which is the product in.this. If the product contains
145 * less than 20% non-zero values, it is returned as a SparseMatrix, else as a
148 * This method is optimised for the sparse arrays which store column values
149 * for a SparseMatrix. Note that postMultiply is not so optimised. That would
150 * require redundantly also storing sparse arrays for the rows, which has not
151 * been done. Currently only preMultiply is used in Jalview.
154 public MatrixI preMultiply(MatrixI in)
156 if (in.width() != rows)
158 throw new IllegalArgumentException("Can't pre-multiply " + this.rows
159 + " rows by " + in.width() + " columns");
161 double[][] tmp = new double[in.height()][this.cols];
164 for (int i = 0; i < in.height(); i++)
166 for (int j = 0; j < this.cols; j++)
169 * result[i][j] is the vector product of
170 * in.row[i] and this.column[j]
171 * we only need to use non-zero values from the column
173 SparseDoubleArray vals = sparseColumns[j];
174 boolean added = false;
175 for (int nonZero = 0; nonZero < vals.size(); nonZero++)
177 int myRow = vals.keyAt(nonZero);
178 double myValue = vals.valueAt(nonZero);
179 tmp[i][j] += (in.getValue(i, myRow) * myValue);
182 if (added && tmp[i][j] != 0d)
184 count++; // non-zero entry in product
190 * heuristic rule - if product is more than 80% zero
191 * then construct a SparseMatrix, else a Matrix
193 if (count * 5 < in.height() * cols)
195 return new SparseMatrix(tmp);
199 return new Matrix(tmp);
204 protected double divideValue(int i, int j, double divisor)
208 return getValue(i, j);
210 double v = sparseColumns[j].divide(i, divisor);
215 protected double addValue(int i, int j, double addend)
217 double v = sparseColumns[j].add(i, addend);
222 * Returns the fraction of the whole matrix size that is actually modelled in
223 * sparse arrays (normally, the non-zero values)
227 public float getFillRatio()
230 for (SparseDoubleArray col : sparseColumns)
234 return count / (float) (height() * width());