 CGAL 4.12 - dD Geometry Kernel
LinearAlgebraTraits_d Concept Reference

## Definition

The data type LinearAlgebraTraits_d encapsulates two classes Matrix, Vector and many functions of basic linear algebra. An instance of data type Matrix is a matrix of variables of type NT. Accordingly, Vector implements vectors of variables of type NT. Most functions of linear algebra are checkable, i.e., the programs can be asked for a proof that their output is correct. For example, if the linear system solver declares a linear system $$A x = b$$ unsolvable it also returns a vector $$c$$ such that $$c^T A = 0$$ and $$c^T b \neq 0$$.

Has Models:

CGAL::Linear_algebraHd<RT>

CGAL::Linear_algebraCd<FT>

## Types

typedef unspecified_type NT
the number type of the components.

typedef unspecified_type Vector
the vector type.

typedef unspecified_type Matrix
the matrix type.

## Operations

static Matrix transpose (const Matrix &M)
returns $$M^T$$ (a M.column_dimension() $$\times$$ M.column_dimension() - matrix).

static bool inverse (const Matrix &M, Matrix &I, NT &D, Vector &c)
determines whether M has an inverse. More...

static Matrix inverse (const Matrix &M, NT &D)
returns the inverse matrix of M. More...

static NT determinant (const Matrix &M, Matrix &L, Matrix &U, std::vector< int > &q, Vector &c)
returns the determinant $$D$$ of M and sufficient information to verify that the value of the determinant is correct. More...

static bool verify_determinant (const Matrix &M, NT D, Matrix &L, Matrix &U, const std::vector< int > &q, Vector &c)
verifies the conditions stated above.

static NT determinant (const Matrix &M)
returns the determinant of M. More...

static int sign_of_determinant (const Matrix &M)
returns the sign of the determinant of M. More...

static bool linear_solver (const Matrix &M, const Vector &b, Vector &x, NT &D, Matrix &spanning_vectors, Vector &c)
determines the complete solution space of the linear system $$M\cdot x = b$$. More...

static bool linear_solver (const Matrix &M, const Vector &b, Vector &x, NT &D, Vector &c)
determines whether the linear system $$M\cdot x = b$$ is solvable. More...

static bool linear_solver (const Matrix &M, const Vector &b, Vector &x, NT &D)
as above, but without the witness $$c$$ More...

static bool is_solvable (const Matrix &M, const Vector &b)
determines whether the system $$M \cdot x = b$$ is solvable More...

static bool homogeneous_linear_solver (const Matrix &M, Vector &x)
determines whether the homogeneous linear system $$M\cdot x = 0$$ has a non - trivial solution. More...

static int homogeneous_linear_solver (const Matrix &M, Matrix &spanning_vecs)
determines the solution space of the homogeneous linear system $$M\cdot x = 0$$. More...

static int independent_columns (const Matrix &M, std::vector< int > &columns)
returns the indices of a maximal subset of independent columns of M.

static int rank (const Matrix &M)
returns the rank of matrix M

## ◆ determinant() [1/2]

 static NT LinearAlgebraTraits_d::determinant ( const Matrix & M, Matrix & L, Matrix & U, std::vector< int > & q, Vector & c )
static

returns the determinant $$D$$ of M and sufficient information to verify that the value of the determinant is correct.

If the determinant is zero then $$c$$ is a vector such that $$c^T \cdot M = 0$$. If the determinant is non-zero then $$L$$ and $$U$$ are lower and upper diagonal matrices respectively and $$q$$ encodes a permutation matrix $$Q$$ with $$Q(i,j) = 1$$ iff $$i = q(j)$$ such that $$L \cdot M \cdot Q = U$$, $$L(0,0) = 1$$, $$L(i,i) = U(i - 1,i - 1)$$ for all $$i$$, $$1 \le i < n$$, and $$D = s \cdot U(n - 1,n - 1)$$ where $$s$$ is the determinant of $$Q$$.

Precondition
M is square.

## ◆ determinant() [2/2]

 static NT LinearAlgebraTraits_d::determinant ( const Matrix & M )
static

returns the determinant of M.

Precondition
M is square.

## ◆ homogeneous_linear_solver() [1/2]

 static bool LinearAlgebraTraits_d::homogeneous_linear_solver ( const Matrix & M, Vector & x )
static

determines whether the homogeneous linear system $$M\cdot x = 0$$ has a non - trivial solution.

If yes, then $$x$$ is such a solution.

## ◆ homogeneous_linear_solver() [2/2]

 static int LinearAlgebraTraits_d::homogeneous_linear_solver ( const Matrix & M, Matrix & spanning_vecs )
static

determines the solution space of the homogeneous linear system $$M\cdot x = 0$$.

It returns the dimension of the solution space. Moreover the columns of spanning_vecs span the solution space.

## ◆ inverse() [1/2]

 static bool LinearAlgebraTraits_d::inverse ( const Matrix & M, Matrix & I, NT & D, Vector & c )
static

determines whether M has an inverse.

It also computes either the inverse as $$(1/D) \cdot I$$ or when no inverse exists, a vector $$c$$ such that $$c^T \cdot M = 0$$.

Precondition
$$M$$ is square.

## ◆ inverse() [2/2]

 static Matrix LinearAlgebraTraits_d::inverse ( const Matrix & M, NT & D )
static

returns the inverse matrix of M.

More precisely, $$1/D$$ times the matrix returned is the inverse of M.

Precondition
determinant(M) != 0.
$$M$$ is square.

## ◆ is_solvable()

 static bool LinearAlgebraTraits_d::is_solvable ( const Matrix & M, const Vector & b )
static

determines whether the system $$M \cdot x = b$$ is solvable

Precondition
M.row_dimension() = b.dimension().

## ◆ linear_solver() [1/3]

 static bool LinearAlgebraTraits_d::linear_solver ( const Matrix & M, const Vector & b, Vector & x, NT & D, Matrix & spanning_vectors, Vector & c )
static

determines the complete solution space of the linear system $$M\cdot x = b$$.

If the system is unsolvable then $$c^T \cdot M = 0$$ and $$c^T \cdot b \not= 0$$. If the system is solvable then $$(1/D) x$$ is a solution, and the columns of spanning_vectors are a maximal set of linearly independent solutions to the corresponding homogeneous system.

Precondition
M.row_dimension() = b.dimension().

## ◆ linear_solver() [2/3]

 static bool LinearAlgebraTraits_d::linear_solver ( const Matrix & M, const Vector & b, Vector & x, NT & D, Vector & c )
static

determines whether the linear system $$M\cdot x = b$$ is solvable.

If yes, then $$(1/D) x$$ is a solution, if not then $$c^T \cdot M = 0$$ and $$c^T \cdot b \not= 0$$.

Precondition
M.row_dimension() = b.dimension().

## ◆ linear_solver() [3/3]

 static bool LinearAlgebraTraits_d::linear_solver ( const Matrix & M, const Vector & b, Vector & x, NT & D )
static

as above, but without the witness $$c$$

Precondition
M.row_dimension() = b.dimension().

## ◆ sign_of_determinant()

 static int LinearAlgebraTraits_d::sign_of_determinant ( const Matrix & M )
static

returns the sign of the determinant of M.

Precondition
M is square.