Processing math: 100%
CGAL 5.6 - dD Geometry Kernel
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
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
 

Member Function Documentation

◆ 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.