Package elki.math.linearalgebra
Class LinearEquationSystem
- java.lang.Object
-
- elki.math.linearalgebra.LinearEquationSystem
-
public class LinearEquationSystem extends java.lang.Object
Class for systems of linear equations.- Since:
- 0.1
- Author:
- Elke Achtert
-
-
Field Summary
Fields Modifier and Type Field Description private double[][]
coeff
The matrix of coefficients.private int[]
col
Encodes column permutations, column j is at position col[j].private static double
DELTA
A small number to handle numbers near 0 as 0.private static Logging
LOG
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 Description LinearEquationSystem(double[][] a, double[] b)
Constructs a linear equation system with given coefficient matrixa
and right hand sideb
.LinearEquationSystem(double[][] a, double[] b, int[] rowPermutations, int[] columnPermutations)
Constructs a linear equation system with given coefficient matrixa
and right hand sideb
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.lang.String
equationsToString(int fractionDigits)
Returns a string representation of this equation system.java.lang.String
equationsToString(java.lang.String prefix, int fractionDigits)
Returns a string representation of this equation system.java.lang.String
equationsToString(java.lang.String prefix, java.text.NumberFormat nf)
Returns a string representation of this equation system.java.lang.String
equationsToString(java.text.NumberFormat nf)
Returns a string representation of this equation system.private java.lang.StringBuilder
format(java.text.NumberFormat nf, java.lang.StringBuilder 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 void
nonZeroPivotSearch(int k, int[] pivotpos)
Method for trivial pivot search, searches for non-zero entry.private void
permutePivot(int r1, int c1, int r2, int c2)
permutes two matrix rows and two matrix columnsprivate void
pivotOperation(int k)
performs a pivot operationprivate void
reducedRowEchelonForm(int method)
Brings this linear equation system into reduced row echelon form with choice of pivot method.java.lang.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 methodvoid
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 void
totalPivotSearch(int k, int[] pivotpos)
Method for total pivot search, searches for x,y in {k,...n}, so that|a_xy| > |a_ij|
-
-
-
Field Detail
-
LOG
private static final Logging LOG
Logger.
-
DELTA
private static final double DELTA
A small number to handle numbers near 0 as 0.- See Also:
- Constant Field Values
-
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 matrixa
and right hand sideb
.- Parameters:
a
- the matrix of the coefficients of the linear equation systemb
- 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 matrixa
and right hand sideb
.- Parameters:
a
- the matrix of the coefficients of the linear equation systemb
- the right hand side of the linear equation systemrowPermutations
- 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 java.lang.String equationsToString(java.lang.String prefix, int fractionDigits)
Returns a string representation of this equation system.- Parameters:
prefix
- the prefix of each linefractionDigits
- the number of fraction digits for output accuracy- Returns:
- a string representation of this equation system
-
equationsToString
public java.lang.String equationsToString(java.lang.String prefix, java.text.NumberFormat nf)
Returns a string representation of this equation system.- Parameters:
prefix
- the prefix of each linenf
- the number format- Returns:
- a string representation of this equation system
-
equationsToString
public java.lang.String equationsToString(java.text.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 java.lang.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 java.lang.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 void totalPivotSearch(int k, int[] pivotpos)
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)pivotpos
- Output pivot positions
-
nonZeroPivotSearch
private void nonZeroPivotSearch(int k, int[] pivotpos)
Method for trivial pivot search, searches for non-zero entry.- Parameters:
k
- search starts at entry (k,k)pivotpos
- Output array
-
permutePivot
private void permutePivot(int r1, int c1, int r2, int c2)
permutes two matrix rows and two matrix columns- Parameters:
r1
- the first row for the permutationc1
- the first column for the permutationr2
- the second row for the permutationc2
- the second column 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 java.lang.NullPointerException
solves linear system with the chosen method- Parameters:
method
- the pivot search method- Throws:
java.lang.NullPointerException
-
isSolvable
private boolean isSolvable(int method) throws java.lang.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:
java.lang.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 java.lang.StringBuilder format(java.text.NumberFormat nf, java.lang.StringBuilder 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 formatbuffer
- the string buffer to append the value tovalue
- the value to appendmaxIntegerDigits
- the maximum number of integer digits- Returns:
- the buffer for chaining
-
subspacedim
public int subspacedim()
Return dimensionality of spanned subspace.- Returns:
- dim
-
-