LinearEquationSystem (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

java.lang.Object
- de.lmu.ifi.dbs.elki.math.linearalgebra.LinearEquationSystem

public class LinearEquationSystem
extends Object

Class for systems of linear equations.

Field Summary

Fields
Modifier and Type	Field and Description
`private double[][]`	`coeff` The matrix of coefficients.
`private int[]`	`col` Encodes column permutations, column j is at position col[j].
`private static Logging`	`logger` Logger.
`private int`	`rank` The rank of the coefficient matrix.
`private boolean`	`reducedRowEchelonForm` Indicates if linear equation system is in reduced row echelon form.
`private double[]`	`rhs` The right hand side of the equation system.
`private int[]`	`row` Encodes row permutations, row i is at position row[i].
`private boolean`	`solvable` Indicates if linear equation system is solvable.
`private boolean`	`solved` Indicates if solvability has been checked.
`private static int`	`TOTAL_PIVOT_SEARCH` Indicates total pivot search strategy.
`private static int`	`TRIVAL_PIVOT_SEARCH` Indicates trivial pivot search strategy.
`private double[][]`	`u` Holds the space of solutions of the homogeneous linear equation system.
`private double[]`	`x_0` Holds the special solution vector.

Constructor Summary

Constructors
Constructor and Description
`LinearEquationSystem(double[][] a, double[] b)` Constructs a linear equation system with given coefficient matrix `a` and right hand side `b`.
`LinearEquationSystem(double[][] a, double[] b, int[] rowPermutations, int[] columnPermutations)` Constructs a linear equation system with given coefficient matrix `a` and right hand side `b`.

Method Summary

Methods
Modifier and Type	Method and Description
`String`	`equationsToString(int fractionDigits)` Returns a string representation of this equation system.
`String`	`equationsToString(NumberFormat nf)` Returns a string representation of this equation system.
`String`	`equationsToString(String prefix, int fractionDigits)` Returns a string representation of this equation system.
`String`	`equationsToString(String prefix, NumberFormat nf)` Returns a string representation of this equation system.
`private void`	`format(NumberFormat nf, StringBuffer buffer, double value, int maxIntegerDigits)` Helper method for output of equations and solution.
`double[][]`	`getCoefficents()` Returns a copy of the coefficient array of this linear equation system.
`int[]`	`getColumnPermutations()` Returns a copy of the column permutations, column i is at position column[i].
`double[]`	`getRHS()` Returns a copy of the right hand side of this linear equation system.
`int[]`	`getRowPermutations()` Returns a copy of the row permutations, row i is at position row[i].
`private int`	`integerDigits(double d)` Returns the integer digits of the specified double value.
`boolean`	`isSolvable()` Checks if a solved system is solvable.
`private boolean`	`isSolvable(int method)` Checks solvability of this linear equation system with the chosen method.
`boolean`	`isSolved()` Tests if system has already been tested for solvability.
`private int`	`maxIntegerDigits(double[] values)` Returns the maximum integer digits of the specified values.
`private int[]`	`maxIntegerDigits(double[][] values)` Returns the maximum integer digits in each column of the specified values.
`private IntIntPair`	`nonZeroPivotSearch(int k)` Method for trivial pivot search, searches for non-zero entry.
`private void`	`permutePivot(IntIntPair pos1, IntIntPair pos2)` permutes two matrix rows and two matrix columns
`private void`	`pivotOperation(int k)` performs a pivot operation
`private void`	`reducedRowEchelonForm(int method)` Brings this linear equation system into reduced row echelon form with choice of pivot method.
`String`	`solutionToString(int fractionDigits)` Returns a string representation of the solution of this equation system.
`private void`	`solve(int method)` solves linear system with the chosen method
`void`	`solveByTotalPivotSearch()` Solves this linear equation system by total pivot search.
`void`	`solveByTrivialPivotSearch()` Solves this linear equation system by trivial pivot search.
`int`	`subspacedim()` Return dimensionality of spanned subspace.
`private IntIntPair`	`totalPivotSearch(int k)` Method for total pivot search, searches for x,y in {k,...n}, so that \|a_xy\| > \|a_ij\|

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - logger
```
private static final Logging logger
```
    Logger.
  - TRIVAL_PIVOT_SEARCH
```
private static final int TRIVAL_PIVOT_SEARCH
```
    Indicates trivial pivot search strategy.
    
    See Also:
    Constant Field Values
  - TOTAL_PIVOT_SEARCH
```
private static final int TOTAL_PIVOT_SEARCH
```
    Indicates total pivot search strategy.
    
    See Also:
    Constant Field Values
  - solvable
```
private boolean solvable
```
    Indicates if linear equation system is solvable.
  - solved
```
private boolean solved
```
    Indicates if solvability has been checked.
  - rank
```
private int rank
```
    The rank of the coefficient matrix.
  - coeff
```
private double[][] coeff
```
    The matrix of coefficients.
  - rhs
```
private double[] rhs
```
    The right hand side of the equation system.
  - row
```
private int[] row
```
    Encodes row permutations, row i is at position row[i].
  - col
```
private int[] col
```
    Encodes column permutations, column j is at position col[j].
  - x_0
```
private double[] x_0
```
    Holds the special solution vector.
  - u
```
private double[][] u
```
    Holds the space of solutions of the homogeneous linear equation system.
  - reducedRowEchelonForm
```
private boolean reducedRowEchelonForm
```
    Indicates if linear equation system is in reduced row echelon form.
- Constructor Detail
  - LinearEquationSystem
```
public LinearEquationSystem(double[][] a,
                    double[] b)
```
    Constructs a linear equation system with given coefficient matrix a and right hand side b.
    
    Parameters:
    a - the matrix of the coefficients of the linear equation system
    b - the right hand side of the linear equation system
  - LinearEquationSystem
```
public LinearEquationSystem(double[][] a,
                    double[] b,
                    int[] rowPermutations,
                    int[] columnPermutations)
```
    Constructs a linear equation system with given coefficient matrix a and right hand side b.
    
    Parameters:
    a - the matrix of the coefficients of the linear equation system
    b - the right hand side of the linear equation system
    rowPermutations - the row permutations, row i is at position row[i]
    columnPermutations - the column permutations, column i is at position column[i]
- Method Detail
  - getCoefficents
```
public double[][] getCoefficents()
```
    Returns a copy of the coefficient array of this linear equation system.
    
    Returns:
    a copy of the coefficient array of this linear equation system
  - getRHS
```
public double[] getRHS()
```
    Returns a copy of the right hand side of this linear equation system.
    
    Returns:
    a copy of the right hand side of this linear equation system
  - getRowPermutations
```
public int[] getRowPermutations()
```
    Returns a copy of the row permutations, row i is at position row[i].
    
    Returns:
    a copy of the row permutations
  - getColumnPermutations
```
public int[] getColumnPermutations()
```
    Returns a copy of the column permutations, column i is at position column[i].
    
    Returns:
    a copy of the column permutations
  - isSolved
```
public boolean isSolved()
```
    Tests if system has already been tested for solvability.
    
    Returns:
    true if a solution has already been computed, false otherwise.
  - solveByTotalPivotSearch
```
public void solveByTotalPivotSearch()
```
    Solves this linear equation system by total pivot search. "Total pivot search" takes as pivot element the element in the current column having the biggest value. If we have:
    ( a_11 ... a_1n ) ( 0 ... a_2n ) ( 0 ... a_ii ... a_in ) ( 0 ... a_(i+1)i ... a_(i+1)n ) ( 0 ... a_ni ... a_nn ) Then we search for x,y in {i,...n}, so that |a_xy| > |a_ij|
  - solveByTrivialPivotSearch
```
public void solveByTrivialPivotSearch()
```
    Solves this linear equation system by trivial pivot search. "Trivial pivot search" takes as pivot element the next element in the current column beeing non zero.
  - isSolvable
```
public boolean isSolvable()
```
    Checks if a solved system is solvable.
    
    Returns:
    true if this linear equation system is solved and solvable
  - equationsToString
```
public String equationsToString(String prefix,
                       int fractionDigits)
```
    Returns a string representation of this equation system.
    
    Parameters:
    prefix - the prefix of each line
    fractionDigits - the number of fraction digits for output accuracy
    
    Returns:
    a string representation of this equation system
  - equationsToString
```
public String equationsToString(String prefix,
                       NumberFormat nf)
```
    Returns a string representation of this equation system.
    
    Parameters:
    prefix - the prefix of each line
    nf - the number format
    
    Returns:
    a string representation of this equation system
  - equationsToString
```
public String equationsToString(NumberFormat nf)
```
    Returns a string representation of this equation system.
    
    Parameters:
    nf - the number format
    
    Returns:
    a string representation of this equation system
  - equationsToString
```
public String equationsToString(int fractionDigits)
```
    Returns a string representation of this equation system.
    
    Parameters:
    fractionDigits - the number of fraction digits for output accuracy
    
    Returns:
    a string representation of this equation system
  - solutionToString
```
public String solutionToString(int fractionDigits)
```
    Returns a string representation of the solution of this equation system.
    
    Parameters:
    fractionDigits - precision
    
    Returns:
    a string representation of the solution of this equation system
  - reducedRowEchelonForm
```
private void reducedRowEchelonForm(int method)
```
    Brings this linear equation system into reduced row echelon form with choice of pivot method.
    
    Parameters:
    method - the pivot search method to use
  - totalPivotSearch
```
private IntIntPair totalPivotSearch(int k)
```
    Method for total pivot search, searches for x,y in {k,...n}, so that |a_xy| > |a_ij|
    
    Parameters:
    k - search starts at entry (k,k)
    
    Returns:
    the position of the found pivot element
  - nonZeroPivotSearch
```
private IntIntPair nonZeroPivotSearch(int k)
```
    Method for trivial pivot search, searches for non-zero entry.
    
    Parameters:
    k - search starts at entry (k,k)
    
    Returns:
    the position of the found pivot element
  - permutePivot
```
private void permutePivot(IntIntPair pos1,
                IntIntPair pos2)
```
    permutes two matrix rows and two matrix columns
    
    Parameters:
    pos1 - the fist position for the permutation
    pos2 - the second position for the permutation
  - pivotOperation
```
private void pivotOperation(int k)
```
    performs a pivot operation
    
    Parameters:
    k - pivoting takes place below (k,k)
  - solve
```
private void solve(int method)
            throws NullPointerException
```
    solves linear system with the chosen method
    
    Parameters:
    method - the pivot search method
    
    Throws:
    
    NullPointerException
  - isSolvable
```
private boolean isSolvable(int method)
                    throws NullPointerException
```
    Checks solvability of this linear equation system with the chosen method.
    
    Parameters:
    method - the pivot search method
    
    Returns:
    true if linear system in solvable
    
    Throws:
    
    NullPointerException
  - maxIntegerDigits
```
private int[] maxIntegerDigits(double[][] values)
```
    Returns the maximum integer digits in each column of the specified values.
    
    Parameters:
    values - the values array
    
    Returns:
    the maximum integer digits in each column of the specified values
  - maxIntegerDigits
```
private int maxIntegerDigits(double[] values)
```
    Returns the maximum integer digits of the specified values.
    
    Parameters:
    values - the values array
    
    Returns:
    the maximum integer digits of the specified values
  - integerDigits
```
private int integerDigits(double d)
```
    Returns the integer digits of the specified double value.
    
    Parameters:
    d - the double value
    
    Returns:
    the integer digits of the specified double value
  - format
```
private void format(NumberFormat nf,
          StringBuffer buffer,
          double value,
          int maxIntegerDigits)
```
    Helper method for output of equations and solution. Appends the specified double value to the given string buffer according the number format and the maximum number of integer digits.
    
    Parameters:
    nf - the number format
    buffer - the string buffer to append the value to
    value - the value to append
    maxIntegerDigits - the maximum number of integer digits
  - subspacedim
```
public int subspacedim()
```
    Return dimensionality of spanned subspace.
    
    Returns:
    dim

Class LinearEquationSystem

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

logger

TRIVAL_PIVOT_SEARCH

TOTAL_PIVOT_SEARCH

solvable

solved

rank

coeff

rhs

row

col

x_0

u

reducedRowEchelonForm

Constructor Detail

LinearEquationSystem

LinearEquationSystem

Method Detail

getCoefficents

getRHS

getRowPermutations

getColumnPermutations

isSolved

solveByTotalPivotSearch

solveByTrivialPivotSearch

isSolvable

equationsToString

equationsToString

equationsToString

equationsToString

solutionToString

reducedRowEchelonForm

totalPivotSearch

nonZeroPivotSearch

permutePivot

pivotOperation

solve

isSolvable

maxIntegerDigits

maxIntegerDigits

integerDigits

format

subspacedim