Interval LU decomposition

Main author: Damien Massé

This page relates to the LU decomposition of an interval matrix with complete pivoting, and related features.

class IntvFullPivLU

Full pivot LU decomposition for matrix of interval, based on Eigen decomposition. The decomposition is of the form M = P{-1} [L][U] Q{-1} where P and Q are permutation matrices, and [L] and [U] are lower and upper interval matrices ([L] diagonal is 1).

Public Functions

explicit IntvFullPivLU(const Matrix &M)

constructor from Matrix of double

Parameters:

M – the matrix for which the decomposition is computed

explicit IntvFullPivLU(const IntervalMatrix &M)

constructor from Matrix of intervals. Eigen decomposition is done on M.mid().

Parameters:

M – the matrix of intervals.

BoolInterval is_injective() const

check if the matrix is injective, i.e. its rank is equal to its number of rows.

Returns:

TRUE, FALSE or UNKNOWN

BoolInterval is_invertible() const

check if the initial matrix is invertible i.e. it is square and full rank

Returns:

TRUE, FALSE or UNKNOWN

BoolInterval is_surjective() const

check if the matrix is surjective i.e. its rank is equal to its number of cols.

Returns:

TRUE, FALSE or UNKNOWN

Interval determinant() const

return an interval enclosing the determinant

Pre:

the matrix is square

Returns:

the product of the diagonal elements of [U]

Interval rank() const

return a interval enclosing the rank. Quite precise for square matrix (number of diagonal elements of [U] not containing 0). Less for non-square matrices, where each row/column outside the top-left part of [U] can change the rank. However, if no diagonal element contains 0, the return is unambiguous.

Returns:

an interval enclosing the possible ranks.

Interval dimension_of_kernel() const

approximation of the size of the kernel space. based on the result of rank() (number of cols-rank()). As such, this is not the exact size of the kernel space as build by kernel()

Returns:

an interval enclosing the possible dimensions.

IntervalMatrix kernel() const

overapproximation of the kernel space as a matrix of column vectors. any vector V which is not a linear combination of the column vectors is guaranteed to be outside the kernel ( \(MV \neq 0\) )

Returns:

a matrix of column vectors, may be empty

template<typename Derived>
inline Derived image(const Eigen::MatrixBase<Derived> &M) const

`underapproximation’ of the column space of the matrix, ie return a set of independant columns of the original matrix which is possibly maximal. As for Eigen, you must provide the original matrix used for the decomposition.

Parameters:

M – the matrix used to build the decomposition.

Pre:

M is the matrix used to build the decomposition

Returns:

a matrix of columns of M, or one vector of 0 if the rank of M may be 0.

IntervalMatrix solve(const IntervalMatrix &rhs) const

equation solving M X = rhs precisely look for solutions where the only non-zero values are those on non-zero pivots if the matrix is full-rank and surjective (cols >= rows), it gives an overapproximation of the solutions (for each possible values of rhs) if the matrix is full-rank and injective (rows >= cols), it returns empty if no solution is possible, and a possible overapproximation of the solutions otherwise (but there may still be no solution) if the matrix is not full-rank, empty means that no solution is possible with the initial precondition (non-zero values for non-zero pivots) non empty presents the possible solutions found

Parameters:

rhs – right-hand side of the equation

Returns:

a potential solution of the equation M X = rhs

IntervalMatrix reconstructed_matrix() const

rebuilding of the matrix, ie compute P^{-1}[L][U]Q^{-1} can be used to evaluate the precision of the decomposition

Returns:

the reconstructed matrix

double max_pivot() const

maximum magnitude of the diagonal elements of [U]

Returns:

the maximum

inline const Eigen::FullPivLU<Matrix>::PermutationPType &permutation_P() const

the permutation P in the decomposition P{-1}LUQ{-1}

Returns:

the permutation P, as defined by Eigen

inline const Eigen::FullPivLU<Matrix>::PermutationQType &permutation_Q() const

the permutation Q in the decomposition P{-1}LUQ{-1}

Returns:

the permutation Q, as defined by Eigen

inline const Eigen::FullPivLU<Matrix> &eigen_LU() const

the Eigen decomposition of M.mid()

Returns:

the Eigen decomposition

inline const IntervalMatrix &matrix_LU() const

returns the matrix storing [L] and [U] ([L] for strictly lower part, [U] for upper part)

Returns:

the interval matrix