CGAL 4.9 - CGAL and Solvers
Several CGAL packages have to solve linear systems with dense or sparse matrices. This package provides concepts and models for that purpose.
It is straightforward to develop equivalent models for other solvers, for example those found in the Intel Math Kernel Library (MKL).
DiagonalizeTraits<T,dim> defines an interface for the diagonalization and computation of eigenvectors and eigenvalues of a symmetric matrix.
T is the number type and
dim is the dimension of the matrices and vector (set to 3 by default). We provide two models for this concept:
Eigen_diagonalize_traits<T,dim>uses the Eigen library.
Diagonalize_traits<T,dim>is an internal implementation that does not depend on another library.
Although both models achieve the same computation,
Eigen_diagonalize_traits<T,dim> is faster and should thus be used if the Eigen library is available. The eigenvalues are stored in ascending order and eigenvectors are stored in accordance.
This is an example of an eigen decomposition of a matrix using this class:
SvdTraits defines an interface for solving in the least square sense a linear system with a singular value decomposition. The field type is
double. We provide the model
Eigen_svd that uses the Eigen library.
Here is a simple example that shows how to handle matrices, vectors and this solver:
We define 3 concepts for sparse linear algebra:
An interface to the sparse solvers from the Eigen library is provided as a model for these 3 concepts through the class
Eigen_solver_traits<T>. This solver traits class can be used for an iterative or a direct, symmetric or general sparse solvers. The specific solver to be used must be given as template parameter.
Each CGAL package using a sparse solver specifies which type of matrix and solver is required:
Here is an example that shows how to fill the sparse matrix and call the solver:
This package is the result of the increasing needs for linear solvers in CGAL. The first packages that introduced the solver concepts were Triangulated Surface Mesh Parameterization Reference, Poisson Surface Reconstruction Reference and Estimation of Local Differential Properties of Point-Sampled Surfaces Reference. At that time, these packages were relying on Taucs, LAPACK, BLAS and OpenNL. Gaël Guennebaud then introduced new models using the Eigen library that became the only supported models by CGAL. Later on the packages Triangulated Surface Mesh Skeletonization and Triangulated Surface Mesh Deformation extended the existing concepts.
Simon Giraudot was responsible for gathering all concepts and classes, and also wrote this user manual with the help of Andreas Fabri.