/*
* JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
* Copyright (C) 2006 - JScience (http://jscience.org/)
* All rights reserved.
*
* Permission to use, copy, modify, and distribute this software is
* freely granted, provided that this notice is preserved.
*/
package org.jscience.mathematics.vector;
import java.util.Iterator;
import java.util.List;
import javolution.context.ObjectFactory;
import javolution.lang.MathLib;
import javolution.util.FastComparator;
import javolution.util.FastMap;
import javolution.util.FastTable;
import javolution.util.Index;
import org.jscience.mathematics.structure.Field;
/**
* This class represents a matrix made of {@link SparseVector sparse
* vectors} (as rows). To create a sparse matrix made of column vectors the
* {@link #transpose} method can be used.
* For example:[code]
* SparseVector column0 = SparseVector.valueOf(...);
* SparseVector column1 = SparseVector.valueOf(...);
* SparseMatrix M = SparseMatrix.valueOf(column0, column1).transpose();
* [/code]
* As for any concrete {@link org.jscience.mathematics.structure.Structure
* structure}, this class is declared final (otherwise most
* operations would have to be overridden to return the appropriate type).
* Specialized dense matrix should sub-class {@link Matrix} directly.
* For example:[code]
* // Extension through composition.
* final class BandMatrix > extends Matrix {
* private SparseMatrix _value;
* ...
* public BandMatrix opposite() { // Returns the right type.
* return BandMatrix.valueOf(_value.opposite());
* }
* ...
* }[/code]
*
* @author Jean-Marie Dautelle
* @version 3.3, January 2, 2007
*/
public final class SparseMatrix> extends Matrix {
/**
* Holds the number of columns n or the number of rows m if transposed.
*/
int _n;
/**
* Holds the zero.
*/
F _zero;;
/**
* Indicates if this matrix is transposed (the rows are then the columns).
*/
boolean _transposed;
/**
* Holds this matrix rows (or columns when transposed).
*/
final FastTable> _rows = new FastTable>();
/**
* Returns the sparse square matrix having the specified diagonal
* vector. This method is typically used to create an identity matrix.
* For example:[code]
* SparseMatrix IDENTITY = Matrix.valueOf(
* DenseVector.valueOf({Real.ONE, Real.ONE, Real.ONE}), Real.ZERO);
* [/code]
*
* @param diagonal the diagonal vector.
* @param zero value of non-diagonal elements.
* @return a square matrix with diagonal on the diagonal and
* zero elsewhere.
*/
public static > SparseMatrix valueOf(
Vector diagonal, F zero) {
int n = diagonal.getDimension();
SparseMatrix M = SparseMatrix.newInstance(n, zero, false);
for (int i = 0; i < n; i++) {
SparseVector row = SparseVector.valueOf(n, zero, i, diagonal
.get(i));
M._rows.add(row);
}
return M;
}
/**
* Returns a sparse matrix holding the specified row vectors
* (column vectors if {@link #transpose transposed}).
*
* @param rows the row vectors.
* @return the matrix having the specified rows.
* @throws DimensionException if the rows do not have the same dimension.
*/
public static > SparseMatrix valueOf(
SparseVector... rows) {
final int n = rows[0]._dimension;
final F zero = rows[0]._zero;
SparseMatrix M = SparseMatrix.newInstance(n, zero, false);
for (int i = 0, m = rows.length; i < m; i++) {
SparseVector rowi = rows[i];
if (rowi._dimension != n)
throw new DimensionException(
"All vectors must have the same dimension.");
if (!zero.equals(rowi._zero))
throw new DimensionException(
"All vectors must have the same zero element.");
M._rows.add(rowi);
}
return M;
}
/**
* Returns a sparse matrix holding the row vectors from the specified
* collection (column vectors if {@link #transpose transposed}).
*
* @param rows the list of row vectors.
* @return the matrix having the specified rows.
* @throws DimensionException if the rows do not have the same dimension.
*/
public static > SparseMatrix valueOf(
List> rows) {
final int n = rows.get(0)._dimension;
final F zero = rows.get(0)._zero;
SparseMatrix M = SparseMatrix.newInstance(n, zero, false);
Iterator> iterator = rows.iterator();
for (int i = 0, m = rows.size(); i < m; i++) {
SparseVector rowi = iterator.next();
if (rowi.getDimension() != n)
throw new DimensionException(
"All vectors must have the same dimension.");
if (!zero.equals(rowi._zero))
throw new DimensionException(
"All vectors must have the same zero element.");
M._rows.add(rowi);
}
return M;
}
/**
* Returns a sparse matrix equivalent to the specified matrix but with
* the zero elements removed using the default object equality comparator.
*
* @param that the matrix to convert.
* @param zero the zero element for the sparse vector to return.
* @return SparseMatrix.valueOf(that, zero, FastComparator.DEFAULT) or a dense matrix holding the same elements
*/
public static > SparseMatrix valueOf(Matrix that, F zero) {
return SparseMatrix.valueOf(that, zero, FastComparator.DEFAULT);
}
/**
* Returns a sparse matrix equivalent to the specified matrix but with
* the zero elements removed using the specified object equality comparator.
*
* @param that the matrix to convert.
* @param zero the zero element for the sparse vector to return.
* @param comparator the comparator used to determinate zero equality.
* @return that or a dense matrix holding the same elements
* as the specified matrix.
*/
public static > SparseMatrix valueOf(Matrix that,
F zero, FastComparator comparator) {
if (that instanceof SparseMatrix)
return (SparseMatrix) that;
int n = that.getNumberOfColumns();
int m = that.getNumberOfRows();
SparseMatrix M = SparseMatrix.newInstance(n, zero, false);
for (int i = 0; i < m; i++) {
SparseVector rowi = SparseVector.valueOf(that.getRow(i), zero,
comparator);
M._rows.add(rowi);
}
return M;
}
/**
* Returns the value of the non-set elements for this sparse matrix.
*
* @return the element corresponding to zero.
*/
public F getZero() {
return _zero;
}
@Override
public int getNumberOfRows() {
return _transposed ? _n : _rows.size();
}
@Override
public int getNumberOfColumns() {
return _transposed ? _rows.size() : _n;
}
@Override
public F get(int i, int j) {
return _transposed ? _rows.get(j).get(i) : _rows.get(i).get(j);
}
@Override
public SparseVector getRow(int i) {
if (!_transposed)
return _rows.get(i);
// Else transposed.
int n = _rows.size();
int m = _n;
if ((i < 0) || (i >= m))
throw new DimensionException();
SparseVector V = SparseVector.newInstance(n, _zero);
for (int j = 0; j < n; j++) {
SparseVector row = _rows.get(j);
F e = row._elements.get(Index.valueOf(i));
if (e != null) {
V._elements.put(Index.valueOf(j), e);
}
}
return V;
}
@Override
public SparseVector getColumn(int j) {
if (_transposed)
return _rows.get(j);
int m = _rows.size();
if ((j < 0) || (j >= _n))
throw new DimensionException();
SparseVector V = SparseVector.newInstance(_n, _zero);
for (int i = 0; i < m; i++) {
SparseVector row = _rows.get(i);
F e = row._elements.get(Index.valueOf(j));
if (e != null) {
V._elements.put(Index.valueOf(i), e);
}
}
return V;
}
@Override
public SparseVector getDiagonal() {
int m = this.getNumberOfRows();
int n = this.getNumberOfColumns();
int dimension = MathLib.min(m, n);
SparseVector V = SparseVector.newInstance(_n, _zero);
for (int i = 0; i < dimension; i++) {
SparseVector row = _rows.get(i);
F e = row._elements.get(Index.valueOf(i));
if (e != null) {
V._elements.put(Index.valueOf(i), e);
}
}
return V;
}
@Override
public SparseMatrix opposite() {
SparseMatrix M = SparseMatrix.newInstance(_n, _zero, _transposed);
for (int i = 0, p = _rows.size(); i < p; i++) {
M._rows.add(_rows.get(i).opposite());
}
return M;
}
@Override
public SparseMatrix plus(Matrix that) {
if (this.getNumberOfRows() != that.getNumberOfRows())
throw new DimensionException();
SparseMatrix M = SparseMatrix.newInstance(_n, _zero, _transposed);
for (int i = 0, p = _rows.size(); i < p; i++) {
M._rows.add(_rows.get(i).plus(
_transposed ? that.getColumn(i) : that.getRow(i)));
}
return M;
}
@Override
public SparseMatrix minus(Matrix that) { // Returns more specialized type.
return this.plus(that.opposite());
}
@Override
public SparseMatrix times(F k) {
SparseMatrix M = SparseMatrix.newInstance(_n, _zero, _transposed);
for (int i = 0, p = _rows.size(); i < p; i++) {
M._rows.add(_rows.get(i).times(k));
}
return M;
}
@Override
public SparseVector times(Vector v) {
if (v.getDimension() != this.getNumberOfColumns())
throw new DimensionException();
final int m = this.getNumberOfRows();
SparseVector V = SparseVector.newInstance(m, _zero);
for (int i = 0; i < m; i++) {
F e = this.getRow(i).times(v);
if (!_zero.equals(e)) {
V._elements.put(Index.valueOf(i), e);
}
}
return V;
}
@Override
public SparseMatrix times(Matrix that) {
final int m = this.getNumberOfRows();
final int n = this.getNumberOfColumns();
final int p = that.getNumberOfColumns();
if (that.getNumberOfRows() != n)
throw new DimensionException();
// Creates a mxp matrix in transposed form (p columns vectors of size m)
FastTable> rows = this.getRows();
SparseMatrix M = SparseMatrix.newInstance(m, _zero, true);
for (int j = 0; j < p; j++) {
Vector thatColj = that.getColumn(j);
SparseVector column = SparseVector.newInstance(m, _zero);
M._rows.add(column); // M is transposed.
for (int i = 0; i < m; i++) {
F e = rows.get(i).times(thatColj);
if (!_zero.equals(e)) {
column._elements.put(Index.valueOf(i), e);
}
}
}
return M;
}
private FastTable> getRows() {
if (!_transposed)
return _rows;
FastTable> rows = FastTable.newInstance();
for (int i = 0; i < _n; i++) {
rows.add(this.getRow(i));
}
return rows;
}
@Override
public SparseMatrix inverse() {
if (!isSquare())
throw new DimensionException("Matrix not square");
F detInv = this.determinant().inverse();
SparseMatrix A = this.adjoint();
// Multiply adjoint elements with 1 / determinant.
for (int i = 0, m = A._rows.size(); i < m; i++) {
SparseVector row = A._rows.get(i);
for (FastMap.Entry e = row._elements.head(), end = row._elements
.tail(); (e = e.getNext()) != end;) {
F element = e.getValue();
e.setValue(detInv.times(element));
}
}
return A;
}
@Override
public F determinant() {
if (!isSquare())
throw new DimensionException("Matrix not square");
if (_n == 1)
return this.get(0, 0);
// Expansion by minors (also known as Laplacian)
// This algorithm is division free but too slow for dense matrix.
SparseVector row0 = this.getRow(0);
F det = null;
for (FastMap.Entry e = row0._elements.head(), end = row0._elements
.tail(); (e = e.getNext()) != end;) {
int i = e.getKey().intValue();
F d = e.getValue().times(cofactor(0, i));
if (i % 2 != 0) {
d = d.opposite();
}
det = (det == null) ? d : det.plus(d);
}
return det == null ? _zero : det;
}
@Override
public Matrix solve(Matrix y) {
return this.inverse().times(y);
}
@Override
public SparseMatrix transpose() {
SparseMatrix M = SparseMatrix.newInstance(_n, _zero, !_transposed);
M._rows.addAll(this._rows);
return M;
}
@Override
public F cofactor(int i, int j) {
if (_transposed) {
int k = i;
i = j;
j = k; // Swaps i,j
}
int m = _rows.size();
SparseMatrix M = SparseMatrix.newInstance(m - 1, _zero, _transposed);
for (int k1 = 0; k1 < m; k1++) {
if (k1 == i)
continue;
SparseVector row = _rows.get(k1);
SparseVector V = SparseVector.newInstance(_n - 1, _zero);
M._rows.add(V);
for (FastMap.Entry e = row._elements.head(), end = row._elements
.tail(); (e = e.getNext()) != end;) {
int index = e.getKey().intValue();
if (index < j) {
V._elements.put(e.getKey(), e.getValue());
} else if (index > j) { // Position shifted (index minus one).
V._elements.put(Index.valueOf(index - 1), e.getValue());
} // Else don't copy element at j.
}
}
return M.determinant();
}
@Override
public SparseMatrix adjoint() {
SparseMatrix M = SparseMatrix.newInstance(_n, _zero, _transposed);
int m = _rows.size();
for (int i = 0; i < m; i++) {
SparseVector row = SparseVector.newInstance(_n, _zero);
M._rows.add(row);
for (int j = 0; j < _n; j++) {
F cofactor = _transposed ? cofactor(j, i) : cofactor(i, j);
if (!_zero.equals(cofactor)) {
row._elements
.put(Index.valueOf(j),
((i + j) % 2 == 0) ? cofactor : cofactor
.opposite());
}
}
}
return M.transpose();
}
@Override
public SparseMatrix tensor(Matrix that) {
final int thism = this.getNumberOfRows();
final int thisn = this.getNumberOfColumns();
final int thatm = that.getNumberOfRows();
final int thatn = that.getNumberOfColumns();
int n = thisn * thatn; // Number of columns,
int m = thism * thatm; // Number of rows.
SparseMatrix M = SparseMatrix.newInstance(n, _zero, false);
for (int i=0; i < m; i++) { // Row index.
final int i_rem_thatm = i % thatm;
final int i_div_thatm = i / thatm;
SparseVector row = SparseVector.newInstance(n, _zero);
M._rows.add(row);
SparseVector thisRow = this.getRow(i_div_thatm);
for (FastMap.Entry e = thisRow._elements.head(),
end = thisRow._elements.tail(); (e = e.getNext()) != end;) {
F a = e.getValue();
int j = e.getKey().intValue();
for (int k=0; k < thatn; k++) {
F b = that.get(i_rem_thatm, k);
if (!b.equals(_zero)) {
row._elements.put(Index.valueOf(j * thatn + k), a.times(b));
}
}
}
}
return M;
}
@Override
public SparseVector vectorization() {
SparseVector V = SparseVector.newInstance(_n
* this.getNumberOfRows(), _zero);
int offset = 0;
for (int j = 0, n = this.getNumberOfColumns(); j < n; j++) {
SparseVector column = this.getColumn(j);
for (FastMap.Entry e = column._elements.head(), end = column._elements
.tail(); (e = e.getNext()) != end;) {
V._elements.put(Index.valueOf(e.getKey().intValue() + offset),
e.getValue());
}
offset += this.getNumberOfRows();
}
return V;
}
@SuppressWarnings("unchecked")
@Override
public SparseMatrix copy() {
SparseMatrix M = newInstance(_n, (F)_zero.copy(), _transposed);
for (SparseVector row : _rows) {
M._rows.add(row.copy());
}
return M;
}
///////////////////////
// Factory creation. //
///////////////////////
@SuppressWarnings("unchecked")
static > SparseMatrix newInstance(int n, F zero,
boolean transposed) {
SparseMatrix M = FACTORY.object();
M._n = n;
M._zero = zero;
M._transposed = transposed;
return M;
}
private static final ObjectFactory FACTORY = new ObjectFactory() {
@Override
protected SparseMatrix create() {
return new SparseMatrix();
}
@Override
protected void cleanup(SparseMatrix matrix) {
matrix._rows.reset();
}
};
private SparseMatrix() {
}
private static final long serialVersionUID = 1L;
}
Ads help maintain this website.