LinearAlgebraTraits_d

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

Types

Operations

static Matrix	LA.transpose ( Matrix M)	returns $$MT (a M.column_dimension() $$ × M.column_dimension() - matrix).
static bool	LA.inverse ( Matrix M, Matrix& I, NT& D, Vector& c)
		determines whether M has an inverse. It also computes either the inverse as $$(1/D) · I or when no inverse exists, a vector $$c such that $$cT · M = 0 . Precondition:  $$M is square.
static Matrix	LA.inverse ( Matrix M, NT& D)	returns the inverse matrix of M. More precisely, $$1/D times the matrix returned is the inverse of M. Precondition:  determinant(M) != 0. Precondition:  $$M is square.
static NT	LA.determinant ( 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. If the determinant is zero then $$c is a vector such that $$cT · 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 · M · Q = U, $$L(0,0) = 1, $$L(i,i) = U(i - 1,i - 1) for all $$i, $$1 i < n, and $$D = s · U(n - 1,n - 1) where $$s is the determinant of $$Q. Precondition:  M is square.
static bool	LA.verify_determinant ( Matrix M, NT D, Matrix& L, Matrix& U, std::vector<int> q, Vector& c)
		verifies the conditions stated above.
static NT	LA.determinant ( Matrix M)	returns the determinant of M. Precondition:  M is square.
static int	LA.sign_of_determinant ( Matrix M)
		returns the sign of the determinant of M. Precondition:  M is square.
static bool	LA.linear_solver ( Matrix M, Vector b, Vector& x, NT& D, Matrix& spanning_vectors, Vector& c)
		determines the complete solution space of the linear system $$M · x = b. If the system is unsolvable then $$cT · M = 0 and $$cT · b 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	LA.linear_solver ( Matrix M, Vector b, Vector& x, NT& D, Vector& c)
		determines whether the linear system M · x = b$$ is solvable. If yes, then (1/D) x$$ is a solution, if not then cT · M = 0$$ and cT · b 0. Precondition:  M.row_dimension() = b.dimension().
static bool	LA.linear_solver ( Matrix M, Vector b, Vector& x, NT& D)
		as above, but without the witness $$c Precondition:  M.row_dimension() = b.dimension().
static bool	LA.is_solvable ( Matrix M, Vector b)
		determines whether the system $$M · x = b is solvable Precondition:  M.row_dimension() = b.dimension().
static bool	LA.homogeneous_linear_solver ( Matrix M, Vector& x)
		determines whether the homogeneous linear system $$M · x = 0 has a non - trivial solution. If yes, then $$x is such a solution.
static int	LA.homogeneous_linear_solver ( Matrix M, Matrix& spanning_vecs)
		determines the solution space of the homogeneous linear system $$M · x = 0. It returns the dimension of the solution space. Moreover the columns of spanning_vecs span the solution space.
static int	LA.independent_columns ( Matrix M, std::vector<int>& columns)
		returns the indices of a maximal subset of independent columns of M.
static int	LA.rank ( Matrix M)	returns the rank of matrix M

Has Models

CGAL::Linear_algebraHd<RT>
CGAL::Linear_algebraCd<FT>