codac2::IntvFullPivLU Class Reference

Full pivot LU decomposition for a matrix of intervals, based on Eigen decomposition. The decomposition is of the form \(\mathbf{M} = \mathbf{P}^{-1} [\mathbf{L}][\mathbf{U}] \mathbf{Q}^{-1}\) where \(\mathbf{P}\) and \(\mathbf{Q}\) are permutation matrices, and \([\mathbf{L}]\) and \([\mathbf{U}]\) are lower and upper interval matrices (i.e. \([\mathbf{L}]\)'s diagonal is 1). More...

#include <codac2_IntvFullPivLU.h>

Public Member Functions
	IntvFullPivLU (const Matrix &M)
	Constructor from Matrix of double.
	IntvFullPivLU (const IntervalMatrix &M)
	Constructor from Matrix of intervals. Eigen decomposition is done on M.mid().
BoolInterval	is_injective () const
	Check if the matrix is injective, i.e. its rank is equal to its number of rows.
BoolInterval	is_invertible () const
	Check if the initial matrix is invertible i.e. it is square and full rank.
BoolInterval	is_surjective () const
	Check if the matrix is surjective i.e. its rank is equal to its number of cols.
Interval	determinant () const
	Return an interval enclosing the determinant.
Interval	rank () const
	Return an interval enclosing the rank. Quite precise for square matrix (number of diagonal elements of \([\mathbf{U}]\) not containing 0). Less precise for non-square matrices, where each row/column outside the top-left part of \([\mathbf{U}]\) can change the rank. However, if no diagonal element contains 0, the return is unambiguous.
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 built by kernel().
IntervalMatrix	kernel () const
	Overapproximation of the kernel space as a matrix of column vectors. Any vector \(\mathbf{V}\) which is not a linear combination of the column vectors is guaranteed to be outside the kernel (i.e., \(\mathbf{M}\mathbf{V} \neq 0\)).
IntervalMatrix	cokernel () const
	Overapproximation of the left-null ("cokernel") space as a matrix of row vectors. Any vector \(\mathbf{V}\) which is not a linear combination of the row vectors is guaranteed to be outside the kernel (i.e., \(\mathbf{V}\mathbf{M} \neq 0\)).
template<typename Derived>
Derived	image (const Eigen::MatrixBase< Derived > &M) const
	"Underapproximation" of the column space of the matrix, i.e. 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.
template<typename Derived>
Derived	coimage (const Eigen::MatrixBase< Derived > &M) const
	"Underapproximation" of the row space of the matrix, i.e. return a set of independant rows of the original matrix which is possibly maximal. As for Eigen, you must provide the original matrix used for the decomposition.
IntervalMatrix	solve (const IntervalMatrix &rhs) const
	Equation solving \(\mathbf{M}\mathbf{X}=\mathbf{rhs}\).
void	solve (const IntervalMatrix &rhs, IntervalMatrix &B) const
	Equation solving \(\mathbf{M}\mathbf{X}=\mathbf{rhs}\) with bounding matrix \([\mathbf{B}]\) for the solution, i.e. contraction of the matrix on the solutions on \(\mathbf{M}\mathbf{X}\).
IntervalMatrix	reconstructed_matrix () const
	Rebuilding of the matrix, i.e. compute \(\mathbf{P}^{-1}[\mathbf{L}][\mathbf{U}]\mathbf{Q}^{-1}\).
double	max_pivot () const
	Maximum magnitude of the diagonal elements of \([\mathbf{U}]\).
const Eigen::FullPivLU< Matrix >::PermutationPType &	permutation_P () const
	The permutation \(\mathbf{P}\) in the decomposition \(\mathbf{P}^{-1}\mathbf{L}\mathbf{U}\mathbf{Q}^{-1}\).
const Eigen::FullPivLU< Matrix >::PermutationQType &	permutation_Q () const
	The permutation \(\mathbf{Q}\) in the decomposition \(\mathbf{P}^{-1}\mathbf{L}\mathbf{U}\mathbf{Q}^{-1}\).
const Eigen::FullPivLU< Matrix > &	eigen_LU () const
	The Eigen decomposition of M.mid()
const Row &	transformation () const
	Return the column-wise transformation done on M.mid() before the Eigen LU decomposition, as a Row.
const IntervalMatrix &	matrix_LU () const
	Returns the matrix storing \([\mathbf{L}]\) and \([\mathbf{U}]\) (i.e. \([\mathbf{L}]\) for strictly lower part, \([\mathbf{U}]\) for upper part).

Detailed Description

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

Constructor & Destructor Documentation

IntvFullPivLU() [1/2]

codac2::IntvFullPivLU::IntvFullPivLU ( const Matrix & M )

explicit

Constructor from Matrix of double.

Parameters

M	the matrix for which the decomposition is computed

IntvFullPivLU() [2/2]

codac2::IntvFullPivLU::IntvFullPivLU ( const IntervalMatrix & M )

explicit

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

Parameters

M	the matrix of intervals.

Member Function Documentation

is_injective()

BoolInterval codac2::IntvFullPivLU::is_injective

(

)

const

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

Returns

a BoolInterval

is_invertible()

BoolInterval codac2::IntvFullPivLU::is_invertible

(

)

const

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

Returns

a BoolInterval

is_surjective()

BoolInterval codac2::IntvFullPivLU::is_surjective

(

)

const

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

Returns

a BoolInterval

determinant()

Interval codac2::IntvFullPivLU::determinant

(

)

const

Return an interval enclosing the determinant.

Precondition

The matrix must be square.

Returns

the product of the diagonal elements of \([\mathbf{U}]\)

rank()

Interval codac2::IntvFullPivLU::rank

(

)

const

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

Returns

an interval enclosing the possible ranks.

dimension_of_kernel()

Interval codac2::IntvFullPivLU::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 built by kernel().

Returns

an interval enclosing the possible dimensions.

kernel()

IntervalMatrix codac2::IntvFullPivLU::kernel

(

)

const

Overapproximation of the kernel space as a matrix of column vectors. Any vector \(\mathbf{V}\) which is not a linear combination of the column vectors is guaranteed to be outside the kernel (i.e., \(\mathbf{M}\mathbf{V} \neq 0\)).

Returns

a matrix of column vectors, may be empty

cokernel()

IntervalMatrix codac2::IntvFullPivLU::cokernel

(

)

const

Overapproximation of the left-null ("cokernel") space as a matrix of row vectors. Any vector \(\mathbf{V}\) which is not a linear combination of the row vectors is guaranteed to be outside the kernel (i.e., \(\mathbf{V}\mathbf{M} \neq 0\)).

Returns

a matrix of row vectors, may be empty

image()

template<typename Derived>

Derived codac2::IntvFullPivLU::image ( const Eigen::MatrixBase< Derived > & M ) const

inline

"Underapproximation" of the column space of the matrix, i.e. 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.

Precondition

\(\mathbf{M}\) is the matrix used to build the decomposition

Parameters

M	the matrix used to build the decomposition.

Returns

a matrix of columns of \(\mathbf{M}\), or one vector of 0 if the rank of \(\mathbf{M}\) may be 0.

{
   int rk = this->rank().lb();
   if (rk==0) {
      return Derived::Zero(M.rows(),1); 
    /* NdDamien : où est-ce qu'on dit que Derived est une
       matrice ??? je crois que je hais le C++ ;)  */
   }
   Derived ret = 
    Derived::Zero(M.rows(),rk);
   Index p = 0;
   Index dim = std::min(matrixLU_.rows(),matrixLU_.cols());
   auto Q = this->_LU.permutationQ();
   for (Index i = 0; i<dim; i++) {
      if (!matrixLU_(i,i).contains(0.0)) {
         ret.col(p) = M.col(Q.indices().coeff(i));
         p++;
      }
   }
   return ret;
}

coimage()

template<typename Derived>

Derived codac2::IntvFullPivLU::coimage ( const Eigen::MatrixBase< Derived > & M ) const

inline

"Underapproximation" of the row space of the matrix, i.e. return a set of independant rows of the original matrix which is possibly maximal. As for Eigen, you must provide the original matrix used for the decomposition.

Precondition

M is the matrix used to build the decomposition

Parameters

M	the matrix used to build the decomposition.

Returns

a matrix of rows of \(\mathbf{M}\), or one row of 0 if the rank of \(\mathbf{M}\) may be 0.

{
   int rk = this->rank().lb();
   if (rk==0) {
      return Derived::Zero(1,M.cols()); 
   }
   Derived ret = 
    Derived::Zero(rk,M.cols());
   Index p = 0;
   Index dim = std::min(matrixLU_.rows(),matrixLU_.cols());
   auto P = this->_LU.permutationP();
   for (Index i = 0; i<dim; i++) {
      if (!matrixLU_(i,i).contains(0.0)) {
         ret.row(p) = M.row(P.indices().coeff(i));
         p++;
      }
   }
   return ret;
}

solve() [1/2]

IntervalMatrix codac2::IntvFullPivLU::solve

(

const IntervalMatrix &

rhs

)

const

Equation solving \(\mathbf{M}\mathbf{X}=\mathbf{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) if the goal is to prove the absence of solution, see solve with a bounding box.
• non empty presents the possible solutions found.

Parameters

rhs	right-hand side of the equation

Returns

a potential solution of the equation \(\mathbf{M}\mathbf{X}=\mathbf{rhs}\)

solve() [2/2]

void codac2::IntvFullPivLU::solve	(	const IntervalMatrix &	rhs,
		IntervalMatrix &	B ) const

Equation solving \(\mathbf{M}\mathbf{X}=\mathbf{rhs}\) with bounding matrix \([\mathbf{B}]\) for the solution, i.e. contraction of the matrix on the solutions on \(\mathbf{M}\mathbf{X}\).

Especially useful where the matrix is not full-rank, where solve without bounding box may return empty even if solutions exist.

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 inside the bounding matrix.
• non empty presents the possible solutions found.

Parameters

rhs	right-hand side of the equation
B	bounding-box of the left hand-side, contracted so that \(\mathbf{M}\mathbf{B}=\mathbf{rhs}\)

reconstructed_matrix()

IntervalMatrix codac2::IntvFullPivLU::reconstructed_matrix

(

)

const

Rebuilding of the matrix, i.e. compute \(\mathbf{P}^{-1}[\mathbf{L}][\mathbf{U}]\mathbf{Q}^{-1}\).

Can be used to evaluate the precision of the decomposition.

Returns

the reconstructed matrix

max_pivot()

double codac2::IntvFullPivLU::max_pivot

(

)

const

Maximum magnitude of the diagonal elements of \([\mathbf{U}]\).

Returns

the maximum

permutation_P()

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

inline

The permutation \(\mathbf{P}\) in the decomposition \(\mathbf{P}^{-1}\mathbf{L}\mathbf{U}\mathbf{Q}^{-1}\).

Returns

the permutation \(\mathbf{P}\), as defined by Eigen

                                          {
    return this->_LU.permutationP();
}

permutation_Q()

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

inline

The permutation \(\mathbf{Q}\) in the decomposition \(\mathbf{P}^{-1}\mathbf{L}\mathbf{U}\mathbf{Q}^{-1}\).

Returns

the permutation \(\mathbf{Q}\), as defined by Eigen

                                          {
    return this->_LU.permutationQ();
}

eigen_LU()

const Eigen::FullPivLU< Matrix > & codac2::IntvFullPivLU::eigen_LU ( ) const

inline

The Eigen decomposition of M.mid()

Returns

the Eigen decomposition

                                                                   {
    return this->_LU;
}

transformation()

const Row & codac2::IntvFullPivLU::transformation ( ) const

inline

Return the column-wise transformation done on M.mid() before the Eigen LU decomposition, as a Row.

Returns

the transformation

                                                      {
     return this->transform;
}

matrix_LU()

const IntervalMatrix & codac2::IntvFullPivLU::matrix_LU ( ) const

inline

Returns the matrix storing \([\mathbf{L}]\) and \([\mathbf{U}]\) (i.e. \([\mathbf{L}]\) for strictly lower part, \([\mathbf{U}]\) for upper part).

Returns

the interval matrix

                                                            {
     return this->matrixLU_;
}

---

The documentation for this class was generated from the following file:

• /home/simon/codac-simon/src/core/matrices/codac2_IntvFullPivLU.h