package jsat.linear;

import java.util.Arrays;
import java.util.Iterator;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.utils.SystemInfo;

/**
 * Creates a new Sparse Matrix where each row is backed by a sparse vector. 
 * 

* This implementation does not support the {@link #qr() QR} or {@link #lup() } * decompositions. *
* {@link #transposeMultiply(jsat.linear.Matrix, jsat.linear.Matrix, java.util.concurrent.ExecutorService) } currently does not use multiple cores. * * @author Edward Raff */ public class SparseMatrix extends Matrix { private static final long serialVersionUID = -4087445771022578544L; private SparseVector[] rows; /** * Creates a new sparse matrix * @param rows the number of rows for the matrix * @param cols the number of columns for the matrix * @param rowCapacity the initial capacity for non zero values for each row */ public SparseMatrix(int rows, int cols, int rowCapacity) { this.rows = new SparseVector[rows]; for(int i = 0; i < rows; i++) this.rows[i] = new SparseVector(cols, rowCapacity); } /** * Creates a new Sparse Matrix backed by the given array of SpareVectors. * Altering the array of any object in it will also alter the this matrix. * * @param rows the array to back this SparseMatrix */ public SparseMatrix(SparseVector[] rows) { this.rows = rows; for(int i = 0; i < rows.length; i++) if(rows[i].length() != rows[0].length()) throw new IllegalArgumentException("Row " + i + " has " + rows[i].length() + " columns instead of " + rows[0].length()); } /** * Creates a new sparse matrix * @param rows the number of rows for the matrix * @param cols the number of columns for the matrix */ public SparseMatrix(int rows, int cols) { this.rows = new SparseVector[rows]; for(int i = 0; i < rows; i++) this.rows[i] = new SparseVector(cols); } /** * Copy constructor * @param toCopy the object to copy */ protected SparseMatrix(SparseMatrix toCopy) { this.rows = new SparseVector[toCopy.rows.length]; for(int i = 0; i < rows.length; i++) this.rows[i] = toCopy.rows[i].clone(); } @Override public void mutableAdd(double c, Matrix B) { if(!Matrix.sameDimensions(this, B)) throw new ArithmeticException("Matrices must be the same dimension to be added"); for( int i = 0; i < rows.length; i++) rows[i].mutableAdd(c, B.getRowView(i)); } @Override public void mutableAdd(final double c, final Matrix B, ExecutorService threadPool) { if(!Matrix.sameDimensions(this, B)) throw new ArithmeticException("Matrices must be the same dimension to be added"); final CountDownLatch latch = new CountDownLatch(rows.length); for (int i = 0; i < rows.length; i++) { final int ii = i; threadPool.submit(new Runnable() { @Override public void run() { rows[ii].mutableAdd(c, B.getRowView(ii)); latch.countDown(); } }); } try { latch.await(); } catch (InterruptedException ex) { Logger.getLogger(SparseMatrix.class.getName()).log(Level.SEVERE, null, ex); } } @Override public void mutableAdd(double c) { for(SparseVector row : rows) row.mutableAdd(c); } @Override public void mutableAdd(final double c, ExecutorService threadPool) { final CountDownLatch latch = new CountDownLatch(rows.length); for(final SparseVector row : rows) { threadPool.submit(new Runnable() { @Override public void run() { row.mutableAdd(c); latch.countDown(); } }); } try { latch.await(); } catch (InterruptedException ex) { Logger.getLogger(SparseMatrix.class.getName()).log(Level.SEVERE, null, ex); } } @Override public void multiply(Vec b, double z, Vec c) { if(this.cols() != b.length()) throw new ArithmeticException("Matrix dimensions do not agree, [" + rows() +"," + cols() + "] x [" + b.length() + ",1]" ); if(this.rows() != c.length()) throw new ArithmeticException("Target vector dimension does not agree with matrix dimensions. Matrix has " + rows() + " rows but tagert has " + c.length()); for(int i = 0; i < rows(); i++) { SparseVector row = rows[i]; c.increment(i, row.dot(b)*z); } } @Override public void multiply(Matrix B, Matrix C) { if(!canMultiply(this, B)) throw new ArithmeticException("Matrix dimensions do not agree"); else if(this.rows() != C.rows() || B.cols() != C.cols()) throw new ArithmeticException("Target Matrix is no the correct size"); for (int i = 0; i < C.rows(); i++) { Vec Arowi = this.rows[i]; Vec Crowi = C.getRowView(i); for(IndexValue iv : Arowi) { final int k = iv.getIndex(); double a = iv.getValue(); Vec Browk = B.getRowView(k); Crowi.mutableAdd(a, Browk); } } } @Override public void multiply(final Matrix B, Matrix C, ExecutorService threadPool) { if (!canMultiply(this, B)) throw new ArithmeticException("Matrix dimensions do not agree"); else if (this.rows() != C.rows() || B.cols() != C.cols()) throw new ArithmeticException("Target Matrix is no the correct size"); final CountDownLatch latch = new CountDownLatch(C.rows()); for (int i = 0; i < C.rows(); i++) { final Vec Arowi = this.rows[i]; final Vec Crowi = C.getRowView(i); threadPool.submit(new Runnable() { @Override public void run() { for (IndexValue iv : Arowi) { final int k = iv.getIndex(); double a = iv.getValue(); Vec Browk = B.getRowView(k); Crowi.mutableAdd(a, Browk); } latch.countDown(); } }); } try { latch.await(); } catch (InterruptedException ex) { Logger.getLogger(SparseMatrix.class.getName()).log(Level.SEVERE, null, ex); } } @Override public void mutableMultiply(double c) { for(SparseVector row : rows) row.mutableMultiply(c); } @Override public void mutableMultiply(final double c, ExecutorService threadPool) { final CountDownLatch latch = new CountDownLatch(rows.length); for(final SparseVector row : rows) { threadPool.submit(new Runnable() { @Override public void run() { row.mutableMultiply(c); latch.countDown(); } }); } try { latch.await(); } catch (InterruptedException ex) { Logger.getLogger(SparseMatrix.class.getName()).log(Level.SEVERE, null, ex); } } @Override public Matrix[] lup() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. } @Override public Matrix[] lup(ExecutorService threadPool) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. } @Override public Matrix[] qr() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. } @Override public Matrix[] qr(ExecutorService threadPool) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. } @Override public void mutableTranspose() { for(int i = 0; i < rows()-1; i++) for(int j = i+1; j < cols(); j++) { double tmp = get(j, i); set(j, i, get(i, j)); set(i, j, tmp); } } @Override public void transpose(Matrix C) { if(this.rows() != C.cols() || this.cols() != C.rows()) throw new ArithmeticException("Target matrix does not have the correct dimensions"); C.zeroOut(); for(int row = 0; row < rows.length; row++) for(IndexValue iv : rows[row]) C.set(iv.getIndex(), row, iv.getValue()); } @Override public void transposeMultiply(Matrix B, Matrix C) { if(this.rows() != B.rows())//Normaly it is A_cols == B_rows, but we are doint A'*B, not A*B throw new ArithmeticException("Matrix dimensions do not agree"); else if(this.cols() != C.rows() || B.cols() != C.cols()) throw new ArithmeticException("Destination matrix does not have matching dimensions"); final SparseMatrix A = this; ///Should choose step size such that 2*NB2^2 * dataTypeSize <= CacheSize final int kLimit = this.rows(); for (int k = 0; k < kLimit; k++) { Vec bRow_k = B.getRowView(k); Vec aRow_k = A.getRowView(k); for (IndexValue iv : aRow_k)//iterating over "i" { Vec cRow_i = C.getRowView(iv.getIndex()); double a = iv.getValue();//A.get(k, i); cRow_i.mutableAdd(a, bRow_k); } } } @Override public void transposeMultiply(final Matrix B, final Matrix C, ExecutorService threadPool) { transposeMultiply(B, C);//TODO use the multiple threads } @Override public void transposeMultiply(double c, Vec b, Vec x) { if(this.rows() != b.length()) throw new ArithmeticException("Matrix dimensions do not agree, [" + cols() +"," + rows() + "] x [" + b.length() + ",1]" ); else if(this.cols() != x.length()) throw new ArithmeticException("Matrix dimensions do not agree with target vector"); for(IndexValue b_iv : b) x.mutableAdd(c*b_iv.getValue(), rows[b_iv.getIndex()]); } @Override public Vec getRowView(int r) { return rows[r]; } @Override public double get(int i, int j) { return rows[i].get(j); } @Override public void set(int i, int j, double value) { rows[i].set(j, value); } @Override public void increment(int i, int j, double value) { rows[i].increment(j, value); } @Override public int rows() { return rows.length; } @Override public int cols() { return rows[0].length(); } @Override public boolean isSparce() { return true; } @Override public void swapRows(int r1, int r2) { SparseVector tmp = rows[r2]; rows[r2] = rows[r1]; rows[r1] = tmp; } @Override public void zeroOut() { for(Vec row : rows) row.zeroOut(); } @Override public SparseMatrix clone() { return new SparseMatrix(this); } @Override public long nnz() { int nnz = 0; for(Vec v : rows) nnz += v.nnz(); return nnz; } @Override public void changeSize(int newRows, int newCols) { if(newRows <= 0) throw new ArithmeticException("Matrix must have a positive number of rows"); if(newCols <= 0) throw new ArithmeticException("Matrix must have a positive number of columns"); final int oldRows = rows.length; if(newCols != cols()) { for(int i = 0; i < rows.length; i++) { final SparseVector row_i = rows[i]; while(row_i.getLastNonZeroIndex() >= newCols) row_i.set(row_i.getLastNonZeroIndex(), 0); row_i.setLength(newCols); } } //update new rows rows = Arrays.copyOf(rows, newRows); for(int i = oldRows; i < newRows; i++) rows[i] = new SparseVector(newCols); } @Override public void multiplyTranspose(Matrix B, Matrix C) { if(this.cols() != B.cols()) throw new ArithmeticException("Matrix dimensions do not agree"); else if (this.rows() != C.rows() || B.rows() != C.cols()) throw new ArithmeticException("Target Matrix is no the correct size"); for (int i = 0; i < this.rows(); i++) { final SparseVector A_i = this.rows[i]; for (int j = 0; j < B.rows(); j++) { final Vec B_j = B.getRowView(j); double C_ij = 0; if(!B_j.isSparse())//B is dense, lets do this the easy way { for (IndexValue iv : A_i) C_ij += iv.getValue() * B_j.get(iv.getIndex()); C.increment(i, j, C_ij); continue;//Skip early, we did it! } //else, sparse Iterator A_iter = A_i.getNonZeroIterator(); Iterator B_iter = B_j.getNonZeroIterator(); if(!B_iter.hasNext() || !A_iter.hasNext())//one is all zeros, nothing to do continue; IndexValue A_val = A_iter.next(); IndexValue B_val = B_iter.next(); while(A_val != null && B_val != null)//go add everything together! { if(A_val.getIndex() == B_val.getIndex())//inc and bump both { C_ij += A_val.getValue()*B_val.getValue(); if(A_iter.hasNext()) A_val = A_iter.next(); else A_val = null; if(B_iter.hasNext()) B_val = B_iter.next(); else B_val = null; } else if(A_val.getIndex() < B_val.getIndex())//A is behind, bump it { if(A_iter.hasNext()) A_val = A_iter.next(); else A_val = null; } else//B is behind, bump it { if(B_iter.hasNext()) B_val = B_iter.next(); else B_val = null; } } C.increment(i, j, C_ij); } } } @Override public void multiplyTranspose(final Matrix B, final Matrix C, ExecutorService threadPool) { if(this.cols() != B.cols()) throw new ArithmeticException("Matrix dimensions do not agree"); else if (this.rows() != C.rows() || B.rows() != C.cols()) throw new ArithmeticException("Target Matrix is no the correct size"); final SparseMatrix A = this; final CountDownLatch latch = new CountDownLatch(SystemInfo.LogicalCores); for(int id = 0; id < SystemInfo.LogicalCores; id++) { final int ID = id; threadPool.submit(new Runnable() { @Override public void run() { try{ for (int i = ID; i < A.rows(); i += SystemInfo.LogicalCores) { final SparseVector A_i = A.rows[i]; for (int j = 0; j < B.rows(); j++) { final Vec B_j = B.getRowView(j); double C_ij = 0; if(!B_j.isSparse())//B is dense, lets do this the easy way { for (IndexValue iv : A_i) C_ij += iv.getValue() * B_j.get(iv.getIndex()); C.increment(i, j, C_ij); continue;//Skip early, we did it! } //else, sparse Iterator A_iter = A_i.getNonZeroIterator(); Iterator B_iter = B_j.getNonZeroIterator(); if(!B_iter.hasNext() || !A_iter.hasNext())//one is all zeros, nothing to do continue; IndexValue A_val = A_iter.next(); IndexValue B_val = B_iter.next(); while(A_val != null && B_val != null)//go add everything together! { if(A_val.getIndex() == B_val.getIndex())//inc and bump both { C_ij += A_val.getValue()*B_val.getValue(); if(A_iter.hasNext()) A_val = A_iter.next(); else A_val = null; if(B_iter.hasNext()) B_val = B_iter.next(); else B_val = null; } else if(A_val.getIndex() < B_val.getIndex())//A is behind, bump it { if(A_iter.hasNext()) A_val = A_iter.next(); else A_val = null; } else//B is behind, bump it { if(B_iter.hasNext()) B_val = B_iter.next(); else B_val = null; } } C.increment(i, j, C_ij); } } } catch(Exception ex) { ex.printStackTrace(); } System.out.println(ID + " fin"); latch.countDown(); } }); } try { latch.await(); } catch (InterruptedException ex) { Logger.getLogger(SparseMatrix.class.getName()).log(Level.SEVERE, null, ex); } } }

Ads help maintain this website.