/*
* 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.Comparator;
import javolution.context.StackContext;
import javolution.lang.MathLib;
import javolution.lang.Realtime;
import javolution.lang.ValueType;
import javolution.text.Text;
import javolution.text.TextBuilder;
import javolution.xml.XMLFormat;
import javolution.xml.stream.XMLStreamException;
import org.jscience.mathematics.structure.Field;
import org.jscience.mathematics.structure.Ring;
import org.jscience.mathematics.structure.VectorSpace;
/**
* This class represents a rectangular table of elements of a ring-like
* algebraic structure.
*
* Instances of this class can be used to resolve system of linear equations
* involving any kind of {@link Field Field} elements
* (e.g. {@link org.jscience.mathematics.number.Real Real},
* {@link org.jscience.mathematics.number.Complex Complex},
* {@link org.jscience.physics.amount.Amount Amount<?>},
* {@link org.jscience.mathematics.function.Function Function}, etc).
* For example:[code]
* // Creates a dense matrix (2x2) of Rational numbers.
* DenseMatrix M = DenseMatrix.valueOf(
* { Rational.valueOf(23, 45), Rational.valueOf(33, 75) },
* { Rational.valueOf(15, 31), Rational.valueOf(-20, 45)});
*
* // Creates a sparse matrix (16x2) of Real numbers.
* SparseMatrix M = SparseMatrix.valueOf(
* SparseVector.valueOf(16, Real.ZERO, 0, Real.valueOf(5)),
* SparseVector.valueOf(16, Real.ZERO, 15, Real.valueOf(-3)));
*
* // Creates a floating-point (64 bits) matrix (3x2).
* Float64Matrix M = Float64Matrix.valueOf(
* {{ 1.0, 2.0, 3.0}, { 4.0, 5.0, 6.0}});
*
* // Creates a complex single column matrix (1x2).
* ComplexMatrix M = ComplexMatrix.valueOf(
* {{ Complex.valueOf(1.0, 2.0), Complex.valueOf(4.0, 5.0)}}).transpose();
*
* // Creates an identity matrix (2x2) for modulo integer.
* SparseMatrix IDENTITY = SparseMatrix.valueOf(
* DenseVector.valueOf(ModuloInteger.ONE, ModuloInteger.ONE), ModuloInteger.ZERO);
* [/code]
*
* Non-commutative field multiplication is supported. Invertible square
* matrices may form a non-commutative field (also called a division
* ring). In which case this class may be used to resolve system of linear
* equations with matrix coefficients.
*
* Implementation Note: Matrices may use {@link
* javolution.context.StackContext StackContext} and {@link
* javolution.context.ConcurrentContext ConcurrentContext} in order to
* minimize heap allocation and accelerate calculations on multi-core
* systems.
*
* @author Jean-Marie Dautelle
* @version 3.3, December 24, 2006
* @see
* Wikipedia: Matrix (mathematics)
*/
public abstract class Matrix>
implements VectorSpace, F>, Ring>, ValueType, Realtime {
/**
* Holds the default XML representation for matrices. For example:[code]
*
* [/code]
*/
@SuppressWarnings("unchecked")
protected static final XMLFormat XML = new XMLFormat(
Matrix.class) {
@Override
public void read(InputElement xml, Matrix M) throws XMLStreamException {
// Nothing to do.
}
@Override
public void write(Matrix M, OutputElement xml)
throws XMLStreamException {
final int m = M.getNumberOfRows();
final int n = M.getNumberOfColumns();
xml.setAttribute("rows", m);
xml.setAttribute("columns", n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
xml.add(M.get(i, j));
}
}
}
};
/**
* Default constructor (for sub-classes).
*/
protected Matrix() {
}
/**
* Returns the number of rows m for this matrix.
*
* @return m, the number of rows.
*/
public abstract int getNumberOfRows();
/**
* Returns the number of columns n for this matrix.
*
* @return n, the number of columns.
*/
public abstract int getNumberOfColumns();
/**
* Returns a single element from this matrix.
*
* @param i the row index (range [0..m[).
* @param j the column index (range [0..n[).
* @return the element read at [i,j].
* @throws IndexOutOfBoundsException
* ((i < 0) || (i >= m)) || ((j < 0) || (j >= n))
*/
public abstract F get(int i, int j);
/**
* Returns the row identified by the specified index in this matrix.
*
* @param i the row index (range [0..m[).
* @return the vector holding the specified row.
* @throws IndexOutOfBoundsException (i < 0) || (i >= m)
*/
public abstract Vector getRow(int i);
/**
* Returns the column identified by the specified index in this matrix.
*
* @param j the column index (range [0..n[).
* @return the vector holding the specified column.
* @throws IndexOutOfBoundsException (j < 0) || (j >= n)
*/
public abstract Vector getColumn(int j);
/**
* Returns the diagonal vector.
*
* @return the vector holding the diagonal elements.
*/
public abstract Vector getDiagonal();
/**
* Returns the negation of this matrix.
*
* @return -this.
*/
public abstract Matrix opposite();
/**
* Returns the sum of this matrix with the one specified.
*
* @param that the matrix to be added.
* @return this + that.
* @throws DimensionException matrices's dimensions are different.
*/
public abstract Matrix plus(Matrix that);
/**
* Returns the difference between this matrix and the one specified.
*
* @param that the matrix to be subtracted.
* @return this - that.
* @throws DimensionException matrices's dimensions are different.
*/
public Matrix minus(Matrix that) {
return this.plus(that.opposite());
}
/**
* Returns the product of this matrix by the specified factor.
*
* @param k the coefficient multiplier.
* @return this · k
*/
public abstract Matrix times(F k);
/**
* Returns the product of this matrix by the specified vector.
*
* @param v the vector.
* @return this · v
* @throws DimensionException if
* v.getDimension() != this.getNumberOfColumns()
*/
public abstract Vector times(Vector v);
/**
* Returns the product of this matrix with the one specified.
*
* @param that the matrix multiplier.
* @return this · that.
* @throws DimensionException if
* this.getNumberOfColumns() != that.getNumberOfRows().
*/
public abstract Matrix times(Matrix that);
/**
* Returns the inverse of this matrix (must be square).
*
* @return 1 / this
* @throws DimensionException if this matrix is not square.
*/
public abstract Matrix inverse();
/**
* Returns this matrix divided by the one specified.
*
* @param that the matrix divisor.
* @return this / that.
* @throws DimensionException if that matrix is not square or dimensions
* do not match.
*/
public Matrix divide(Matrix that) {
return this.times(that.inverse());
}
/**
* Returns the inverse or pseudo-inverse if this matrix if not square.
*
* Note: To resolve the equation A * X = B,
* it is usually faster to calculate A.lu().solve(B)
* rather than A.inverse().times(B).
*
* @return the inverse or pseudo-inverse of this matrix.
*/
public Matrix pseudoInverse() {
if (isSquare())
return this.inverse();
Matrix thisTranspose = this.transpose();
return (thisTranspose.times(this)).inverse().times(thisTranspose);
}
/**
* Returns the determinant of this matrix.
*
* @return this matrix determinant.
* @throws DimensionException if this matrix is not square.
*/
public abstract F determinant();
/**
* Returns the transpose of this matrix.
*
* @return A'.
*/
public abstract Matrix transpose();
/**
* Returns the cofactor of an element in this matrix. It is the value
* obtained by evaluating the determinant formed by the elements not in
* that particular row or column.
*
* @param i the row index.
* @param j the column index.
* @return the cofactor of THIS[i,j].
* @throws DimensionException matrix is not square or its dimension
* is less than 2.
*/
public abstract F cofactor(int i, int j);
/**
* Returns the adjoint of this matrix. It is obtained by replacing each
* element in this matrix with its cofactor and applying a + or - sign
* according (-1)**(i+j), and then finding the transpose of the resulting
* matrix.
*
* @return the adjoint of this matrix.
* @throws DimensionException if this matrix is not square or if
* its dimension is less than 2.
*/
public abstract Matrix adjoint();
/**
* Indicates if this matrix is square.
*
* @return getNumberOfRows() == getNumberOfColumns()
*/
public boolean isSquare() {
return getNumberOfRows() == getNumberOfColumns();
}
/**
* Solves this matrix for the specified vector (returns x
* such as this · x = y).
*
* @param y the vector for which the solution is calculated.
* @return x such as this · x = y
* @throws DimensionException if that matrix is not square or dimensions
* do not match.
*/
public Vector solve(Vector y) {
DenseMatrix M = DenseMatrix.newInstance(y.getDimension(), true);
M._rows.add(DenseVector.valueOf(y));
return solve(M).getColumn(0);
}
/**
* Solves this matrix for the specified matrix (returns x
* such as this · x = y).
*
* @param y the matrix for which the solution is calculated.
* @return x such as this · x = y
* @throws DimensionException if that matrix is not square or dimensions
* do not match.
*/
public Matrix solve(Matrix y) {
return LUDecomposition.valueOf(this).solve(y); // Default implementation.
}
/**
* Returns this matrix raised at the specified exponent.
*
* @param exp the exponent.
* @return thisexp
* @throws DimensionException if this matrix is not square.
*/
public Matrix pow(int exp) {
if (exp > 0) {
StackContext.enter();
try {
Matrix pow2 = this;
Matrix result = null;
while (exp >= 1) { // Iteration.
if ((exp & 1) == 1) {
result = (result == null) ? pow2 : result.times(pow2);
}
pow2 = pow2.times(pow2);
exp >>>= 1;
}
return StackContext.outerCopy(result);
} finally {
StackContext.exit();
}
} else if (exp == 0) {
return this.times(this.inverse()); // Identity.
} else {
return this.pow(-exp).inverse();
}
}
/**
* Returns the trace of this matrix.
*
* @return the sum of the diagonal elements.
*/
public F trace() {
F sum = this.get(0, 0);
for (int i = MathLib.min(getNumberOfColumns(), getNumberOfRows()); --i > 0;) {
sum = sum.plus(get(i, i));
}
return sum;
}
/**
* Returns the linear algebraic matrix tensor product of this matrix
* and another (Kronecker product). The default implementation returns
* a {@link DenseMatrix}.
*
* @param that the second matrix.
* @return this ⊗ that
* @see
* Wikipedia: Kronecker Product
*/
public abstract Matrix tensor(Matrix that);
/**
* Returns the vectorization of this matrix. The vectorization of
* a matrix is the column vector obtain by stacking the columns of the
* matrix on top of one another. The default implementation returns
* a {@link DenseVector}.
*
* @return the vectorization of this matrix.
* @see
* Wikipedia: Vectorization.
*/
public abstract Vector vectorization();
/**
* Returns the text representation of this matrix.
*
* @return the text representation of this matrix.
*/
public Text toText() {
final int m = this.getNumberOfRows();
final int n = this.getNumberOfColumns();
TextBuilder tmp = TextBuilder.newInstance();
tmp.append('{');
for (int i = 0; i < m; i++) {
tmp.append('{');
for (int j = 0; j < n; j++) {
tmp.append(get(i, j));
if (j != n - 1) {
tmp.append(", ");
}
}
tmp.append("}");
if (i != m - 1) {
tmp.append(",\n");
}
}
tmp.append("}");
Text txt = tmp.toText();
TextBuilder.recycle(tmp);
return txt;
}
/**
* Returns the text representation of this matrix as a
* java.lang.String.
*
* @return toText().toString()
*/
public final String toString() {
return toText().toString();
}
/**
* Indicates if this matrix can be considered equals to the one
* specified using the specified comparator when testing for
* element equality. The specified comparator may allow for some
* tolerance in the difference between the matrix elements.
*
* @param that the matrix to compare for equality.
* @param cmp the comparator to use when testing for element equality.
* @return true if this matrix and the specified matrix are
* both matrices with equal elements according to the specified
* comparator; false otherwise.
*/
public boolean equals(Matrix that, Comparator cmp) {
if (this == that)
return true;
final int m = this.getNumberOfRows();
final int n = this.getNumberOfColumns();
if ((that.getNumberOfRows() != m) || (that.getNumberOfColumns() != n))
return false;
for (int i = m; --i >= 0;) {
for (int j = n; --j >= 0;) {
if (cmp.compare(this.get(i, j), that.get(i, j)) != 0)
return false;
}
}
return true;
}
/**
* Indicates if this matrix is strictly equal to the object specified.
*
* @param that the object to compare for equality.
* @return true if this matrix and the specified object are
* both matrices with equal elements; false otherwise.
* @see #equals(Matrix, Comparator)
*/
public boolean equals(Object that) {
if (this == that)
return true;
if (!(that instanceof Matrix))
return false;
final int m = this.getNumberOfRows();
final int n = this.getNumberOfColumns();
Matrix M = (Matrix) that;
if ((M.getNumberOfRows() != m) || (M.getNumberOfColumns() != n))
return false;
for (int i = m; --i >= 0;) {
for (int j = n; --j >= 0;) {
if (!this.get(i, j).equals(M.get(i, j)))
return false;
}
}
return true;
}
/**
* Returns a hash code value for this matrix.
* Equals objects have equal hash codes.
*
* @return this matrix hash code value.
* @see #equals
*/
public int hashCode() {
final int m = this.getNumberOfRows();
final int n = this.getNumberOfColumns();
int code = 0;
for (int i = m; --i >= 0;) {
for (int j = n; --j >= 0;) {
code += get(i, j).hashCode();
}
}
return code;
}
/**
* Returns a copy of this matrix
* {@link javolution.context.AllocatorContext allocated}
* by the calling thread (possibly on the stack).
*
* @return an identical and independant copy of this matrix.
*/
public abstract Matrix copy();
}
Ads help maintain this website.