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

java.lang.Object
  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