{
  "name": "ConstantSparsityPatternSystem",
  "main": {
    "name": "ConstantSparsityPatternSystem",
    "namespace": "sofa::component::linearsystem",
    "module": "Sofa.Component.LinearSystem",
    "include": "sofa/component/linearsystem/ConstantSparsityPatternSystem.h",
    "doc": "Linear system taking advantage of the constant sparsity pattern of the global matrix to speed up the matrix assembly. Do not use if sparsity pattern is not constant (topological changes, ...).\n\nAssembling method benefitting from the constant sparsity pattern of the linear system in order to increase the\nperformances.\nThis method must not be used if the sparsity pattern changes from a time step to another.\nThe method uses the first iteration to build the data structures required to accelerate the matrix assembly, based\non a constant sparsity pattern.\nFirst iteration:\n1) During the accumulation of matrix contributions, the local matrix stores an ordered list of matrix elements (row\nand column) corresponding to the order of insertion. This order must not change along the simulation.\n2) After the matrix assembly, the global matrix is compressed so that the ordered list of matrix elements can be\nconverted into an ordered list of ids corresponding to locations in the values array of the compressed matrix.\nSecond time step and after:\n1) The local matrices assume the order of insertion did not change. Therefore, they rely only on the ordered list of\nids to know where in the values array to insert the matrix contribution. The row and column ids are useless.",
    "inherits": [
      "MatrixLinearSystem"
    ],
    "templates": [
      "linearalgebra::CompressedRowSparseMatrix<SReal>, linearalgebra::FullVector<SReal>"
    ],
    "data_fields": [],
    "links": [],
    "methods": [
      {
        "name": "applyProjectiveConstraints",
        "return_type": "void",
        "params": [
          {
            "name": "mparams",
            "type": "const core::MechanicalParams *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "resizeSystem",
        "return_type": "void",
        "params": [
          {
            "name": "n",
            "type": "int"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "clearSystem",
        "return_type": "void",
        "params": [],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "isConstantSparsityPatternUsedYet",
        "return_type": "bool",
        "params": [],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "preAssembleSystem",
        "return_type": "void",
        "params": [
          {
            "name": "",
            "type": "const core::MechanicalParams *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "replaceLocalMatrices",
        "return_type": "void",
        "params": [
          {
            "name": "mparams",
            "type": "const core::MechanicalParams *"
          },
          {
            "name": "matrixMaps",
            "type": "LocalMatrixMaps<c, Real> &"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "replaceLocalMatrixMapped",
        "return_type": "void",
        "params": [
          {
            "name": "mparams",
            "type": "const core::MechanicalParams *"
          },
          {
            "name": "matrixMaps",
            "type": "LocalMatrixMaps<c, Real> &"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "replaceLocalMatricesNonMapped",
        "return_type": "void",
        "params": [
          {
            "name": "mparams",
            "type": "const core::MechanicalParams *"
          },
          {
            "name": "matrixMaps",
            "type": "LocalMatrixMaps<c, Real> &"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "replaceLocalMatrixNonMapped",
        "return_type": "void",
        "params": [
          {
            "name": "mparams",
            "type": "const core::MechanicalParams *"
          },
          {
            "name": "matrixMaps",
            "type": "LocalMatrixMaps<c, Real> &"
          },
          {
            "name": "component",
            "type": "int *"
          },
          {
            "name": "localMatrix",
            "type": "BaseAssemblingMatrixAccumulator<c> *&"
          },
          {
            "name": "states",
            "type": "const typename Inherit1::PairMechanicalStates &"
          },
          {
            "name": "sparsityPatternMatrix",
            "type": "SparsityPatternLocalMatrix<c, TStrategy> *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "reinitLocalMatrices",
        "return_type": "void",
        "params": [
          {
            "name": "matrixMaps",
            "type": "LocalMatrixMaps<c, Real> &"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "buildHashTable",
        "return_type": "void",
        "params": [
          {
            "name": "M",
            "type": "int &"
          },
          {
            "name": "mapping",
            "type": "int &"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "protected"
      },
      {
        "name": "makeCreateDispatcher",
        "return_type": "void",
        "params": [],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "makeIndexVerificationStrategy",
        "return_type": "int",
        "params": [
          {
            "name": "component",
            "type": "sofa::core::objectmodel::BaseObject *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      }
    ]
  },
  "desc": {
    "title": "Constant Sparsity Pattern System",
    "description": "This component is a specialized linear system designed to take advantage of the constant sparsity pattern in the global matrix assembly process, which can significantly speed up simulation performance when applicable.",
    "parameters": [],
    "detailed_description": {
      "general_info": "The Constant Sparsity Pattern System is a linear system component specifically optimized for scenarios where the structure (sparsity pattern) of the global matrix remains unchanged throughout the simulation. It leverages this constant sparsity to accelerate the assembly process, thereby improving performance.",
      "usage_notes": [
        "This method should not be used when the topology of the model changes dynamically as it assumes a consistent sparsity pattern across time steps.",
        "During the first iteration, the system builds internal data structures necessary for efficient matrix accumulation. These include an ordered list of matrix elements and their corresponding indices in the compressed sparse row (CSR) format.",
        "From the second iteration onwards, these precomputed indices are used to directly insert contributions into the global matrix, bypassing the need for potentially expensive element lookups or checks."
      ],
      "technical_details": {
        "class_hierarchy": [
          "sofa::component::linearsystem::ConstantSparsityPatternSystem<MatrixType, VectorType>"
        ],
        "template_specializations": [
          "sofa::linearalgebra::CompressedRowSparseMatrix<SReal>",
          "sofa::linearalgebra::FullVector<SReal>"
        ]
      },
      "example_use_case": {
        "description": "A common use case for the Constant Sparsity Pattern System is in simulations where the topology of the system remains fixed, such as certain types of soft tissue modeling or rigid body dynamics with predefined contact points.",
        "code_example": [
          "auto constantSparsitySystem = sofa::core::objectmodel::New<sofa::component::linearsystem::ConstantSparsityPatternSystem<sofa::linearalgebra::CompressedRowSparseMatrix<SReal>, sofa::linearalgebra::FullVector<SReal>>>();",
          "// Add to the scene graph and connect with other components as needed."
        ]
      },
      "limitations": [
        "Does not support dynamic changes in topology. If elements are added or removed from the simulation, this component will not function correctly.",
        "Requires that all matrix contributions are inserted in a consistent order across time steps. Any change in insertion order can lead to incorrect results."
      ],
      "related_components": [
        {
          "name": "MatrixLinearSystem",
          "description": "Base class for linear systems using matrices and vectors for solving linear equations."
        },
        {
          "name": "CompressedRowSparseMatrix",
          "description": "A data structure for storing sparse matrices in compressed row format, used by this system to store the global matrix."
        }
      ]
    }
  },
  "maths": {
    "maths": "# Mathematical and Physical Description of ConstantSparsityPatternSystem\n\n## Introduction\n\nThe `ConstantSparsityPatternSystem` is a specialized linear system designed to optimize the assembly process for matrices whose sparsity pattern remains constant over time. The key idea behind this optimization is that, by leveraging knowledge about the constant structure of the matrix, the computational overhead associated with identifying and updating non-zero entries can be minimized.\n\n## Constant Sparsity Pattern Assumption\n\nA *sparsity pattern* refers to the locations of the non-zero elements in a matrix. In many simulation contexts, particularly those involving finite element methods or contact dynamics, the sparsity pattern often remains invariant over time, even as the actual values at these positions change.\n\n### First Iteration: Building the Data Structures\n1. **Matrix Contributions Accumulation**: During the first assembly pass, local matrices accumulate contributions to the global matrix and simultaneously record an ordered list of their respective row-column (RC) pairs that correspond to non-zero elements.\n2. **Ordering Constraint**: The assumption is made that the order in which these RC pairs are added does not change over subsequent iterations; this is critical for maintaining performance gains.\n3. **Compression Step**: After assembling the global matrix, it undergoes a compression process where duplicate and zero entries are eliminated, leaving behind a compressed representation (e.g., Compressed Row Storage or CRS format).\n\n### Subsequent Iterations: Utilizing Constant Patterns\n1. **Pre-Computed Indices**: The system relies on pre-computed indices that map RC pairs to specific locations in the values array of the compressed matrix.\n2. **Direct Value Insertion**: During each subsequent iteration, local matrices directly insert their contributions into the global matrix using these indices instead of recalculating positions based on row and column IDs. This process is significantly faster since it bypasses checks for sparsity patterns.\n\n## Mathematical Representation\n\nLet's denote the global matrix as \\(A\\), a sparse matrix with dimensions \\(N \\times N\\).\n- **Sparsity Pattern**: Denote the set of non-zero indices in \\(A\\) by \\(\text{S}(A) = \big\">(indices)_i | A[(index)]_i \neq 0 \big\">)\n\nFor a constant sparsity pattern, \\(\text{S}(A_t) = \text{S}(A_{t+1})\\), where \\(t\\) denotes the time step.\n\n### Index Mapping and Assembly Process\n- **Index Mapping**: Let \\(\text{M}\\) be the mapping function from RC pairs to index positions in the compressed array. For an entry at \\((i, j)\\):\n  \n  $$\text{M}(i, j) = k$$\n\n  where \\(k\\) is the position of the non-zero value in the compressed matrix.\n- **Matrix Assembly**: In the subsequent time steps, contributions from local matrices to global positions are directly inserted using these mappings:\n  \n  $$A[k] += \text{local_contribution}$$\n\n### Performance Implications\nThe key performance gain comes from avoiding repeated computations of sparsity checks and position lookups. Instead, the system relies on pre-computed indices for direct value insertion.\n\n## Physical Interpretation\nIn physical terms, this approach is particularly useful in simulations where the connectivity (or adjacency) between elements remains constant over time but their interactions change dynamically. For instance:\n- **Finite Element Methods**: The mesh structure remains fixed while material properties or applied forces vary.\n- **Contact Dynamics**: Contacts and collisions occur between predefined sets of objects, maintaining a consistent interaction pattern.\n\n## Conclusion\nBy leveraging the invariant sparsity pattern in matrix assembly, `ConstantSparsityPatternSystem` significantly accelerates linear system solutions, making it suitable for simulations where the underlying topology does not change over time. This optimization is particularly beneficial in scenarios with large-scale systems and complex interactions that maintain a constant structure."
  },
  "summary": {
    "abstract": "The `ConstantSparsityPatternSystem` optimizes linear system solutions by exploiting a constant sparsity pattern in matrix assembly, significantly speeding up simulations where topological changes do not occur.",
    "sheet": "# ConstantSparsityPatternSystem\n\n## Overview\n\nThe `ConstantSparsityPatternSystem` is a specialized linear system designed to optimize the assembly process for matrices whose sparsity patterns remain constant over time. This optimization leverages pre-computed indices and avoids repeated computations of sparsity checks, leading to significant performance gains in simulations where topological changes do not occur.\n\n## Mathematical Model\n\nThe `ConstantSparsityPatternSystem` operates under the assumption that the sparsity pattern of the global matrix remains constant over time. This allows for efficient assembly by pre-computing indices and directly inserting values into the compressed matrix representation.\n\n### First Iteration: Building Data Structures\n1. **Matrix Contributions Accumulation**: During the first iteration, local matrices accumulate contributions to the global matrix while recording an ordered list of row-column (RC) pairs corresponding to non-zero elements.\n2. **Ordering Constraint**: The order in which these RC pairs are added is assumed to remain constant over subsequent iterations.\n3. **Compression Step**: After assembling the global matrix, it undergoes compression where duplicate and zero entries are eliminated, leaving a compressed representation (e.g., Compressed Row Storage or CRS format).\n\n### Subsequent Iterations: Utilizing Constant Patterns\n1. **Pre-Computed Indices**: The system relies on pre-computed indices that map RC pairs to specific locations in the values array of the compressed matrix.\n2. **Direct Value Insertion**: During each subsequent iteration, local matrices directly insert their contributions into the global matrix using these indices instead of recalculating positions based on row and column IDs.\n\n### Mathematical Representation\nLet's denote the global matrix as \\(A\\), a sparse matrix with dimensions \\(N \\times N\\).\n- **Sparsity Pattern**: Denote the set of non-zero indices in \\(A\\) by \\(S(A) = \\{(i, j) | A_{ij} \neq 0\\}\\).\n\nFor a constant sparsity pattern, \\(S(A_t) = S(A_{t+1})\\), where \\(t\\) denotes the time step.\n\n### Index Mapping and Assembly Process\n- **Index Mapping**: Let \\(M\\) be the mapping function from RC pairs to index positions in the compressed array. For an entry at \\((i, j)\\):\n  \n  $$ M(i, j) = k $$\n\n  where \\(k\\) is the position of the non-zero value in the compressed matrix.\n- **Matrix Assembly**: In subsequent time steps, contributions from local matrices to global positions are directly inserted using these mappings:\n  \n  $$ A[k] += \\text{local_contribution} $$\n\n### Performance Implications\nThe key performance gain comes from avoiding repeated computations of sparsity checks and position lookups. Instead, the system relies on pre-computed indices for direct value insertion."
  }
}