de.lmu.ifi.dbs.elki.math.linearalgebra
Class LinearEquationSystem

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

public class LinearEquationSystem
extends Object

Class for systems of linear equations.


Field Summary
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
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
 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

Release 0.4.0 (2011-09-20_1324)