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

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.

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

static

returns the determinant of M.

Precondition: M is square.

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.

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.

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.

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.

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().

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().

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().

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().

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

static

returns the sign of the determinant of M.

Precondition: M is square.

Definition

Types

Operations

Member Function Documentation