Sparse Matrix Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Sparse Matrix Ontology within the Kireth Research Semantic Library. Sparse matrix mathematics studies matrices in which most entries are zero and the computational methods used to store, manipulate, factorise and solve systems involving them efficiently. This ontology supports sparsity patterns, compressed storage formats, graph interpretations, fill-in, ordering, sparse direct solvers, iterative methods, preconditioning, matrix-free operators, sparse matrix-vector multiplication, sparse factorizations, parallel sparse computation and relationships with numerical linear algebra, scientific computing, high-performance computing, graph algorithms and finite-element systems.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Sparse Matrix Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Computational Mathematics / Sparse Matrices"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/computational-mathematics/sparse-matrix-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = SparseMatrix
 SYMBOLIC_FORMS = [
  "nnz(A) << m*n",
  "A x = b",
  "y = A x",
  "P A P^T = L U"
 ]
 ENTITY_CLASS = SparseLinearAlgebraRepresentationFramework
 PRIMARY_CONTEXT = ComputationalMathematics
 DEFINITION = "A sparse matrix is a matrix in which the number of nonzero entries is small relative to the total number of possible entries."
 SEMANTIC_ROLE = "Provides machine-readable semantics for sparsity patterns, compressed storage, sparse matrix operations, graph structure, reordering, fill-in, sparse factorisation, iterative solution and scalable sparse computation."
}

SCOPE {
 INCLUDE = [
  SparseMatrix,
  Sparsity,
  SparsityPattern,
  NonzeroEntry,
  ZeroEntry,
  NumberOfNonzeros,
  NNZ,
  SparseVector,
  SparseLinearSystem,
  SparseMatrixVectorProduct,
  SpMV,
  SparseMatrixMatrixProduct,
  SparseAddition,
  SparseTranspose,
  SparseFactorisation,
  SparseLU,
  SparseCholesky,
  SparseQR,
  FillIn,
  EliminationTree,
  EliminationGraph,
  GraphOfMatrix,
  AdjacencyGraph,
  BipartiteGraph,
  Reordering,
  PermutationMatrix,
  ReverseCuthillMcKee,
  MinimumDegreeOrdering,
  ApproximateMinimumDegree,
  NestedDissection,
  Bandwidth,
  Profile,
  SymmetricSparsityPattern,
  StructuralSymmetry,
  NumericalSymmetry,
  CSR,
  CSC,
  COO,
  DIA,
  ELL,
  BlockSparseMatrix,
  BSR,
  CompressedSparseRow,
  CompressedSparseColumn,
  CoordinateFormat,
  MatrixFreeOperator,
  Preconditioning,
  JacobiPreconditioner,
  ILU,
  IncompleteCholesky,
  AlgebraicMultigrid,
  KrylovMethod,
  ConjugateGradient,
  GMRES,
  BiCGSTAB,
  SparseDirectSolver,
  SparseIterativeSolver,
  SparseEigenproblem,
  ParallelSparseMatrix,
  DistributedSparseMatrix,
  GraphPartitioning,
  DomainDecomposition,
  SparseAssembly,
  FiniteElementAssembly
 ]

 EXCLUDE_AS_PRIMARY = [
  DenseMatrixWithoutSparsityStructure,
  GeneralGraphWithoutMatrixInterpretation,
  SymbolicMatrixExpressionWithoutSparseStorageOrComputation,
  LowRankMatrixWithoutSparseStructureAsPrimaryProperty
 ]

 DISAMBIGUATION_RULE =
  "When matrix structure, storage or computation is dominated by a relatively small set of nonzero entries, interpret the context as a sparse matrix problem."
}

CORE_CONCEPTS {

 SparseMatrix {
  definition = "A matrix whose nonzero entries are few relative to its total size."
 }

 SparsityPattern {
  definition = "The arrangement of zero and nonzero positions in a sparse matrix."
 }

 NumberOfNonzeros {
  definition = "The count of explicitly stored nonzero matrix entries."
 }

 SparseMatrixVectorProduct {
  definition = "Multiplication of a sparse matrix by a vector using only stored nonzero entries."
 }

 FillIn {
  definition = "New nonzero entries created during sparse factorisation."
 }

 Reordering {
  definition = "Permutation of rows and columns to improve factorisation, locality or bandwidth."
 }

 EliminationTree {
  definition = "A graph structure describing dependencies in sparse Cholesky- or related factorisation."
 }

 CSR {
  definition = "Compressed sparse row storage representing nonzeros by row."
 }

 CSC {
  definition = "Compressed sparse column storage representing nonzeros by column."
 }

 MatrixFreeOperator {
  definition = "An operator applied to vectors without explicitly storing its full matrix."
 }
}

RELATIONS {
 SparseMatrix --is_child_of--> ComputationalMathematics
 SparseMatrix --has--> SparsityPattern
 SparseMatrix --has--> NumberOfNonzeros
 SparseMatrixVectorProduct --uses--> SparseMatrix
 GraphOfMatrix --represents--> SparsityPattern
 Reordering --permutes--> SparseMatrix
 Reordering --can_reduce--> FillIn
 ReverseCuthillMcKee --reduces--> Bandwidth
 ApproximateMinimumDegree --targets--> FillInReduction
 NestedDissection --uses--> GraphPartitioning
 SparseLU --creates--> FillIn
 SparseCholesky --uses--> EliminationTree
 CSR --stores--> SparseMatrixByRows
 CSC --stores--> SparseMatrixByColumns
 COO --stores--> CoordinateTriples
 BSR --stores--> BlockSparseMatrix
 ILU --approximates--> SparseLU
 IncompleteCholesky --approximates--> SparseCholesky
 AlgebraicMultigrid --preconditions--> SparseLinearSystem
 KrylovMethod --solves--> SparseLinearSystem
 ParallelSparseMatrix --partitions--> NonzeroStructure
 FiniteElementAssembly --produces--> SparseMatrix
}

OPERATORS {
 SPARSITY_RATIO(A,m,n) :=
  s=nnz(A)/(m*n)

 DENSITY(A,m,n) :=
  d=nnz(A)/(m*n)

 SPMV(A,x) :=
  y=A*x using only explicitly stored nonzeros

 CSR_STORAGE(A) :=
  {values,column_indices,row_pointer}

 CSC_STORAGE(A) :=
  {values,row_indices,column_pointer}

 COO_STORAGE(A) :=
  {(i_k,j_k,a_k)} for each stored nonzero

 PERMUTED_MATRIX(P,A,Q) :=
  A_p=P*A*Q

 SYMMETRIC_REORDERING(P,A) :=
  A_p=P*A*P^T

 BANDWIDTH(A) :=
  max{|i-j| : a_ij != 0}

 PROFILE(A) :=
  sum_over_rows distance_from_diagonal_to_first_nonzero

 SPARSE_RESIDUAL(A,x,b) :=
  r=b-A*x

 FILL_RATIO(L,U,A) :=
  fill=(nnz(L)+nnz(U))/nnz(A)

 BLOCK_SPARSE_PRODUCT(A_block,x_block) :=
  y_block=A_block*x_block
}

DEFINITIONS {
 D1 = "Sparse matrices store and process only a subset of entries explicitly."
 D2 = "Sparsity pattern can be as important computationally as the numerical values."
 D3 = "Sparse storage reduces memory use when nnz is much smaller than the full matrix size."
 D4 = "Sparse matrix-vector multiplication is a core kernel in iterative numerical methods."
 D5 = "Factorisation can create fill-in outside the original sparsity pattern."
 D6 = "Reordering can reduce fill-in, bandwidth or communication."
 D7 = "Sparse matrices naturally correspond to graphs in many applications."
 D8 = "Finite-element and finite-volume discretisations commonly produce sparse matrices."
 D9 = "Matrix-free methods avoid explicit storage when operator application is cheaper."
 D10 = "Sparse performance depends strongly on memory access and irregular data movement."
}

AXIOMS {
 A1_EXPLICIT_NONZERO_STRUCTURE:
  SparseMatrix computation exploits explicitly represented nonzero structure

 A2_STORAGE_EFFICIENCY:
  Sparse storage should use memory proportional to nnz plus structural metadata

 A3_STRUCTURE_VALUE_DISTINCTION:
  Sparsity pattern is distinct from numerical values

 A4_FILL_IN:
  Sparse factorisation can increase the number of stored nonzeros

 A5_ORDERING:
  Row and column permutations can preserve the mathematical problem while changing computational cost

 A6_GRAPH_INTERPRETATION:
  Sparse matrix structure may be represented using graph or bipartite graph relationships

 A7_ITERATIVE_COMPATIBILITY:
  Sparse systems are commonly solved by iterative methods using efficient sparse matrix-vector products

 A8_PARALLEL_PARTITIONING:
  Large sparse matrices can be partitioned across computational resources by rows columns blocks or graph structure
}

REASONING {

 R1_SPARSE_MATRIX_CONTEXT {
  INPUT = matrix_problem
  IDENTIFY = dimensions
  IDENTIFY = nnz
  IDENTIFY = sparsity_pattern
  IDENTIFY = symmetry_block_structure_and_origin
  RETURN = sparse_matrix_context
 }

 R2_STORAGE_SELECTION {
  INPUT = sparse_matrix_context
  IF row_oriented_operations
   CONSIDER = CSR
  IF column_oriented_operations
   CONSIDER = CSC
  IF incremental_assembly
   CONSIDER = COO_then_compress
  IF block_structure
   CONSIDER = BSR
  RETURN = sparse_storage_strategy
 }

 R3_GRAPH_REASONING {
  INPUT = sparsity_pattern
  BUILD = graph_or_bipartite graph
  ANALYSE = connectivity_partitions_and_elimination structure
  RETURN = graph_profile
 }

 R4_REORDERING_REASONING {
  INPUT = sparse_pattern_and_solver
  SELECT = RCM_AMD_nestedDissection_or_other ordering
  ESTIMATE = bandwidth_fill_or_parallel benefit
  RETURN = reordered_matrix
 }

 R5_DIRECT_SOLVER_REASONING {
  INPUT = sparse_linear_system
  SELECT = sparseLU_sparseCholesky_or_sparseQR
  ANALYSE = pivoting_fill_memory_and_elimination tree
  RETURN = sparse_direct_solution
 }

 R6_ITERATIVE_SOLVER_REASONING {
  INPUT = large_sparse_system
  SELECT = CG_GMRES_BiCGSTAB_or_related Krylov method
  SELECT = preconditioner
  RETURN = sparse_iterative_strategy
 }

 R7_PRECONDITIONING_REASONING {
  INPUT = sparse_system
  SELECT = Jacobi_ILU_incompleteCholesky_AMG_or_domain decomposition
  ESTIMATE = setup_cost_memory_and_iteration reduction
  RETURN = preconditioned_system
 }

 R8_MATRIX_FREE_REASONING {
  INPUT = operator_application_and_memory constraints
  IF explicit_matrix_storage_expensive
   CONSIDER = matrix_free_operator
  RETURN = matrix_free_strategy
 }

 R9_PARALLEL_SPARSE_REASONING {
  INPUT = sparse_matrix_and_hardware
  PARTITION = rows_columns_blocks_or_graph
  ESTIMATE = local_nnz_communication_and_imbalance
  RETURN = distributed_sparse_strategy
 }

 R10_VALIDATION {
  INPUT = sparse_computation_result
  CHECK = residual_storage_integrity_ordering equivalence_fill_memory_convergence_and_parallel correctness
  RETURN = validated_sparse_status
 }
}

CONSTRAINTS {
 C1 = "Sparse storage is inefficient when matrix density becomes high."
 C2 = "Explicit zero values should not be confused with structurally absent entries."
 C3 = "Reordering changes computational structure but not the underlying linear mapping when permutations are applied consistently."
 C4 = "Sparse direct methods can require much more memory than the original matrix because of fill-in."
 C5 = "Pivoting for numerical stability can disrupt symbolic fill predictions."
 C6 = "CSR and CSC favour different access patterns."
 C7 = "SpMV is commonly memory-bandwidth limited."
 C8 = "Graph partitioning objectives may conflict with numerical load balance."
 C9 = "ILU and incomplete Cholesky quality depends strongly on drop tolerances and ordering."
 C10 = "Distributed sparse operations require explicit communication handling for off-process dependencies."
}

SEMANTIC_EQUIVALENCE {
 "SparseMatrix" <=> "SparseNumericalMatrix"
 "NumberOfNonzeros" <=> "NNZ"
 "CompressedSparseRow" <=> "CSR"
 "CompressedSparseColumn" <=> "CSC"
 "CoordinateFormat" <=> "COO"
 "SparseMatrixVectorProduct" <=> "SpMV"
}

VALIDATION {
 V1 = "Matrix dimensions and nnz are explicit."
 V2 = "Storage format is compatible with required operations."
 V3 = "Row and column indices are structurally valid."
 V4 = "Permutation operations preserve the mathematical system."
 V5 = "Fill-in and memory growth are measured for direct methods."
 V6 = "Residuals are checked after sparse solution."
 V7 = "Iterative convergence history is assessed."
 V8 = "Preconditioner setup and application costs are documented."
 V9 = "Distributed partitions balance nnz and communication."
 V10 = "Sparse assembly handles duplicate and accumulated entries consistently."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 SPARSE_MATRIX_DEFINITION = 0.99
 STORAGE_REASONING = 0.99
 GRAPH_REASONING = 0.98
 REORDERING_REASONING = 0.98
 DIRECT_SOLVER_REASONING = 0.98
 ITERATIVE_SOLVER_REASONING = 0.99
 PRECONDITIONING_REASONING = 0.98
 MATRIX_FREE_REASONING = 0.98
 PARALLEL_SPARSE_REASONING = 0.98

 POLICY =
  "Reduce confidence when sparsity pattern, nnz, matrix symmetry, ordering, pivoting, drop tolerances, partitioning, storage layout or convergence evidence are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  SparseMatrixReasoning,
  SparsityPatternReasoning,
  SparseStorageReasoning,
  CSRReasoning,
  CSCReasoning,
  COOReasoning,
  SparseMatrixVectorReasoning,
  GraphOfMatrixReasoning,
  ReorderingReasoning,
  FillInReasoning,
  SparseFactorisationReasoning,
  SparseLUReasoning,
  SparseCholeskyReasoning,
  SparseQRReasoning,
  SparseIterativeSolverReasoning,
  SparsePreconditioningReasoning,
  MatrixFreeReasoning,
  ParallelSparseReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "sparse matrix" -> SparseMatrix
  "sparsity pattern" -> SparsityPattern
  "number of nonzeros" -> NumberOfNonzeros
  "NNZ" -> NumberOfNonzeros
  "CSR" -> CompressedSparseRow
  "CSC" -> CompressedSparseColumn
  "COO" -> CoordinateFormat
  "SpMV" -> SparseMatrixVectorProduct
  "fill-in" -> FillIn
  "nested dissection" -> NestedDissection
 }

 INTERPRETATION_ORDER = [
  detect_sparse_matrix_context,
  identify dimensions_nnz_pattern_symmetry_block structure_and_origin,
  select storage format,
  construct graph interpretation_if useful,
  select ordering_and_partitioning,
  choose sparse_direct_iterative_or_matrixFree method,
  apply preconditioning_if_iterative,
  compute result,
  assess fill_memory_residual_convergence_and_parallel communication,
  validate sparse_structure_and_numerical equivalence,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("sparse matrix")
  OR matrix_has_relatively_few_nonzero entries
  THEN activate(SparseMatrixOntology)

 E2:
  IF rowwise SpMV_dominates
  THEN prefer CSR_like storage

 E3:
  IF columnwise_factorisation_or_access dominates
  THEN consider CSC_like storage

 E4:
  IF matrix_is_symmetric_positive_definite
  THEN consider SparseCholesky_or_CG

 E5:
  IF general_sparse_direct_solution
  THEN consider SparseLU_with_ordering_and_pivoting

 E6:
  IF large_sparse_system
  THEN consider Krylov_and_preconditioning

 E7:
  IF factorisation_fill_expected_large
  THEN assess AMD_nestedDissection_or_iterative alternatives

 E8:
  IF explicit_matrix_memory_is_prohibitive
  THEN consider MatrixFreeOperator

 E9:
  IF distributed_computation
  THEN partition_sparse_structure_and_account_for_off_process communication
}

RECURSION {
 ENTRY = SparseMatrix

 EXPAND(SparseMatrix) -> [
  Sparsity,
  SparsityPattern,
  NonzeroEntry,
  NumberOfNonzeros,
  SparseVector,
  SparseLinearSystem,
  SparseMatrixVectorProduct,
  SparseMatrixMatrixProduct,
  SparseAddition,
  SparseTranspose,
  SparseFactorisation,
  SparseLU,
  SparseCholesky,
  SparseQR,
  FillIn,
  EliminationTree,
  EliminationGraph,
  GraphOfMatrix,
  AdjacencyGraph,
  BipartiteGraph,
  Reordering,
  PermutationMatrix,
  ReverseCuthillMcKee,
  MinimumDegreeOrdering,
  ApproximateMinimumDegree,
  NestedDissection,
  Bandwidth,
  Profile,
  SymmetricSparsityPattern,
  StructuralSymmetry,
  NumericalSymmetry,
  CSR,
  CSC,
  COO,
  DIA,
  ELL,
  BlockSparseMatrix,
  BSR,
  MatrixFreeOperator,
  Preconditioning,
  JacobiPreconditioner,
  ILU,
  IncompleteCholesky,
  AlgebraicMultigrid,
  KrylovMethod,
  ConjugateGradient,
  GMRES,
  BiCGSTAB,
  SparseDirectSolver,
  SparseIterativeSolver,
  SparseEigenproblem,
  ParallelSparseMatrix,
  DistributedSparseMatrix,
  GraphPartitioning,
  DomainDecomposition,
  SparseAssembly,
  FiniteElementAssembly
 ]

 EXPAND(StorageFormats) -> [
  CSR,
  CSC,
  COO,
  DIA,
  ELL,
  BSR
 ]

 EXPAND(SparseSolvers) -> [
  SparseLU,
  SparseCholesky,
  SparseQR,
  ConjugateGradient,
  GMRES,
  BiCGSTAB,
  AlgebraicMultigrid
 ]

 STOP_CONDITION =
  "Stop when sparsity structure, storage, ordering, fill, solver, preconditioner, residual, memory use and parallel partitioning are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Mathematics"

 IMMEDIATE_CONTEXTS = [
  "Computational Mathematics Ontology",
  "Numerical Linear Algebra Ontology",
  "Scientific Computing Ontology",
  "High Performance Computing Ontology"
 ]

 RELATED_ONTOLOGIES = [
  "Computational Mathematics",
  "Computational Mathematics Ontology",
  "Numerical Linear Algebra Ontology",
  "Scientific Computing Ontology",
  "High Performance Computing Ontology",
  "Parallel Algorithms Ontology",
  "Matrix Ontologies",
  "Graph Algorithm Ontologies",
  "Finite Element Ontology",
  "Finite Volume Ontologies",
  "Sparse Direct Solver Ontologies",
  "Krylov Method Ontologies",
  "Preconditioning Ontologies",
  "Distributed Systems Ontologies"
 ]

 ROUTE_RULES = [
  "Sparse Matrix -> Computational Mathematics for parent semantics",
  "Sparse Matrix -> Numerical Linear Algebra for matrix algorithms",
  "Sparse Matrix -> Scientific Computing for assembled simulation systems",
  "Sparse Matrix -> High Performance Computing for distributed sparse kernels",
  "Sparse Matrix -> Parallel Algorithms for partitioned sparse operations",
  "Sparse Matrix -> Graph Algorithms for ordering and partitioning",
  "Sparse Matrix -> Finite Element and Finite Volume for sparse system assembly",
  "Sparse Matrix -> Krylov and Preconditioning Ontologies for iterative solution",
  "Sparse Matrix -> Distributed Systems for communication-aware partitioning"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible sparse storage formats, orderings or solver pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve sparse-structure semantics.",
  "Preserve sparsity-pattern-versus-value distinction.",
  "Preserve storage-format semantics.",
  "Preserve fill-in and reordering semantics.",
  "Preserve sparse direct-versus-iterative distinction.",
  "Preserve matrix-free semantics.",
  "Preserve distributed sparse partition semantics.",
  "Preserve machine-readable sparse-matrix semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "A sparse matrix is a matrix with relatively few nonzero entries, enabling storage and computation proportional to its nonzero structure."

 STORAGE_SUMMARY =
  "CSR, CSC, COO and block-sparse formats store nonzero values together with indexing metadata."

 GRAPH_SUMMARY =
  "Sparse matrix patterns can be interpreted as graphs for ordering, elimination and partitioning."

 FACTORISATION_SUMMARY =
  "Sparse direct factorisation must manage fill-in, pivoting, elimination structure and memory growth."

 ITERATIVE_SUMMARY =
  "Large sparse systems are commonly solved with Krylov methods and sparse preconditioners."

 MATRIX_FREE_SUMMARY =
  "Matrix-free approaches apply the operator without explicitly storing every matrix entry."

 PARALLEL_SUMMARY =
  "Distributed sparse computation partitions rows, columns, blocks or graph structure while managing off-process communication."

 VALIDATION_SUMMARY =
  "Sparse computations should be checked for structural integrity, residuals, fill, convergence, memory use and parallel consistency."
}

FLOW {
 INPUT
 -> detect_sparse_matrix_context
 -> identify matrix_dimensions_nnz_pattern_symmetry_block structure_and_application origin
 -> choose CSR_CSC_COO_BSR_or_other storage
 -> if_graph_useful construct adjacency_or_bipartite representation
 -> choose ordering_for_bandwidth_fill_or_parallelism
 -> choose sparseLU_sparseCholesky_sparseQR_Krylov_or_matrixFree pathway
 -> if_iterative select preconditioner
 -> if_parallel partition sparse_structure
 -> compute factorisation_product_eigenpair_or_linear-system solution
 -> evaluate residual_fill_memory_convergence_and_communication
 -> validate structural_and_numerical equivalence
 -> route to computational_mathematics numerical_linear_algebra scientific_computing high_performance_computing parallel_algorithms matrix graph finite_element finite_volume sparse_solver Krylov preconditioning_or_distributed_systems ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Sparse Matrix Ontology defines sparse matrix structure and computation. It supports sparsity patterns, nonzero counts, sparse vectors and systems, sparse matrix-vector and matrix-matrix operations, sparse LU, Cholesky and QR factorisation, fill-in, elimination trees and graphs, graph interpretations, permutations, reverse Cuthill-McKee, minimum-degree and nested-dissection orderings, bandwidth and profile, structural and numerical symmetry, CSR, CSC, COO, DIA, ELL and block-sparse storage, matrix-free operators, Jacobi, ILU, incomplete Cholesky and algebraic multigrid preconditioning, Krylov solvers, sparse eigenproblems, distributed sparse matrices, graph partitioning, domain decomposition and finite-element sparse assembly."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-APPLIED-MATHEMATICS-SPARSE-MATRIX-ONTOLOGY-V1"
}

}

END_FLOW