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)
53 sparseColumns = new SparseDoubleArray[cols];
56 * transpose v[row][col] into [col][row] order
58 for (int col = 0; col < cols; col++)
60 SparseDoubleArray sparseColumn = new SparseDoubleArray();
61 sparseColumns[col] = sparseColumn;
62 for (int row = 0; row < rows; row++)
64 double value = v[row][col];
67 sparseColumn.put(row, value);
74 * Answers the value at row i, column j
77 public double getValue(int i, int j)
79 return sparseColumns[j].get(i);
83 * Sets the value at row i, column j to val
86 public void setValue(int i, int j, double val)
90 sparseColumns[j].delete(i);
94 sparseColumns[j].put(i, val);
99 public double[] getColumn(int i)
101 double[] col = new double[height()];
103 SparseDoubleArray vals = sparseColumns[i];
104 for (int nonZero = 0; nonZero < vals.size(); nonZero++)
106 col[vals.keyAt(nonZero)] = vals.valueAt(nonZero);
112 public MatrixI copy()
114 double[][] vals = new double[height()][width()];
115 for (int i = 0; i < height(); i++)
119 return new SparseMatrix(vals);
123 public MatrixI transpose()
125 double[][] out = new double[cols][rows];
130 for (int i = 0; i < cols; i++)
133 * put non-zero values into the corresponding row
134 * of the transposed matrix
136 SparseDoubleArray vals = sparseColumns[i];
137 for (int nonZero = 0; nonZero < vals.size(); nonZero++)
139 out[i][vals.keyAt(nonZero)] = vals.valueAt(nonZero);
143 return new SparseMatrix(out);
147 * Answers a new matrix which is the product in.this. If the product contains
148 * less than 20% non-zero values, it is returned as a SparseMatrix, else as a
151 * This method is optimised for the sparse arrays which store column values
152 * for a SparseMatrix. Note that postMultiply is not so optimised. That would
153 * require redundantly also storing sparse arrays for the rows, which has not
154 * been done. Currently only preMultiply is used in Jalview.
157 public MatrixI preMultiply(MatrixI in)
159 if (in.width() != rows)
161 throw new IllegalArgumentException("Can't pre-multiply " + this.rows
162 + " rows by " + in.width() + " columns");
164 double[][] tmp = new double[in.height()][this.cols];
167 for (int i = 0; i < in.height(); i++)
169 for (int j = 0; j < this.cols; j++)
172 * result[i][j] is the vector product of
173 * in.row[i] and this.column[j]
174 * we only need to use non-zero values from the column
176 SparseDoubleArray vals = sparseColumns[j];
177 boolean added = false;
178 for (int nonZero = 0; nonZero < vals.size(); nonZero++)
180 int myRow = vals.keyAt(nonZero);
181 double myValue = vals.valueAt(nonZero);
182 tmp[i][j] += (in.getValue(i, myRow) * myValue);
185 if (added && tmp[i][j] != 0d)
187 count++; // non-zero entry in product
193 * heuristic rule - if product is more than 80% zero
194 * then construct a SparseMatrix, else a Matrix
196 if (count * 5 < in.height() * cols)
198 return new SparseMatrix(tmp);
202 return new Matrix(tmp);
207 protected double divideValue(int i, int j, double divisor)
211 return getValue(i, j);
213 double v = sparseColumns[j].divide(i, divisor);
218 protected double addValue(int i, int j, double addend)
220 double v = sparseColumns[j].add(i, addend);
225 * Returns the fraction of the whole matrix size that is actually modelled in
226 * sparse arrays (normally, the non-zero values)
230 public float getFillRatio()
233 for (SparseDoubleArray col : sparseColumns)
237 return count / (float) (height() * width());