{
  "name": "BaseOrderingMethod",
  "main": {
    "name": "BaseOrderingMethod",
    "namespace": "sofa::core::behavior",
    "module": "Sofa.framework.Core",
    "include": "sofa/core/behavior/BaseOrderingMethod.h",
    "doc": "Abstract base class for ordering methods in sparse linear solvers\nA permutation is computed and applied on a sparse matrix to improve the\ncomputation time when solving a linear system.",
    "inherits": [
      "BaseObject"
    ],
    "templates": [],
    "data_fields": [],
    "links": [],
    "methods": [
      {
        "name": "computePermutation",
        "return_type": "void",
        "params": [
          {
            "name": "inPattern",
            "type": "const SparseMatrixPattern &"
          },
          {
            "name": "outPermutation",
            "type": "int *"
          },
          {
            "name": "outInversePermutation",
            "type": "int *"
          }
        ],
        "is_virtual": true,
        "is_pure_virtual": true,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "methodName",
        "return_type": "int",
        "params": [],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "computeInverseFromPermutation",
        "return_type": "void",
        "params": [
          {
            "name": "matrixSize",
            "type": "int"
          },
          {
            "name": "inPermutation",
            "type": "const int *"
          },
          {
            "name": "outInversePermutation",
            "type": "int *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "public"
      }
    ]
  },
  "desc": {
    "description": "The `BaseOrderingMethod` is an abstract base class within the SOFA framework that defines ordering methods for sparse linear solvers. Its primary role is to compute and apply permutations on sparse matrices to optimize computation time during the solution of linear systems. This class inherits from `BaseObject`, a fundamental component in SOFA's object model hierarchy.\n\nThe main method, `computePermutation`, is pure virtual and must be implemented by derived classes. It computes a permutation based on the input matrix pattern (`inPattern`) and outputs this permutation along with its inverse (`outInversePermutation`). The computed permutations help reduce the number of elements in the decomposition process, leading to faster linear system solutions.\n\nAnother notable method is `computeInverseFromPermutation`, which statically computes the inverse of a given permutation. This utility function can be useful for various numerical operations within SOFA's solvers and related components.\n\nUsage guidance involves deriving from this base class to implement specific ordering methods, ensuring that the `computePermutation` method is correctly defined. The implementation should focus on efficiently generating permutations that optimize sparse matrix factorizations."
  },
  "maths": {
    "maths": "The `BaseOrderingMethod` is an abstract base class in the SOFA framework that provides functionality for computing permutations on sparse matrices to optimize the performance of linear solvers. This optimization aims to reduce the computational complexity and time required to solve a linear system, particularly when dealing with large sparse matrices.\n\n### Role in Linear System Solution\n\nIn the context of solving a linear system \\(Ax = b\\), where \\(A\\) is a sparse matrix, the `BaseOrderingMethod` plays a crucial role by reordering the rows and columns of \\(A\\). This permutation can significantly affect the fill-in (non-zero elements introduced during factorization) in the factorized form of \\(A\\). By minimizing this fill-in, the computational cost of solving the linear system is reduced.\n\n### Key Methods\n\n#### `computePermutation`\n\nThis pure virtual method computes a permutation matrix \\(P\\), which reorders the rows and columns of the sparse matrix. The input to this method is the sparse matrix pattern (`inPattern`), which includes information such as the size of the matrix, the number of non-zero elements, and their positions.\n\nThe method outputs two arrays: `outPermutation`, representing the permutation itself, and `outInversePermutation`, representing its inverse. The permutation matrix \\(P\\) can be used to transform the original sparse matrix \\(A\\) into a reordered form \\(PA P^T\\), where \\(P^T\\) is the transpose of \\(P\\).\n\n#### `computeInverseFromPermutation`\n\nThis static method computes the inverse permutation given an input permutation array. It is useful for various numerical operations, such as reverting the reordering after solving the linear system.\n\n### Mathematical Representation\n\nGiven a sparse matrix \\(A\\) with dimensions \\(N \times N\\), and its pattern information:\n- `matrixSize` (the size of the matrix)\n- `numberOfNonZeros` (number of non-zero elements)\n- `rowBegin` (beginning indices for each row in a compressed sparse row format)\n- `colsIndex` (column indices for non-zero elements)\n\nThe method `computePermutation` computes a permutation vector \\(\\pi = [\\pi_0, \\pi_1, ..., \\pi_{N-1}]\\), where \\(\\pi_i\\) indicates the new position of row \\(i\\). The inverse permutation is computed such that applying both permutations results in the identity transformation:\n\n\begin{align*}\n    \forall i \text{ in } [0, N-1], &\text{ if } \\pi_j = i \text{ then } \\pi^{-1}_i = j \\\\[8pt]\n    PAP^T &= A_{reordered} \n\rend{align*}\n\nwhere \\(P\\) is the permutation matrix constructed from \\(π\\).\n\n### Application in SOFA\n\nIn the context of SOFA, this component can be used to optimize linear solvers within various numerical simulations. Sparse matrices often arise from discretization schemes like finite element methods (FEM), where reordering techniques are crucial for efficient computation.\n"
  },
  "summary": {
    "abstract": "`BaseOrderingMethod` is an abstract base class that defines ordering methods to compute permutations on sparse matrices, optimizing computation time in linear system solutions within SOFA simulations.",
    "sheet": "\n# BaseOrderingMethod\n\n## Overview\n\nThe `BaseOrderingMethod` is an abstract base class for defining ordering methods used in sparse linear solvers. It computes and applies permutations on the rows and columns of a sparse matrix to optimize computation time during the solution of linear systems.\n\n## Mathematical Model\n\nIn the context of solving a linear system \\(Ax = b\\), where \\(A\\) is a sparse matrix, `BaseOrderingMethod` reorders the rows and columns of \\(A\\). This permutation can significantly reduce fill-in (non-zero elements introduced during factorization) in the factorized form of \\(A\\).\n\nGiven a sparse matrix \\(A\\) with dimensions \\(N \\times N\\), and its pattern information:\n- `matrixSize` (the size of the matrix)\n- `numberOfNonZeros` (number of non-zero elements)\n- `rowBegin` (beginning indices for each row in a compressed sparse row format)\n- `colsIndex` (column indices for non-zero elements)\n\nThe method `computePermutation` computes a permutation vector \\(\\pi = [\\pi_0, \\pi_1, ..., \\pi_{N-1}]\\), where \\(\\pi_i\\) indicates the new position of row \\(i\\). The inverse permutation is computed such that applying both permutations results in the identity transformation:\n\n\begin{align*}\n    \forall i \text{ in } [0, N-1], &\text{ if } \\\\[8pt]\n    PAP^T &= A_{reordered} \n\rend{align*}\n\nwhere \\(P\\) is the permutation matrix constructed from \\(π\\)."
  }
}