Sparse Matrix Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Sparse Matrix Ontology 2 within the Kireth Research Semantic Library. Sparse matrices are matrices in which most entries are zero and computational methods exploit that structure to reduce storage, arithmetic and communication costs. This ontology supports sparse storage formats, sparsity patterns, graph interpretations, sparse matrix-vector and matrix-matrix multiplication, sparse direct factorisation, fill-in, reordering, iterative solvers, preconditioning, incomplete factorisations, multigrid, distributed sparse computation, conditioning, stability and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = SparseMatrix
 ENTITY_CLASS = SparseLinearAlgebraFramework
 PRIMARY_CONTEXT = LinearAlgebraComputation
 DEFINITION = "A sparse matrix is a matrix with a sufficiently large proportion of zero entries that algorithms and storage structures can exploit sparsity for reduced computational and memory cost."
 SYMBOLIC_FORMS = [
  "nnz(A) << m*n",
  "y=A*x",
  "A=P*L*U",
  "fill(A_factor)>nnz(A)"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for sparse structure, sparse storage, graph-based sparsity, sparse factorisation, fill-in, reordering, iterative methods, preconditioning and scalable sparse linear algebra."
}

SCOPE {
 INCLUDE = [
  SparseMatrix,
  Sparsity,
  SparsityPattern,
  NonzeroEntry,
  ZeroEntry,
  NumberOfNonzeros,
  NNZ,
  SparseDensity,
  SparseStorage,
  CompressedSparseRow,
  CSR,
  CompressedSparseColumn,
  CSC,
  CoordinateFormat,
  COO,
  ELLPACK,
  DIAFormat,
  BlockSparseMatrix,
  BlockCSR,
  SparseVector,
  SparseMatrixVectorProduct,
  SpMV,
  SparseMatrixMatrixProduct,
  SpMM,
  SparseTranspose,
  SparseAddition,
  SparseScaling,
  SparseTriangularSolve,
  SparseLinearSystem,
  SparseLeastSquares,
  SparseEigenvalueProblem,
  GraphOfMatrix,
  AdjacencyGraph,
  BipartiteGraph,
  EliminationGraph,
  EliminationTree,
  FillIn,
  SymbolicFactorisation,
  NumericFactorisation,
  SparseLU,
  SparseCholesky,
  SparseQR,
  SparseLDLT,
  Pivoting,
  ThresholdPivoting,
  Reordering,
  FillReducingOrdering,
  MinimumDegreeOrdering,
  ApproximateMinimumDegree,
  AMD,
  NestedDissection,
  CuthillMcKee,
  ReverseCuthillMcKee,
  RCM,
  PermutationMatrix,
  RowPermutation,
  ColumnPermutation,
  DirectSparseSolver,
  IterativeSparseSolver,
  KrylovSubspace,
  ConjugateGradientMethod,
  GMRES,
  MINRES,
  BiCGSTAB,
  LSQR,
  LSMR,
  Preconditioner,
  JacobiPreconditioner,
  BlockJacobiPreconditioner,
  IncompleteLU,
  ILU,
  ILU0,
  ILUT,
  IncompleteCholesky,
  AlgebraicMultigrid,
  AMG,
  GeometricMultigrid,
  DomainDecomposition,
  SchwarzMethod,
  SparseConditioning,
  ConditionNumber,
  Scaling,
  Equilibration,
  DiagonalScaling,
  Residual,
  ForwardError,
  BackwardError,
  NumericalStability,
  RoundOffError,
  FloatingPointArithmetic,
  MachinePrecision,
  SparseLowRankStructure,
  LowRankUpdate,
  ShermanMorrisonWoodbury,
  SparseDirectMethod,
  SparseIterativeMethod,
  DistributedSparseMatrix,
  GraphPartitioning,
  MatrixPartitioning,
  DomainPartitioning,
  HaloExchange,
  CommunicationVolume,
  LoadBalancing,
  ParallelSpMV,
  GPUComputing,
  SparseGPUKernel,
  MemoryBandwidth,
  CacheLocality,
  ArithmeticIntensity,
  ComputationalComplexity,
  MemoryComplexity,
  Verification,
  Benchmarking,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  DenseMatrixWithoutSparsityExploitation,
  GraphTheoryWithoutMatrixRepresentation,
  DataCompressionWithoutLinearAlgebraSemantics,
  SparseDataStructuresWithoutMatrixOperations
 ]
 DISAMBIGUATION_RULE = "When matrix zero structure is explicitly exploited for storage, arithmetic, factorisation, iterative solution or parallel computation, interpret the context as sparse matrix computation."
}

CORE_CONCEPTS {
 SparseMatrix = "Matrix whose zero structure is exploited computationally."
 SparsityPattern = "Locations of nonzero entries in a sparse matrix."
 NumberOfNonzeros = "Count of explicitly represented nonzero entries."
 SparseStorage = "Compressed representation storing nonzero values and index information."
 FillIn = "New nonzero entries created during sparse factorisation."
 Reordering = "Permutation of rows and columns to improve fill, locality or solver behaviour."
 SparseFactorisation = "LU, Cholesky, QR or related factorisation performed while exploiting sparse structure."
 Preconditioner = "Approximate inverse or transformation improving iterative convergence."
 EliminationTree = "Graph structure describing dependencies in sparse factorisation."
}

RELATIONS {
 SparseMatrix --is_child_of--> LinearAlgebraComputation
 SparseMatrix --is_type_of--> Matrix
 SparseMatrix --has--> SparsityPattern
 SparseMatrix --has_measure--> NumberOfNonzeros
 SparseStorage --represents--> SparseMatrix
 CSR --is_type_of--> SparseStorage
 CSC --is_type_of--> SparseStorage
 COO --is_type_of--> SparseStorage
 SparseMatrixVectorProduct --operates_on--> SparseMatrix
 SparseMatrixMatrixProduct --operates_on--> SparseMatrix
 SparseLU --factorises--> SparseMatrix
 SparseCholesky --factorises--> SparsePositiveDefiniteMatrix
 SparseQR --factorises--> SparseMatrix
 Factorisation --can_create--> FillIn
 Reordering --can_reduce--> FillIn
 MinimumDegreeOrdering --is_type_of--> FillReducingOrdering
 NestedDissection --is_type_of--> FillReducingOrdering
 EliminationTree --represents--> FactorisationDependencies
 IncompleteLU --approximates--> LUFactorisation
 IncompleteCholesky --approximates--> CholeskyFactorisation
 Preconditioner --improves--> IterativeConvergence
 AMG --uses--> MultilevelHierarchy
 GraphPartitioning --supports--> DistributedSparseMatrix
 ParallelSpMV --is_limited_by--> MemoryBandwidth
}

OPERATORS {
 NNZ(A) := count_nonzero_entries(A)
 DENSITY(A) := nnz(A)/(rows(A)*cols(A))
 SPARSE_MATVEC(A,x) := y=A*x using_nonzero_entries_only
 SPARSE_MATMAT(A,B) := C=A*B using_sparse_structure
 PERMUTE(A,P,Q) := A_perm=P*A*Q
 FILL_RATIO(A,L,U) := (nnz(L)+nnz(U))/nnz(A)
 RELATIVE_RESIDUAL(A,x,b) := ||b-A*x||/(||A||*||x||+||b||)
 PRECONDITIONED_SYSTEM(M,A,x,b) := M^(-1)*A*x=M^(-1)*b
 LOW_RANK_UPDATE(A,U,V) := A_new=A+U*V^T
}

AXIOMS {
 A1 = "Sparsity is a structural property of a matrix representation and problem."
 A2 = "Sparse storage should avoid explicit representation of most zero entries."
 A3 = "Sparse factorisation can create fill-in even when the original matrix is highly sparse."
 A4 = "Reordering can change computational cost without changing the underlying linear problem."
 A5 = "Sparse iterative methods often trade arithmetic work for reduced memory compared with direct factorisation."
 A6 = "Preconditioning can be essential for practical convergence of large sparse systems."
 A7 = "Sparse matrix performance is frequently limited by memory movement and communication rather than floating-point throughput."
 A8 = "Sparse computations require explicit structure, storage, ordering, solver and reproducibility semantics."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,nnz,sparsity_pattern,symmetry,definiteness,problem_type)
 R2_STORAGE = choose(CSR,CSC,COO,block_or_other_sparse_format)
 R3_GRAPH = derive(adjacency_or_elimination_graph_if_useful)
 R4_METHOD = select(direct_sparse,iterative_Krylov,multigrid_or_hybrid_method)
 R5_ORDERING = if_direct choose(fill_reducing_ordering)
 R6_PRECONDITIONING = if_iterative choose(Jacobi,ILU,IC,AMG_or_domain_decomposition)
 R7_STABILITY = analyse(pivoting,scaling,conditioning,roundoff_and_breakdown)
 R8_PARALLEL = partition(matrix_or_graph,estimate_communication_and_load_balance)
 R9_COST = estimate(nnz_based_work,memory,fill,bandwidth_and_communication)
 R10_VALIDATION = compare(residuals,fill_ratio,convergence,memory,reference_solution_and_reproducibility)
}

CONSTRAINTS {
 C1 = "A matrix can be sparse yet expensive if its factorisation creates large fill-in."
 C2 = "CSR and CSC favour different access patterns."
 C3 = "Sparse matrix multiplication can substantially increase the number of nonzeros."
 C4 = "Ordering quality can dominate sparse direct-solver cost."
 C5 = "Incomplete factorisations can fail or become ineffective without suitable dropping, scaling or pivoting."
 C6 = "Standard conjugate gradients require symmetric positive-definite structure."
 C7 = "GMRES memory use increases with Krylov basis size unless restarted."
 C8 = "Parallel sparse performance can be dominated by irregular memory access and communication."
 C9 = "A low residual can still correspond to significant forward error for ill-conditioned sparse systems."
 C10 = "Sparse thresholds and drop tolerances can change numerical and structural behaviour."
}

SEMANTIC_EQUIVALENCE {
 "SparseMatrix" <=> "SparseMatrixRepresentation"
 "NumberOfNonzeros" <=> "NNZ"
 "CompressedSparseRow" <=> "CSR"
 "CompressedSparseColumn" <=> "CSC"
 "CoordinateFormat" <=> "COO"
 "SparseMatrixVectorProduct" <=> "SpMV"
 "SparseMatrixMatrixProduct" <=> "SpMM"
 "ApproximateMinimumDegree" <=> "AMD"
 "ReverseCuthillMcKee" <=> "RCM"
 "AlgebraicMultigrid" <=> "AMG"
}

VALIDATION {
 V1 = "Matrix dimensions and number of nonzeros are explicit."
 V2 = "Sparse storage format is documented."
 V3 = "Sparsity pattern and structural symmetry are identified where relevant."
 V4 = "Fill-in is measured for sparse direct methods."
 V5 = "Ordering strategy is documented."
 V6 = "Preconditioner and drop tolerances are documented."
 V7 = "Residual and conditioning are interpreted separately."
 V8 = "Memory and communication costs are measured for large-scale problems."
 V9 = "Reference or benchmark solutions are used where feasible."
 V10 = "Sparse computations are reproducible under documented ordering, solver and arithmetic settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 SPARSE_MATRIX_DEFINITION = 0.99
 STORAGE_REASONING = 0.99
 FILL_IN_REASONING = 0.99
 ORDERING_REASONING = 0.99
 SPARSE_FACTORISATION_REASONING = 0.99
 ITERATIVE_SOLVER_REASONING = 0.99
 PRECONDITIONING_REASONING = 0.98
 PARALLEL_SPARSE_REASONING = 0.98
 POLICY = "Reduce confidence when sparsity pattern, storage format, ordering, symmetry, preconditioner, drop tolerance, conditioning or partitioning are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, SparseMatrixReasoning,
  SparseStorageReasoning, CSRReasoning, CSCReasoning, COOReasoning,
  SpMVReasoning, SpMMReasoning, SparseFactorisationReasoning,
  FillInReasoning, ReorderingReasoning, EliminationTreeReasoning,
  SparseIterativeSolverReasoning, PreconditioningReasoning,
  ILUReasoning, IncompleteCholeskyReasoning, AMGReasoning,
  GraphPartitioningReasoning, ParallelSparseReasoning,
  MemoryBandwidthReasoning, KnowledgeGraphConstruction,
  RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "sparse matrix" -> SparseMatrix
  "NNZ" -> NumberOfNonzeros
  "CSR" -> CompressedSparseRow
  "CSC" -> CompressedSparseColumn
  "COO" -> CoordinateFormat
  "SpMV" -> SparseMatrixVectorProduct
  "SpMM" -> SparseMatrixMatrixProduct
  "AMD" -> ApproximateMinimumDegree
  "RCM" -> ReverseCuthillMcKee
  "AMG" -> AlgebraicMultigrid
 }
}

EXECUTION_RULES {
 E1 = "If matrix zero structure is computationally exploited, activate SparseMatrixOntology."
 E2 = "If repeated row-based matvecs dominate, consider CSR or an equivalent row-oriented format."
 E3 = "If column-oriented operations dominate, consider CSC or an equivalent column-oriented format."
 E4 = "If a sparse direct factorisation is used, analyse fill-in and choose an ordering."
 E5 = "If iterative solution is used, select a preconditioner suited to matrix structure."
 E6 = "If the matrix is symmetric positive definite, consider sparse Cholesky or conjugate gradients."
 E7 = "If the problem is large and distributed, partition the matrix or graph to balance work and communication."
 E8 = "If sparse kernels are bandwidth-bound, optimise locality and data movement."
 E9 = "Any sparse result should be validated for residual, fill, convergence, memory, communication and reproducibility."
}

RECURSION {
 ENTRY = SparseMatrix
 EXPAND(SparseMatrix) -> [
  Sparsity, SparsityPattern, NonzeroEntry, NumberOfNonzeros, SparseDensity,
  SparseStorage, CompressedSparseRow, CompressedSparseColumn,
  CoordinateFormat, ELLPACK, DIAFormat, BlockSparseMatrix, SparseVector,
  SparseMatrixVectorProduct, SparseMatrixMatrixProduct, SparseTranspose,
  SparseAddition, SparseScaling, SparseTriangularSolve,
  SparseLinearSystem, SparseLeastSquares, SparseEigenvalueProblem,
  GraphOfMatrix, AdjacencyGraph, BipartiteGraph, EliminationGraph,
  EliminationTree, FillIn, SymbolicFactorisation, NumericFactorisation,
  SparseLU, SparseCholesky, SparseQR, SparseLDLT, Pivoting,
  ThresholdPivoting, Reordering, FillReducingOrdering,
  MinimumDegreeOrdering, ApproximateMinimumDegree, NestedDissection,
  CuthillMcKee, ReverseCuthillMcKee, PermutationMatrix,
  DirectSparseSolver, IterativeSparseSolver, KrylovSubspace,
  ConjugateGradientMethod, GMRES, MINRES, BiCGSTAB, LSQR, LSMR,
  Preconditioner, JacobiPreconditioner, BlockJacobiPreconditioner,
  IncompleteLU, ILU0, ILUT, IncompleteCholesky, AlgebraicMultigrid,
  GeometricMultigrid, DomainDecomposition, SchwarzMethod,
  SparseConditioning, ConditionNumber, Scaling, Equilibration,
  Residual, ForwardError, BackwardError, NumericalStability,
  RoundOffError, FloatingPointArithmetic, SparseLowRankStructure,
  LowRankUpdate, DistributedSparseMatrix, GraphPartitioning,
  MatrixPartitioning, HaloExchange, CommunicationVolume, LoadBalancing,
  ParallelSpMV, GPUComputing, SparseGPUKernel, MemoryBandwidth,
  CacheLocality, ArithmeticIntensity, ComputationalComplexity,
  MemoryComplexity, Verification, Benchmarking, Reproducibility
 ]
 EXPAND(SparseFamilies) -> [
  SparseStorageFormats,
  SparseMatrixProducts,
  SparseDirectFactorisation,
  SparseIterativeSolvers,
  SparsePreconditioning,
  MultigridAndDomainDecomposition,
  DistributedSparseComputation
 ]
 STOP_CONDITION = "Stop when sparsity pattern, storage, ordering, solver, preconditioner, fill, communication and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Linear Algebra Computation"
 RELATED_ONTOLOGIES = [
  "Linear Algebra Computation",
  "Numerical Linear Algebra Ontology 2",
  "Matrix Computation Ontology",
  "Graph Theory Ontologies",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Scientific Computing Ontology 2",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "Sparse Matrix -> Linear Algebra Computation for parent semantics",
  "Sparse Matrix -> Numerical Linear Algebra for solver and factorisation theory",
  "Sparse Matrix -> Matrix Computation for storage and matrix operations",
  "Sparse Matrix -> Graph Theory for adjacency, ordering and partitioning",
  "Sparse Matrix -> Numerical Analysis for conditioning and error",
  "Sparse Matrix -> Numerical Convergence for iterative behaviour",
  "Sparse Matrix -> Scientific Computing for large discretised systems",
  "Sparse Matrix -> HPC for distributed sparse kernels and communication"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible sparse formats, solvers, preconditioners or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve sparse-versus-dense distinction.",
  "Preserve structural-zero-versus-stored-nonzero distinction.",
  "Preserve symbolic-versus-numeric factorisation distinction.",
  "Preserve ordering-versus-mathematical-problem distinction.",
  "Preserve direct-versus-iterative sparse solver distinction.",
  "Preserve fill-versus-original-sparsity distinction.",
  "Preserve local-computation-versus-communication-cost distinction.",
  "Preserve machine-readable sparse-matrix semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A sparse matrix is a matrix whose zero structure is explicitly exploited to reduce storage and computational cost."
 STORAGE_SUMMARY = "CSR, CSC, COO and block formats represent nonzero entries and indices without storing most zeros."
 PRODUCT_SUMMARY = "SpMV and SpMM perform matrix products while exploiting sparsity patterns."
 FACTORISATION_SUMMARY = "Sparse LU, Cholesky, QR and LDLT methods require ordering and fill management."
 ITERATIVE_SUMMARY = "Krylov methods often solve large sparse systems without forming dense factors."
 PRECONDITIONING_SUMMARY = "ILU, incomplete Cholesky, multigrid and domain decomposition can improve sparse iterative convergence."
 PARALLEL_SUMMARY = "Distributed sparse computation depends strongly on partitioning, communication volume, load balance and memory bandwidth."
 VALIDATION_SUMMARY = "Sparse computations should be checked for residual, fill, convergence, memory use, communication cost and reproducibility."
}

FLOW {
 INPUT
 -> detect_sparse_matrix_context
 -> identify_dimensions_nnz_sparsity_pattern_symmetry_definiteness_and_problem_type
 -> choose_sparse_storage_format
 -> if_direct_construct_graph_and_choose_fill_reducing_ordering
 -> select_sparse_LU_Cholesky_QR_LDLT_or_iterative_Krylov_method
 -> if_iterative_choose_preconditioner
 -> analyse_conditioning_scaling_pivoting_and_roundoff
 -> estimate_nnz_work_fill_memory_bandwidth_and_communication
 -> if_distributed_partition_matrix_or_graph_and_balance_load
 -> validate_residual_fill_ratio_convergence_memory_communication_and_reproducibility
 -> route_to_linear_algebra_computation_numerical_linear_algebra_matrix_computation_graph_theory_numerical_analysis_convergence_scientific_computing_or_HPC_ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Sparse Matrix Ontology 2 defines matrix computation that explicitly exploits zero structure. It supports sparsity patterns and nonzero counts, CSR, CSC, COO, ELLPACK, diagonal and block sparse formats, sparse matrix-vector and matrix-matrix multiplication, sparse triangular solves, sparse linear, least-squares and eigenvalue problems, matrix graphs, elimination trees, symbolic and numeric factorisation, sparse LU, Cholesky, QR and LDLT, fill-in, pivoting and fill-reducing ordering, minimum-degree, AMD, nested-dissection and RCM methods, Krylov solvers including CG, MINRES, GMRES and BiCGSTAB, LSQR and LSMR, Jacobi, ILU, incomplete-Cholesky and multigrid preconditioning, domain decomposition, scaling and conditioning, distributed sparse matrices, graph partitioning, halo exchange, parallel SpMV, GPU kernels, memory-bandwidth and communication costs, verification, benchmarking and reproducibility."
}

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

}

END_FLOW