Package org.flag4j.linalg.decompositions.schur

Class Schur<T extends MatrixMixin<T,?,?,?,?,?,?,?>,U>

java.lang.Object

org.flag4j.linalg.decompositions.schur.Schur<T,U>

Type Parameters:

T - The type of matrix to be decomposed.

U - The type for the internal storage datastructure of the matrix to be decomposed.

All Implemented Interfaces:

Decomposition<T>

Direct Known Subclasses:

ComplexSchur, RealSchur

public abstract class Schur<T extends MatrixMixin<T,?,?,?,?,?,?,?>,U>
extends Object
implements Decomposition<T>

The base class for Schur decompositions.

The Schur decomposition decompose a square matrix A into A=UTU<sup>H</sup> where U is a unitary matrix and T is a quasi-upper triangular matrix called the Schur form of A. T is upper triangular except for possibly 2x2 blocks along the diagonal. T is similar to A meaning they share the same eigenvalues.

Field Summary

Fields

Modifier and Type	Field	Description
protected boolean	checkFinite	Flag indicating if a check should be made during the decomposition that the working matrix contains only finite values.
protected final boolean	computeU	Flag indicating if the orthogonal matrix U in the Schur decomposition should be computed.
protected final int	DEFAULT_EXCEPTIONAL_ITERS	Default number of iterations to apply before doing an exceptional shift.
protected final int	DEFAULT_MAX_ITERS_FACTOR	Default factor for computing the maximum number of iterations to perform.
protected int	exceptionalThreshold	Number of iterations to run without deflation before an exceptional shift is done.
protected UnitaryDecomposition<T,U>	hess	Decomposer to compute the Hessenburg decomposition as a setup step for the implicit double step QR algorithm.
protected U	householderVector	Stores the vector v in the Householder reflector P = I - invalid input: '&alpha'vvT.
protected int	maxIterations	Maximum number of iterations to run QR algorithm for.
protected int	maxIterationsFactor	Factor for computing the maximum number of iterations to run the QR algorithm for.
protected int	numExceptional	The total number of exceptional shifts that have been used during the decomposition.
protected int	numRows	Stores the number of rows in the matrix being decomposed.
protected final RandomCNumber	rng	Random number generator to be used when computing a random exceptional shift.
protected U	shiftCol	Stores the non-zero entries of the first column of the shifted matrix (A-invalid input: '&rho'1I)(A-invalid input: '&rho'2I) where invalid input: '&rho'1 and invalid input: '&rho'2 are the two shifts.
protected int	sinceLastExceptional	The number of iterations run in the QR algorithm without deflating or performing an exceptional shift.
protected T	T	For storing the (possibly block) upper triangular matrix T in the Schur decomposition.
protected U	temp	Array for holding temporary values when computing the shifts.
protected T	U	For storing the unitary U matrix in the Schur decomposition.
protected U	workArray	An array for storing temporary values along the colum of a matrix when applying Householder reflectors.

Constructor Summary

Constructors

Constructor	Description
Schur(boolean computeU, RandomCNumber rng, UnitaryDecomposition<T,U> hess)	Creates a decomposer to compute the Schur decomposition for a real dense matrix.

Method Summary

Modifier and Type	Method	Description
protected abstract int	checkConvergence(int workingSize)	Checks for convergence of lower 2x2 sub-matrix within working matrix to upper triangular or block upper triangular form.
void	decomposeBase(T src)	Computes the Schur decomposition of the input matrix.
T	getT()	Gets the upper, or possibly block-upper, triangular Schur matrix T from the Schur decomposition
T	getU()	Gets the unitary matrix U from the Schur decomposition containing the Schur vectors as its columns.
protected abstract void	performDoubleShift(int workingSize)	Performs a full iteration of the Francis implicit double shifted QR algorithm (this includes the bulge chase).
protected abstract void	performExceptionalShift(int workingSize)	Performs a full iteration of the single shifted QR algorithm (this includes the bulge chase) where the shift is chosen to be a random value with the same magnitude as the lower right element of the working matrix.
Schur<T,U>	setExceptionalThreshold(int exceptionalThreshold)	Sets the number of iterations of the QR algorithm to perform without deflation before performing a random shift.
Schur<T,U>	setMaxIterationFactor(int maxIterationFactor)	Specify maximum iteration factor for computing the total number of iterations to run the QR algorithm for when computing the decomposition.
protected void	setUp(T src)	Performs basic setup and initializes data structures to be used in the decomposition.
protected abstract void	setUpArrays()	Initializes temporary work arrays to be used in the decomposition.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.flag4j.linalg.decompositions.Decomposition

decompose

Field Details

rng

protected final RandomCNumber rng

Random number generator to be used when computing a random exceptional shift.

DEFAULT_EXCEPTIONAL_ITERS

protected final int DEFAULT_EXCEPTIONAL_ITERS

Default number of iterations to apply before doing an exceptional shift.

See Also:

• Constant Field Values

DEFAULT_MAX_ITERS_FACTOR

protected final int DEFAULT_MAX_ITERS_FACTOR

Default factor for computing the maximum number of iterations to perform.

See Also:

• Constant Field Values

T

protected T extends MatrixMixin<T,?,?,?,?,?,?,?> T

For storing the (possibly block) upper triangular matrix T in the Schur decomposition.

U

protected T extends MatrixMixin<T,?,?,?,?,?,?,?> U

For storing the unitary U matrix in the Schur decomposition.

hess

protected UnitaryDecomposition<T extends MatrixMixin<T,?,?,?,?,?,?,?>,U> hess

Decomposer to compute the Hessenburg decomposition as a setup step for the implicit double step QR algorithm.

numRows

protected int numRows

Stores the number of rows in the matrix being decomposed.

householderVector

protected U householderVector

Stores the vector v in the Householder reflector P = I - invalid input: '&alpha'vv^T.

shiftCol

protected U shiftCol

Stores the non-zero entries of the first column of the shifted matrix (A-invalid input: '&rho'₁I)(A-invalid input: '&rho'₂I) where invalid input: '&rho'₁ and invalid input: '&rho'₂ are the two shifts.

workArray

protected U workArray

An array for storing temporary values along the colum of a matrix when applying Householder reflectors. This can help improve cache performance when applying the reflector.

temp

protected U temp

Array for holding temporary values when computing the shifts.

maxIterationsFactor

protected int maxIterationsFactor

Factor for computing the maximum number of iterations to run the QR algorithm for.

maxIterations

protected int maxIterations

Maximum number of iterations to run QR algorithm for.

exceptionalThreshold

protected int exceptionalThreshold

Number of iterations to run without deflation before an exceptional shift is done.

sinceLastExceptional

protected int sinceLastExceptional

The number of iterations run in the QR algorithm without deflating or performing an exceptional shift.

numExceptional

protected int numExceptional

The total number of exceptional shifts that have been used during the decomposition.

checkFinite

protected boolean checkFinite

Flag indicating if a check should be made during the decomposition that the working matrix contains only finite values. If true, an explicit check will be made and an exception will be thrown if non-finite values are found. If false, no check will be made and the floating point arithmetic will carry on with infinities, negative-infinities, and NaNs present.

computeU

protected final boolean computeU

Flag indicating if the orthogonal matrix U in the Schur decomposition should be computed. If false, U will not be computed. This may provide performance improvements for large matrices when U is not required (for instance: in eigenvalue computations where eigenvectors are not needed).

Constructor Details

Schur

public Schur(boolean computeU,
 RandomCNumber rng,
 UnitaryDecomposition<T,U> hess)

Creates a decomposer to compute the Schur decomposition for a real dense matrix.

If the U matrix is not needed, passing computeU = false may provide a performance improvement.

Parameters:

computeU - Flag indicating if the unitary U matrix should be computed for the Schur decomposition. If true, U will be computed. If false, U will not be computed.

rng - Random number generator to use when performing random exceptional shifts.

hess - Decomposer to compute the Hessenburg decomposition as a setup step for the QR algorithm.

Method Details

setExceptionalThreshold

public Schur<T,U> setExceptionalThreshold(int exceptionalThreshold)

Sets the number of iterations of the QR algorithm to perform without deflation before performing a random shift.

That is, if exceptionalThreshold = 10, then at most 10 iterations QR algorithm iterations will be performed. If, by the 10th iteration, no convergence has been detected which allows for deflation, then a QR algorithm iteration will be performed with a random (i.e. exceptional) shift.

By default, the threshold is set to DEFAULT_EXCEPTIONAL_ITERS

Parameters:

exceptionalThreshold - The new exceptional shift threshold. i.e. the number of iterations to perform without deflation before performing an iteration with random shifts.

Returns:

A reference to this decomposer.

Throws:

IllegalArgumentException - If exceptionalThreshold is not positive.

setMaxIterationFactor

public Schur<T,U> setMaxIterationFactor(int maxIterationFactor)

Specify maximum iteration factor for computing the total number of iterations to run the QR algorithm for when computing the decomposition. The maximum number of iterations is computed as

     maxIteration = maxIterationFactor * src.numRows; 

If the algorithm does not converge within this limit, an error will be thrown.

By default, this is computed as

     maxIterations = DEFAULT_MAX_ITERS_FACTOR* src.numRows;

where src is the matrix being decomposed.

Parameters:

maxIterationFactor - maximum iteration factor for use in computing the total maximum number of iterations to run the QR algorithm for.

Throws:

IllegalArgumentException - If maxIterationFactor is not positive.

getT

public T getT()

Gets the upper, or possibly block-upper, triangular Schur matrix T from the Schur decomposition

Returns:

The T matrix from the Schur decomposition A=UTU^H

getU

public T getU()

Gets the unitary matrix U from the Schur decomposition containing the Schur vectors as its columns.

Returns:

A=UTU^H

decomposeBase

public void decomposeBase(T src)

Computes the Schur decomposition of the input matrix.

Parameters:

src - The source matrix to decompose.

Throws:

LinearAlgebraException - If the decomposition does not converge within the specified number of max iterations. See invalid input: '{@link /*missing*/}'

setUp

protected void setUp(T src)

Performs basic setup and initializes data structures to be used in the decomposition.

Parameters:

src - The matrix to be decomposed.

setUpArrays

protected abstract void setUpArrays()

Initializes temporary work arrays to be used in the decomposition.

performExceptionalShift

protected abstract void performExceptionalShift(int workingSize)

Performs a full iteration of the single shifted QR algorithm (this includes the bulge chase) where the shift is chosen to be a random value with the same magnitude as the lower right element of the working matrix. This can help the QR converge for certain pathological cases where the double shift algorithm oscillates or fails to converge for repeated eigenvalues.

Parameters:

workingSize - The current working size for the decomposition. I.e. all entries below this row have converged to an upper or possible 2x2 block upper triangular form.

performDoubleShift

protected abstract void performDoubleShift(int workingSize)

Performs a full iteration of the Francis implicit double shifted QR algorithm (this includes the bulge chase).

Parameters:

workingSize - The current working size for the decomposition. I.e. all entries below this row have converged to an upper or possible 2x2 block upper triangular form.

checkConvergence

protected abstract int checkConvergence(int workingSize)

Checks for convergence of lower 2x2 sub-matrix within working matrix to upper triangular or block upper triangular form. If convergence is found, this will also zero out the values which have converged to near zero.

Parameters:

workingSize - Size of current working matrix.

Returns:

Returns the amount the working matrix size should be deflated. Will be zero if no convergence is detected, one if convergence to upper triangular form is detected and two if convergence to block upper triangular form is detected.