cern.colt.matrix.linalg

## Class Algebra

- java.lang.Object
- - cern.colt.PersistentObject
  - - cern.colt.matrix.linalg.Algebra

- All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable

      public class Algebra
      extends PersistentObject

  Linear algebraic matrix operations operating on `DoubleMatrix2D`; concentrates most functionality of this package.
  Version:
    1.0, 09/24/99
  See Also:
    Serialized Form

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `static Algebra` | `DEFAULT` A default Algebra object; has `Property.DEFAULT` attached for tolerance.
    `static Algebra` | `ZERO` A default Algebra object; has `Property.ZERO` attached for tolerance.

    - ### Fields inherited from class cern.colt.PersistentObject

      `serialVersionUID`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Algebra()` Constructs a new instance with an equality tolerance given by `Property.DEFAULT.tolerance()`.
    `Algebra(double tolerance)` Constructs a new instance with the given equality tolerance.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `java.lang.Object` | `clone()` Returns a copy of the receiver.
    `double` | `cond(DoubleMatrix2D A)` Returns the condition of matrix `A`, which is the ratio of largest to smallest singular value.
    `double` | `det(DoubleMatrix2D A)` Returns the determinant of matrix `A`.
    `DoubleMatrix2D` | `inverse(DoubleMatrix2D A)` Returns the inverse or pseudo-inverse of matrix `A`.
    `double` | `mult(DoubleMatrix1D x, DoubleMatrix1D y)` Inner product of two vectors; `Sum(x[i] * y[i])`.
    `DoubleMatrix1D` | `mult(DoubleMatrix2D A, DoubleMatrix1D y)` Linear algebraic matrix-vector multiplication; `z = A * y`.
    `DoubleMatrix2D` | `mult(DoubleMatrix2D A, DoubleMatrix2D B)` Linear algebraic matrix-matrix multiplication; `C = A x B`.
    `DoubleMatrix2D` | `multOuter(DoubleMatrix1D x, DoubleMatrix1D y, DoubleMatrix2D A)` Outer product of two vectors; Sets `A[i,j] = x[i] * y[j]`.
    `double` | `norm1(DoubleMatrix1D x)` Returns the one-norm of vector `x`, which is `Sum(abs(x[i]))`.
    `double` | `norm1(DoubleMatrix2D A)` Returns the one-norm of matrix `A`, which is the maximum absolute column sum.
    `double` | `norm2(DoubleMatrix1D x)` Returns the two-norm (aka euclidean norm) of vector `x`; equivalent to `mult(x,x)`.
    `double` | `norm2(DoubleMatrix2D A)` Returns the two-norm of matrix `A`, which is the maximum singular value; obtained from SVD.
    `double` | `normF(DoubleMatrix2D A)` Returns the Frobenius norm of matrix `A`, which is `Sqrt(Sum(A[i,j]2))`.
    `double` | `normInfinity(DoubleMatrix1D x)` Returns the infinity norm of vector `x`, which is `Max(abs(x[i]))`.
    `double` | `normInfinity(DoubleMatrix2D A)` Returns the infinity norm of matrix `A`, which is the maximum absolute row sum.
    `DoubleMatrix1D` | `permute(DoubleMatrix1D A, int[] indexes, double[] work)` Modifies the given vector `A` such that it is permuted as specified; Useful for pivoting.
    `DoubleMatrix2D` | `permute(DoubleMatrix2D A, int[] rowIndexes, int[] columnIndexes)` Constructs and returns a new row and column permuted selection view of matrix `A`; equivalent to `DoubleMatrix2D.viewSelection(int[],int[])`.
    `DoubleMatrix2D` | `permuteColumns(DoubleMatrix2D A, int[] indexes, int[] work)` Modifies the given matrix `A` such that it's columns are permuted as specified; Useful for pivoting.
    `DoubleMatrix2D` | `permuteRows(DoubleMatrix2D A, int[] indexes, int[] work)` Modifies the given matrix `A` such that it's rows are permuted as specified; Useful for pivoting.
    `DoubleMatrix2D` | `pow(DoubleMatrix2D A, int p)` Linear algebraic matrix power; `B = Ak <==> B = A*A*...*A`.
    `Property` | `property()` Returns the property object attached to this Algebra, defining tolerance.
    `int` | `rank(DoubleMatrix2D A)` Returns the effective numerical rank of matrix `A`, obtained from Singular Value Decomposition.
    `void` | `setProperty(Property property)` Attaches the given property object to this Algebra, defining tolerance.
    `DoubleMatrix2D` | `solve(DoubleMatrix2D A, DoubleMatrix2D B)` Solves A*X = B.
    `DoubleMatrix2D` | `solveTranspose(DoubleMatrix2D A, DoubleMatrix2D B)` Solves X*A = B, which is also A'*X' = B'.
    `DoubleMatrix2D` | `subMatrix(DoubleMatrix2D A, int fromRow, int toRow, int fromColumn, int toColumn)` Constructs and returns a new sub-range view which is the sub matrix `A[fromRow..toRow,fromColumn..toColumn]`.
    `java.lang.String` | `toString(DoubleMatrix2D matrix)` Returns a String with (propertyName, propertyValue) pairs.
    `java.lang.String` | `toVerboseString(DoubleMatrix2D matrix)` Returns the results of `toString(A)` and additionally the results of all sorts of decompositions applied to the given matrix.
    `double` | `trace(DoubleMatrix2D A)` Returns the sum of the diagonal elements of matrix `A`; `Sum(A[i,i])`.
    `DoubleMatrix2D` | `transpose(DoubleMatrix2D A)` Constructs and returns a new view which is the transposition of the given matrix `A`.

    - ### Methods inherited from class java.lang.Object

      `equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### DEFAULT

          public static final Algebra DEFAULT

      A default Algebra object; has `Property.DEFAULT` attached for tolerance. Allows ommiting to construct an Algebra object time and again. Note that this Algebra object is immutable. Any attempt to assign a new Property object to it (via method `setProperty`), or to alter the tolerance of its property object (via `property().setTolerance(...)`) will throw an exception.

    - #### ZERO

          public static final Algebra ZERO

      A default Algebra object; has `Property.ZERO` attached for tolerance. Allows ommiting to construct an Algebra object time and again. Note that this Algebra object is immutable. Any attempt to assign a new Property object to it (via method `setProperty`), or to alter the tolerance of its property object (via `property().setTolerance(...)`) will throw an exception.

  - ### Constructor Detail

    - #### Algebra

          public Algebra()

      Constructs a new instance with an equality tolerance given by `Property.DEFAULT.tolerance()`.

    - #### Algebra

          public Algebra(double tolerance)

      Constructs a new instance with the given equality tolerance.
      Parameters:
        `tolerance` - the tolerance to be used for equality operations.

  - ### Method Detail

    - #### clone

          public java.lang.Object clone()

      Returns a copy of the receiver. The attached property object is also copied. Hence, the property object of the copy is mutable.
      Overrides:
        `clone` in class `PersistentObject`
      Returns:
        a copy of the receiver.

    - #### cond

          public double cond(DoubleMatrix2D A)

      Returns the condition of matrix `A`, which is the ratio of largest to smallest singular value.

    - #### det

          public double det(DoubleMatrix2D A)

      Returns the determinant of matrix `A`.
      Returns:
        the determinant.

    - #### inverse

          public DoubleMatrix2D inverse(DoubleMatrix2D A)

      Returns the inverse or pseudo-inverse of matrix `A`.
      Returns:
        a new independent matrix; inverse(matrix) if the matrix is square, pseudoinverse otherwise.

    - #### mult

          public double mult(DoubleMatrix1D x,
                    DoubleMatrix1D y)

      Inner product of two vectors; `Sum(x[i] * y[i])`. Also known as dot product.
      Equivalent to `x.zDotProduct(y)`.
      Parameters:
        `x` - the first source vector.
        `y` - the second source matrix.
      Returns:
        the inner product.
      Throws:
        `java.lang.IllegalArgumentException` - if `x.size() != y.size()`.

    - #### mult

          public DoubleMatrix1D mult(DoubleMatrix2D A,
                            DoubleMatrix1D y)

      Linear algebraic matrix-vector multiplication; `z = A * y`. `z[i] = Sum(A[i,j] * y[j]), i=0..A.rows()-1, j=0..y.size()-1`.
      Parameters:
        `A` - the source matrix.
        `y` - the source vector.
      Returns:
        `z`; a new vector with `z.size()==A.rows()`.
      Throws:
        `java.lang.IllegalArgumentException` - if `A.columns() != y.size()`.

    - #### mult

          public DoubleMatrix2D mult(DoubleMatrix2D A,
                            DoubleMatrix2D B)

      Linear algebraic matrix-matrix multiplication; `C = A x B`. `C[i,j] = Sum(A[i,k] * B[k,j]), k=0..n-1`.
      Matrix shapes: `A(m x n), B(n x p), C(m x p)`.
      Parameters:
        `A` - the first source matrix.
        `B` - the second source matrix.
      Returns:
        `C`; a new matrix holding the results, with `C.rows()=A.rows(), C.columns()==B.columns()`.
      Throws:
        `java.lang.IllegalArgumentException` - if `B.rows() != A.columns()`.

    - #### multOuter

          public DoubleMatrix2D multOuter(DoubleMatrix1D x,
                                 DoubleMatrix1D y,
                                 DoubleMatrix2D A)

      Outer product of two vectors; Sets `A[i,j] = x[i] * y[j]`.
      Parameters:
        `x` - the first source vector.
        `y` - the second source vector.
        `A` - the matrix to hold the results. Set this parameter to `null` to indicate that a new result matrix shall be constructed.
      Returns:
        A (for convenience only).
      Throws:
        `java.lang.IllegalArgumentException` - if `A.rows() != x.size() || A.columns() != y.size()`.

    - #### norm1

          public double norm1(DoubleMatrix1D x)

      Returns the one-norm of vector `x`, which is `Sum(abs(x[i]))`.

    - #### norm1

          public double norm1(DoubleMatrix2D A)

      Returns the one-norm of matrix `A`, which is the maximum absolute column sum.

    - #### norm2

          public double norm2(DoubleMatrix1D x)

      Returns the two-norm (aka euclidean norm) of vector `x`; equivalent to `mult(x,x)`.

    - #### norm2

          public double norm2(DoubleMatrix2D A)

      Returns the two-norm of matrix `A`, which is the maximum singular value; obtained from SVD.

    - #### normF

          public double normF(DoubleMatrix2D A)

      Returns the Frobenius norm of matrix `A`, which is `Sqrt(Sum(A[i,j]2))`.

    - #### normInfinity

          public double normInfinity(DoubleMatrix1D x)

      Returns the infinity norm of vector `x`, which is `Max(abs(x[i]))`.

    - #### normInfinity

          public double normInfinity(DoubleMatrix2D A)

      Returns the infinity norm of matrix `A`, which is the maximum absolute row sum.

    - #### permute

          public DoubleMatrix1D permute(DoubleMatrix1D A,
                               int[] indexes,
                               double[] work)

      Modifies the given vector `A` such that it is permuted as specified; Useful for pivoting. Cell `A[i]` will go into cell `A[indexes[i]]`.

      Example:

          Reordering
          [A,B,C,D,E] with indexes [0,4,2,3,1] yields
          [A,E,C,D,B]
          In other words A[0]<--A[0], A[1]<--A[4], A[2]<--A[2], A[3]<--A[3], A[4]<--A[1].

          Reordering
          [A,B,C,D,E] with indexes [0,4,1,2,3] yields
          [A,E,B,C,D]
          In other words A[0]<--A[0], A[1]<--A[4], A[2]<--A[1], A[3]<--A[2], A[4]<--A[3].

      Parameters:
        `A` - the vector to permute.
        `indexes` - the permutation indexes, must satisfy `indexes.length==A.size() && indexes[i] >= 0 && indexes[i] < A.size()`;
        `work` - the working storage, must satisfy `work.length >= A.size()`; set `work==null` if you don't care about performance.
      Returns:
        the modified `A` (for convenience only).
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `indexes.length != A.size()`.

    - #### permute

          public DoubleMatrix2D permute(DoubleMatrix2D A,
                               int[] rowIndexes,
                               int[] columnIndexes)

      Constructs and returns a new row and column permuted selection view of matrix `A`; equivalent to `DoubleMatrix2D.viewSelection(int[],int[])`. The returned matrix is backed by this matrix, so changes in the returned matrix are reflected in this matrix, and vice-versa. Use idioms like `result = permute(...).copy()` to generate an independent sub matrix.
      Returns:
        the new permuted selection view.

    - #### permuteColumns

          public DoubleMatrix2D permuteColumns(DoubleMatrix2D A,
                                      int[] indexes,
                                      int[] work)

      Modifies the given matrix `A` such that it's columns are permuted as specified; Useful for pivoting. Column `A[i]` will go into column `A[indexes[i]]`. Equivalent to `permuteRows(transpose(A), indexes, work)`.
      Parameters:
        `A` - the matrix to permute.
        `indexes` - the permutation indexes, must satisfy `indexes.length==A.columns() && indexes[i] >= 0 && indexes[i] < A.columns()`;
        `work` - the working storage, must satisfy `work.length >= A.columns()`; set `work==null` if you don't care about performance.
      Returns:
        the modified `A` (for convenience only).
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `indexes.length != A.columns()`.

    - #### permuteRows

          public DoubleMatrix2D permuteRows(DoubleMatrix2D A,
                                   int[] indexes,
                                   int[] work)

      Modifies the given matrix `A` such that it's rows are permuted as specified; Useful for pivoting. Row `A[i]` will go into row `A[indexes[i]]`.

      Example:

          Reordering
          [A,B,C,D,E] with indexes [0,4,2,3,1] yields
          [A,E,C,D,B]
          In other words A[0]<--A[0], A[1]<--A[4], A[2]<--A[2], A[3]<--A[3], A[4]<--A[1].

          Reordering
          [A,B,C,D,E] with indexes [0,4,1,2,3] yields
          [A,E,B,C,D]
          In other words A[0]<--A[0], A[1]<--A[4], A[2]<--A[1], A[3]<--A[2], A[4]<--A[3].

      Parameters:
        `A` - the matrix to permute.
        `indexes` - the permutation indexes, must satisfy `indexes.length==A.rows() && indexes[i] >= 0 && indexes[i] < A.rows()`;
        `work` - the working storage, must satisfy `work.length >= A.rows()`; set `work==null` if you don't care about performance.
      Returns:
        the modified `A` (for convenience only).
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `indexes.length != A.rows()`.

    - #### pow

          public DoubleMatrix2D pow(DoubleMatrix2D A,
                           int p)

      Linear algebraic matrix power; `B = Ak <==> B = A*A*...*A`.
      - `p >= 1: B = A*A*...*A`.
      - `p == 0: B = identity matrix`.
      - `p < 0: B = pow(inverse(A),-p)`.
      Implementation: Based on logarithms of 2, memory usage minimized.
      Parameters:
        `A` - the source matrix; must be square; stays unaffected by this operation.
        `p` - the exponent, can be any number.
      Returns:
        `B`, a newly constructed result matrix; storage-independent of `A`.
      Throws:
        `java.lang.IllegalArgumentException` - if `!property().isSquare(A)`.

    - #### property

          public Property property()

      Returns the property object attached to this Algebra, defining tolerance.
      Returns:
        the Property object.
      See Also:
        `setProperty(Property)`

    - #### rank

          public int rank(DoubleMatrix2D A)

      Returns the effective numerical rank of matrix `A`, obtained from Singular Value Decomposition.

    - #### setProperty

          public void setProperty(Property property)

      Attaches the given property object to this Algebra, defining tolerance.
      Parameters:
        `the` - Property object to be attached.
      Throws:
        `java.lang.UnsupportedOperationException` - if `this==DEFAULT && property!=this.property()` - The DEFAULT Algebra object is immutable.
        `java.lang.UnsupportedOperationException` - if `this==ZERO && property!=this.property()` - The ZERO Algebra object is immutable.
      See Also:
        `property`

    - #### solve

          public DoubleMatrix2D solve(DoubleMatrix2D A,
                             DoubleMatrix2D B)

      Solves A*X = B.
      Returns:
        X; a new independent matrix; solution if A is square, least squares solution otherwise.

    - #### solveTranspose

          public DoubleMatrix2D solveTranspose(DoubleMatrix2D A,
                                      DoubleMatrix2D B)

      Solves X*A = B, which is also A'*X' = B'.
      Returns:
        X; a new independent matrix; solution if A is square, least squares solution otherwise.

    - #### subMatrix

          public DoubleMatrix2D subMatrix(DoubleMatrix2D A,
                                 int fromRow,
                                 int toRow,
                                 int fromColumn,
                                 int toColumn)

      Constructs and returns a new sub-range view which is the sub matrix `A[fromRow..toRow,fromColumn..toColumn]`. The returned matrix is backed by this matrix, so changes in the returned matrix are reflected in this matrix, and vice-versa. Use idioms like `result = subMatrix(...).copy()` to generate an independent sub matrix.
      Parameters:
        `A` - the source matrix.
        `fromRow` - The index of the first row (inclusive).
        `toRow` - The index of the last row (inclusive).
        `fromColumn` - The index of the first column (inclusive).
        `toColumn` - The index of the last column (inclusive).
      Returns:
        a new sub-range view.
      Throws:
        `java.lang.IndexOutOfBoundsException` - if `fromColumn<0 || toColumn-fromColumn+1<0 || toColumn>=A.columns() || fromRow<0 || toRow-fromRow+1<0 || toRow>=A.rows()`

    - #### toString

          public java.lang.String toString(DoubleMatrix2D matrix)

      Returns a String with (propertyName, propertyValue) pairs. Useful for debugging or to quickly get the rough picture. For example,

          cond          : 14.073264490042144
          det           : Illegal operation or error: Matrix must be square.
          norm1         : 0.9620244354009628
          norm2         : 3.0
          normF         : 1.304841791648992
          normInfinity  : 1.5406551198102534
          rank          : 3
          trace         : 0

    - #### toVerboseString

          public java.lang.String toVerboseString(DoubleMatrix2D matrix)

      Returns the results of `toString(A)` and additionally the results of all sorts of decompositions applied to the given matrix. Useful for debugging or to quickly get the rough picture. For example,

          A = 3 x 3 matrix
          249  66  68
          104 214 108
          144 146 293

          cond         : 3.931600417472078
          det          : 9638870.0
          norm1        : 497.0
          norm2        : 473.34508217011404
          normF        : 516.873292016525
          normInfinity : 583.0
          rank         : 3
          trace        : 756.0

          density                      : 1.0
          isDiagonal                   : false
          isDiagonallyDominantByColumn : true
          isDiagonallyDominantByRow    : true
          isIdentity                   : false
          isLowerBidiagonal            : false
          isLowerTriangular            : false
          isNonNegative                : true
          isOrthogonal                 : false
          isPositive                   : true
          isSingular                   : false
          isSkewSymmetric              : false
          isSquare                     : true
          isStrictlyLowerTriangular    : false
          isStrictlyTriangular         : false
          isStrictlyUpperTriangular    : false
          isSymmetric                  : false
          isTriangular                 : false
          isTridiagonal                : false
          isUnitTriangular             : false
          isUpperBidiagonal            : false
          isUpperTriangular            : false
          isZero                       : false
          lowerBandwidth               : 2
          semiBandwidth                : 3
          upperBandwidth               : 2

          -----------------------------------------------------------------------------
          LUDecompositionQuick(A) --> isNonSingular(A), det(A), pivot, L, U, inverse(A)
          -----------------------------------------------------------------------------
          isNonSingular = true
          det = 9638870.0
          pivot = [0, 1, 2]

          L = 3 x 3 matrix
          1        0       0
          0.417671 1       0
          0.578313 0.57839 1

          U = 3 x 3 matrix
          249  66         68
            0 186.433735  79.598394
            0   0        207.635819

          inverse(A) = 3 x 3 matrix
           0.004869 -0.000976 -0.00077
          -0.001548  0.006553 -0.002056
          -0.001622 -0.002786  0.004816

          -----------------------------------------------------------------
          QRDecomposition(A) --> hasFullRank(A), H, Q, R, pseudo inverse(A)
          -----------------------------------------------------------------
          hasFullRank = true

          H = 3 x 3 matrix
          1.814086 0        0
          0.34002  1.903675 0
          0.470797 0.428218 2

          Q = 3 x 3 matrix
          -0.814086  0.508871  0.279845
          -0.34002  -0.808296  0.48067
          -0.470797 -0.296154 -0.831049

          R = 3 x 3 matrix
          -305.864349 -195.230337 -230.023539
             0        -182.628353  467.703164
             0           0        -309.13388

          pseudo inverse(A) = 3 x 3 matrix
           0.006601  0.001998 -0.005912
          -0.005105  0.000444  0.008506
          -0.000905 -0.001555  0.002688

          --------------------------------------------------------------------------
          CholeskyDecomposition(A) --> isSymmetricPositiveDefinite(A), L, inverse(A)
          --------------------------------------------------------------------------
          isSymmetricPositiveDefinite = false

          L = 3 x 3 matrix
          15.779734  0         0
           6.590732 13.059948  0
           9.125629  6.573948 12.903724

          inverse(A) = Illegal operation or error: Matrix is not symmetric positive definite.

          ---------------------------------------------------------------------
          EigenvalueDecomposition(A) --> D, V, realEigenvalues, imagEigenvalues
          ---------------------------------------------------------------------
          realEigenvalues = 1 x 3 matrix
          462.796507 172.382058 120.821435
          imagEigenvalues = 1 x 3 matrix
          0 0 0

          D = 3 x 3 matrix
          462.796507   0          0
            0        172.382058   0
            0          0        120.821435

          V = 3 x 3 matrix
          -0.398877 -0.778282  0.094294
          -0.500327  0.217793 -0.806319
          -0.768485  0.66553   0.604862

          ---------------------------------------------------------------------
          SingularValueDecomposition(A) --> cond(A), rank(A), norm2(A), U, S, V
          ---------------------------------------------------------------------
          cond = 3.931600417472078
          rank = 3
          norm2 = 473.34508217011404

          U = 3 x 3 matrix
          0.46657  -0.877519  0.110777
          0.50486   0.161382 -0.847982
          0.726243  0.45157   0.51832

          S = 3 x 3 matrix
          473.345082   0          0
            0        169.137441   0
            0          0        120.395013

          V = 3 x 3 matrix
          0.577296 -0.808174  0.116546
          0.517308  0.251562 -0.817991
          0.631761  0.532513  0.563301

    - #### trace

          public double trace(DoubleMatrix2D A)

      Returns the sum of the diagonal elements of matrix `A`; `Sum(A[i,i])`.

    - #### transpose

          public DoubleMatrix2D transpose(DoubleMatrix2D A)

      Constructs and returns a new view which is the transposition of the given matrix `A`. Equivalent to `A.viewDice()`. This is a zero-copy transposition, taking O(1), i.e. constant time. The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. Use idioms like `result = transpose(A).copy()` to generate an independent matrix.

      Example:

      2 x 3 matrix: 1, 2, 3 4, 5, 6 | transpose ==> | 3 x 2 matrix: 1, 4 2, 5 3, 6 | transpose ==> | 2 x 3 matrix: 1, 2, 3 4, 5, 6

      Returns:
        a new transposed view.

Jump to the Colt Homepage