ru.sscc.matrix.solve
Class RealCommonSolver

java.lang.Object
  |
  +--ru.sscc.matrix.solve.RealDirectSolver
        |
        +--ru.sscc.matrix.solve.RealDenseSolver
              |
              +--ru.sscc.matrix.solve.RealCommonSolver

Direct Known Subclasses:

EliminationSolver, ReflectionSolver, RotationSolver

public abstract class RealCommonSolver

extends RealDenseSolver

Basic abstract class for direct solvers of SLAE with a real rectangular dense matrix. Usually, the QU decomposition of the matrix is used where Q is an orthogonal matrix and U is an upper triangular matrix. If the matrix rows number is greater than the columns number, all superfluous rows will be ignored after their annulment in factorization. This case corresponds to the solving of the system by the Least Square Method, and its solution is called the pseudosolution. The factorization never fails. So, a solution or pseudosolution may be found for any SLAE. If the matrix has nontrivial null space (e.g. some matrix columns depend on other columns), the solution is not unique, but there exists the unique normal solution having the minimum Euqlidian norm. The null space orthonormal base it calculated in this class on the factorization step, and the normal pseudosolution of the SLAE is constructed by the solve method.

When the matrix is factorized by factors, the matrix range is calculated. Then it is compared with the possible maximal range (the minimum of row and column numbers) and if the factorized matrix has non-maximal range, the CalculatingException will be thrown at the end of factorization. You can ignore the exception and solve the system in this case also. The solving of transposed SLAE is also possible.

The additional solveT() method allows to solve systems with the transposed matrix basing on the factorization of the original matrix. To minimaze memory use, we recommend to factorize the matrix having more rows than columns and then use solve() or solveT() method for the solving.

The balancing of the matrix before the factorization may improve the accuracy of the result. We use a special row balancing algorithm for this purpose. Try to set the balance tag before the factorization if you don't like the solution.

Special abstract methods are added to the solver because they are useful in the GreenSolver and may also have the self-dependent interest.

Note: nonorthogonal decomposition is also useful, but in this case the solution of the system having more rows than columns will be non-pseudosolution.

See Also:

Serialized Form

Field Summary

protected double[]	balanceVector The balance vector.
protected int	range The calculated matrix range.

Fields inherited from class ru.sscc.matrix.solve.RealDenseSolver

matrix

Constructor Summary

RealCommonSolver()

Method Summary

void	attach(DenseMatrix matrix) Attaches a matrix to the solver and sets the initial state for the solver and matrix.
void	backSubstitution(RealVector source, RealVector target) Applies the back substitution to the vector (the last step of solving SLAE with already factorized matrix) and constructs the normal solution if the null space is nontrivial.
void	backSubstitutionT(RealVector source, RealVector target) Applies the transposed back substituon to the vector with the upper triangular matrix from the last step of solving SLAE (this is the first step of solving SLAE with the transposed matrix).
protected void	balance() The matrix balancing algorithm.
double[]	balanceVector() Returns the balance vector calculated on the factorization or null if the factorization was proceeded without balancing.
protected void	columnFactorized(int i) This method must be called at the end of i-th column factorization.
protected void	doBackSubstitution(RealVector source, RealVector target) The kernal method for the back substitution.
protected void	doBackSubstitutionT(RealVector source, RealVector target) The kernal method for the transposed back substitution.
protected abstract void	doFactorize() The kernal method for the factorization.
protected void	ensureTransformable(DenseMatrix matrix) Tests the dense matrix to be transformable by the orthogonal transformation.
RealDirectSolver	factorize() Factorizes the dense rectangular matrix.
double	getReductionAccuracy() Returns the reduction accuracy level.
boolean	hasBalanceTag() Returns true if the balance tag is turned on.
int	matrixRange() Returns the calculated matrix range.
DenseMatrix	nullSpace() Returns the matrix of null space base or null if the factorized matrix has the trivial null space.
int	nullSpaceRange() Returns the calculated null space range.
protected void	prepareNullVector(int i) Prepares a new basic vector of the matrix null space by i-th matrix column.
void	reuse() Clears the factorization tag to reuse the attached matrix once more and frees additional memory occupied from the previous use.
void	setBalanceTag(boolean balanceTag) Sets the balance tag.
void	setReductionAccuracy(double accuracy) Sets the reduction accuracy level affecting on making the decision ether a matrix column depends on previous columns or not.
void	solve(RealVector source, RealVector target) Solves SLAE with already factorized matrix.
void	solveT(RealVector source, RealVector target) Solves transposed SLAE with already factorized original matrix.
abstract void	transform(DenseMatrix matrix) Applies the orthogonal transformation to the dense matrix in the same order as it was done at the factorization of the attached matrix.
abstract void	transform(RealVector vector) Applies the orthogonal transformation to the vector in the same order as it was done at the factorization of the attached matrix (the first step of solving SLAE with already factorized matrix).
abstract void	transformT(RealVector vector) Applies the transpose orthogonal transformation to the vector.

Methods inherited from class ru.sscc.matrix.solve.RealDenseSolver

clone, forwardSubstitution, getMatrix, solveLowerTriangular, solveUpperTriangular, sourceSize, targetSize

Methods inherited from class ru.sscc.matrix.solve.RealDirectSolver

constructInverse, constructRefinedInverse, ensureFactorized, isFactorized, setFactorized, solveAndRefine

Methods inherited from class java.lang.Object

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

Field Detail

range

protected int range

The calculated matrix range.

balanceVector

protected double[] balanceVector

The balance vector.

Constructor Detail

RealCommonSolver

public RealCommonSolver()

Method Detail

attach

public void attach(DenseMatrix matrix)

Attaches a matrix to the solver and sets the initial state for the solver and matrix. The matrix is set to be algebraic and the solver factorize tag is turned off. To clean the solver, use attach(null).

Overrides:

attach in class RealDenseSolver

reuse

public void reuse()

Clears the factorization tag to reuse the attached matrix once more and frees additional memory occupied from the previous use.

Overrides:

reuse in class RealDenseSolver

setReductionAccuracy

public final void setReductionAccuracy(double accuracy)

Sets the reduction accuracy level affecting on making the decision ether a matrix column depends on previous columns or not. The relative accuracy bound used in the matrix factorization is calculated as the maximum of user's reduction accuracy and the theoretical estimate. So, the negative or too small user's accuracy level has no effect on making the decision on columns dependency.

getReductionAccuracy

public final double getReductionAccuracy()

Returns the reduction accuracy level.

setBalanceTag

public final void setBalanceTag(boolean balanceTag)

Sets the balance tag. If the matrix is already factorized, the operation is ignored.

hasBalanceTag

public final boolean hasBalanceTag()

Returns true if the balance tag is turned on.

balanceVector

public final double[] balanceVector()

Returns the balance vector calculated on the factorization or null if the factorization was proceeded without balancing. This method must be called after the factorization. Otherwise, the IllegalStateException will be thrown.

matrixRange

public final int matrixRange()

Returns the calculated matrix range. In attempt to call this method for non-factorized matrix the IllegalStateException will be thrown.

nullSpaceRange

public final int nullSpaceRange()

Returns the calculated null space range. In attempt to call this method for non-factorized matrix the IllegalStateException will be thrown.

nullSpace

public final DenseMatrix nullSpace()

Returns the matrix of null space base or null if the factorized matrix has the trivial null space. The basic null space vectors are stored in the matrix columns. The matrix entries are ordered by columns. The basis is the orthonormal. This method must be called after the factorization. Otherwise, the IllegalStateException will be thrown.

balance

protected void balance()

The matrix balancing algorithm.

factorize

public RealDirectSolver factorize()
                           throws CalculatingException

Factorizes the dense rectangular matrix. Does nothing if the matrix is already factorized. If the matrix is nonalgebraic, throws the IllegalStateException. If the calculated matrix range will be less than the maximum possible range, throws the CalculatingException. Any case the method sets the factorization tag to true.

Overrides:

factorize in class RealDirectSolver

Returns:

itself

Throws:

CalculatingException - is thrown when the matrix has not full range

doFactorize

protected abstract void doFactorize()

The kernal method for the factorization. It is called in the factorize() method when all preliminary actions for the factorization are already made: the balancing of the matrix is done if necessary and the initial matrix and null space ranges are set to zero. The method should do the factorization in column-per-column order. It must start the factorization of i-th column from the testing its linear dependency. To do this, the norm of the first range column entries (norm1) is compared with the norm of the rest of column (norm2). If norm2<=eps*norm1 for the sufficiently small eps, the column is considered to be depending on previous columns. In this case, the prepareNullVector(i) method must be called and the processing of the current column is finished. Otherwise, the method must factorize the column, increase the range, and call the columnFactorized(i) method. The result of the factorization must be stored in the first range columns of the matrix. If some column was not factorized in the main cycle, the columns following after it must be moved to the left to remove empty column. The movement of any column should be done when it is factorized. So, a column may change the position in the matrix only while its factorization is proceeded.

columnFactorized

protected final void columnFactorized(int i)

This method must be called at the end of i-th column factorization.

prepareNullVector

protected void prepareNullVector(int i)

Prepares a new basic vector of the matrix null space by i-th matrix column. The basic vector is produced by applying the back substitution to the i-th matrix column and assigning (-1) to the i-th entry of the result. Then the null vector is added to the null space base and normalized.

solve

public void solve(RealVector source,
                  RealVector target)

Solves SLAE with already factorized matrix. The source and target vectors may coinside if they contain enough space, e.g. the length of the vector is greater than max(sourceSize(),targetSize()).

Overrides:

solve in class RealDirectSolver

Parameters:

source - a source vector (the right hand side of SLAE)

target - a target vector to write the solution

solveT

public void solveT(RealVector source,
                   RealVector target)

Solves transposed SLAE with already factorized original matrix. The source and target vectors may coinside if they contain enough space, e.g. the length of the vector is greater than max(sourceSize(),targetSize()).

Parameters:

source - a source vector (the right hand side of transposed SLAE)

target - a target vector to write the solution

backSubstitution

public void backSubstitution(RealVector source,
                             RealVector target)

Applies the back substitution to the vector (the last step of solving SLAE with already factorized matrix) and constructs the normal solution if the null space is nontrivial. The source and target vectors may coinside.

Parameters:

source - the source vector (only the first range its entries are used)

target - the vector to store the result (must have at least nColumns entries)

doBackSubstitution

protected void doBackSubstitution(RealVector source,
                                  RealVector target)

The kernal method for the back substitution. It is called in the backSubstitution method right after the testing of vector lengthes. It must solve SLAE with the U matrix stored in the first range columns of the matrix and store the result in the first range entries of the target vector. The range is always positive here. The current implementation is done in assumption that all U matrix entries are stored on their normal positions.

Parameters:

source - the source vector (the range entries are used)

target - the target vector (the range entries are filled in)

backSubstitutionT

public void backSubstitutionT(RealVector source,
                              RealVector target)

Applies the transposed back substituon to the vector with the upper triangular matrix from the last step of solving SLAE (this is the first step of solving SLAE with the transposed matrix). The source and target vectors may coinside. The source vector may be changed if the matrix has non-trivial null space.

Parameters:

source - the source vector (must have at least nColumns entries).

target - the vector to store the result (only the first range its entries are used)

doBackSubstitutionT

protected void doBackSubstitutionT(RealVector source,
                                   RealVector target)

The kernal method for the transposed back substitution. It is called at the end of backSubstitutionT method. It must solve SLAE with the U^T matrix stored in the first range columns of the matrix and store the result in the first range entries of the target vector. The range is always positive here. The current implementation is done in assumption that all U matrix entries are stored on their normal positions.

Parameters:

source - the source vector (the range entries are used) $param target the target vector (the range entries are filled in)

transform

public abstract void transform(DenseMatrix matrix)

Applies the orthogonal transformation to the dense matrix in the same order as it was done at the factorization of the attached matrix.

transform

public abstract void transform(RealVector vector)

Applies the orthogonal transformation to the vector in the same order as it was done at the factorization of the attached matrix (the first step of solving SLAE with already factorized matrix).

transformT

public abstract void transformT(RealVector vector)

Applies the transpose orthogonal transformation to the vector.

ensureTransformable

protected final void ensureTransformable(DenseMatrix matrix)

Tests the dense matrix to be transformable by the orthogonal transformation. The parameter matrix and solver's matrix must have identical number of rows. If this test fails, throws the IllegalArgumentException.