SparseLDLSolver

This component belongs to the category of LinearSolver. The role of the SparseLDLSolver is to solve the linear system $\mathbf{A}x=b$ assuming that the matrix $\mathbf{A}$ is symmetric and sparse.

To do so, the SparseLDLSolver relies on the method of LDL decomposition. The system matrix will be decomposed $\mathbf{A}=\mathbf{L}\mathbf{D}{\mathbf{L}}^T$, where $\mathbf{L}$ is a lower triangular matrix $\mathbf{A}$ and $\mathbf{D}$ is a diagonal matrix. This decomposition is an extension of the Cholesky decomposition which reduces its numerical inaccuracy.

As a direct solver, the SparseLDLSolver computes at each simulation time step an exact solution as follows:

$$\mathbf{L}\mathbf{D}{\mathbf{L}}^{T}x=b$$

Using a block forward substitution, we successively solve two triangular systems. Between those two resolutions, we need to inverse $\mathbf{D}$, which is trivial as it is a diagonal matrix that has no null value on its diagonal.

$$\{\begin{array}{l}\mathbf{A}x=b\\ \mathbf{A}={\mathbf{LDL}}^{\mathbf{T}}\end{array}⟺\{\begin{array}{l}\mathbf{L}z=b\\ \mathbf{D}y=z\\ {\mathbf{L}}^{T}x=y\end{array}$$

It is important to note that this decomposition considers that the system matrix $\mathbf{A}$ is symmetric.

Note that using permutation, the SparseLDLSolver will apply fill reducing permutation on the rows and the columns of $\mathbf{A}$ in order to minimize the number of non null values in $\mathbf{L}$ . Instead of solving $\mathbf{A}x=b$, we will solve $\mathbf{(}\mathbf{PAQ}\mathbf{)}\mathbf{(}{\mathbf{Q}}^{\mathbf{-}\mathbf{1}}x)=Pb$. Moreover, $\mathbf{A}$ is symmetric, so we will use the same permutation on the rows and on the columns with $\mathbf{Q}={\mathbf{P}}^T={\mathbf{P}}^{-1}$. We will factorize $\tilde{\mathbf{A}} =\mathbf{PAP^T} $ and then we will solve

$$\{\begin{array}{l}\tilde{\mathbf{A}}y=Pb\\ {\mathbf{Q}}^{-1}x=y\end{array}$$

As the impact of the use of fill reducing permutations on the performances is highly influenced by the repartition of the nodes used to model an object, we advise the users to test which type of permutation is the best suited for their simulations.

Sequence diagram

Usage

The SparseLDLSolver requires the use (above in the scene graph) of an integration scheme, and (below in the scene graph) of a MechanicalObject storing the state information that the SparseLDLSolver will access.

As a direct solver, the SparseLDLSolver might be extremely time consuming for large system. However, it will always give you an exact solution, making the assumption that the system matrix $\mathbf{A}$ is symmetric.

Direct linear solver using a Sparse LDL^T factorization.

CompressedRowSparseMatrixMat3x3d

Templates:

• CompressedRowSparseMatrixMat3x3d

Target: Sofa.Component.LinearSolver.Direct

namespace: sofa::component::linearsolver::direct

parents:

• SparseLDLSolverImpl

Data

Name	Description	Default value
name	object name	unnamed
printLog	if true, emits extra messages at runtime.	0
tags	list of the subsets the object belongs to
bbox	this object bounding box
componentState	The state of the component among (Dirty, Valid, Undefined, Loading, Invalid).	Undefined
listening	if true, handle the events, otherwise ignore the events	0
parallelInverseProduct	Parallelize the computation of the product J*M^{-1}*J^T where M is the matrix of the linear system and J is any matrix with compatible dimensions	0
precomputeSymbolicDecomposition	If true, the solver will reuse the precomputed symbolic decomposition, meaning that it will store the shape of [factor matrix] on the first step, or when its shape changes, and then it will only update its coefficients. When the shape of the matrix changes, a new factorization is computed.If false, the solver will compute the entire decomposition at each step	1
L_nnz	Number of non-zero values in the lower triangular matrix of the factorization. The lower, the faster the system is solved.	0

Links

Name	Description	Destination type name
context	Graph Node containing this object (or BaseContext::getDefault() if no graph is used)	BaseContext
slaves	Sub-objects used internally by this object	BaseObject
master	nullptr for regular objects, or master object for which this object is one sub-objects	BaseObject
linearSystem	The linear system to solve	TypedMatrixLinearSystem<CompressedRowSparseMatrixMat3x3d>
orderingMethod	Ordering method used by this component	BaseOrderingMethod

CompressedRowSparseMatrixd

Templates:

• CompressedRowSparseMatrixd

Target: Sofa.Component.LinearSolver.Direct

namespace: sofa::component::linearsolver::direct

parents:

• SparseLDLSolverImpl

Data

Name	Description	Default value
name	object name	unnamed
printLog	if true, emits extra messages at runtime.	0
tags	list of the subsets the object belongs to
bbox	this object bounding box
componentState	The state of the component among (Dirty, Valid, Undefined, Loading, Invalid).	Undefined
listening	if true, handle the events, otherwise ignore the events	0
parallelInverseProduct	Parallelize the computation of the product J*M^{-1}*J^T where M is the matrix of the linear system and J is any matrix with compatible dimensions	0
precomputeSymbolicDecomposition	If true, the solver will reuse the precomputed symbolic decomposition, meaning that it will store the shape of [factor matrix] on the first step, or when its shape changes, and then it will only update its coefficients. When the shape of the matrix changes, a new factorization is computed.If false, the solver will compute the entire decomposition at each step	1
L_nnz	Number of non-zero values in the lower triangular matrix of the factorization. The lower, the faster the system is solved.	0

Links

Name	Description	Destination type name
context	Graph Node containing this object (or BaseContext::getDefault() if no graph is used)	BaseContext
slaves	Sub-objects used internally by this object	BaseObject
master	nullptr for regular objects, or master object for which this object is one sub-objects	BaseObject
linearSystem	The linear system to solve	TypedMatrixLinearSystem<CompressedRowSparseMatrixd>
orderingMethod	Ordering method used by this component	BaseOrderingMethod