Matrix Computation Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Matrix Computation Ontology within the Kireth Research Semantic Library. Matrix computation studies the numerical and algorithmic manipulation of matrices for solving linear systems, factorisation, eigenvalue problems, matrix functions, low-rank approximation, sparse computation and scientific applications. This ontology supports dense and sparse storage, matrix-vector and matrix-matrix products, decompositions, inversion and pseudoinversion, conditioning, stability, iterative methods, block algorithms, parallel computation and relationships with numerical linear algebra and computational mathematics.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = MatrixComputation
 ENTITY_CLASS = ComputationalMatrixOperationsFramework
 PRIMARY_CONTEXT = LinearAlgebraComputation
 DEFINITION = "Matrix computation is the algorithmic and numerical manipulation of matrices for solving linear systems, transformations, decompositions, eigenproblems, approximation and related computational tasks."
 SYMBOLIC_FORMS = [
  "C=A*B",
  "y=A*x",
  "A=P*L*U",
  "A=U*Sigma*V^T"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for matrix representation, arithmetic, factorisation, inversion, eigenvalue and singular-value computation, sparse algorithms, matrix functions, conditioning, stability and scalable execution."
}

SCOPE {
 INCLUDE = [
  MatrixComputation,
  Matrix,
  DenseMatrix,
  SparseMatrix,
  StructuredMatrix,
  SquareMatrix,
  RectangularMatrix,
  SymmetricMatrix,
  HermitianMatrix,
  PositiveDefiniteMatrix,
  PositiveSemidefiniteMatrix,
  OrthogonalMatrix,
  UnitaryMatrix,
  TriangularMatrix,
  UpperTriangularMatrix,
  LowerTriangularMatrix,
  DiagonalMatrix,
  BandedMatrix,
  BlockMatrix,
  ToeplitzMatrix,
  HankelMatrix,
  PermutationMatrix,
  IdentityMatrix,
  ZeroMatrix,
  MatrixEntry,
  MatrixDimension,
  MatrixShape,
  MatrixStorage,
  RowMajorStorage,
  ColumnMajorStorage,
  SparseStorage,
  CSR,
  CSC,
  COO,
  MatrixAddition,
  MatrixSubtraction,
  MatrixScaling,
  MatrixVectorProduct,
  MatrixMatrixProduct,
  MatrixTranspose,
  ConjugateTranspose,
  MatrixTrace,
  MatrixDeterminant,
  MatrixRank,
  MatrixNorm,
  FrobeniusNorm,
  SpectralNorm,
  MatrixInverse,
  Pseudoinverse,
  MoorePenrosePseudoinverse,
  MatrixPower,
  MatrixPolynomial,
  MatrixFunction,
  MatrixExponential,
  MatrixLogarithm,
  MatrixSquareRoot,
  LinearSystem,
  MatrixEquation,
  LeastSquaresProblem,
  MatrixFactorisation,
  LUDecomposition,
  LDUDecomposition,
  CholeskyDecomposition,
  LDLTDecomposition,
  QRDecomposition,
  SchurDecomposition,
  HessenbergReduction,
  TridiagonalReduction,
  SingularValueDecomposition,
  SVD,
  TruncatedSVD,
  EigenvalueProblem,
  GeneralisedEigenvalueProblem,
  PowerMethod,
  InverseIteration,
  RayleighQuotientIteration,
  QRAlgorithm,
  LanczosMethod,
  ArnoldiMethod,
  KrylovSubspace,
  MatrixConditionNumber,
  Conditioning,
  PerturbationAnalysis,
  Residual,
  ForwardError,
  BackwardError,
  NumericalStability,
  FloatingPointArithmetic,
  MachinePrecision,
  RoundOffError,
  Scaling,
  Equilibration,
  Pivoting,
  PartialPivoting,
  CompletePivoting,
  Reordering,
  FillIn,
  BlockAlgorithm,
  TiledAlgorithm,
  CacheAwareAlgorithm,
  SparseMatrixVectorProduct,
  SpMV,
  SparseMatrixMatrixProduct,
  SpMM,
  LowRankApproximation,
  RankRevealingFactorisation,
  RandomisedLinearAlgebra,
  RandomisedSVD,
  Sketching,
  KroneckerProduct,
  HadamardProduct,
  TensorProduct,
  ParallelMatrixComputation,
  DistributedMatrix,
  BlockCyclicDistribution,
  GPUComputing,
  BLAS,
  LAPACK,
  ScaLAPACK,
  MixedPrecision,
  IterativeRefinement,
  ComputationalComplexity,
  MemoryComplexity,
  CommunicationCost,
  Verification,
  Benchmarking,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  AbstractMatrixTheoryWithoutComputationalMethod,
  TensorComputationWithoutMatrixContext,
  PureSoftwareArrayManipulationWithoutMatrixSemantics,
  StatisticalTableOperationsWithoutLinearAlgebraMeaning
 ]
 DISAMBIGUATION_RULE = "When matrices are represented, transformed, multiplied, factorised, inverted, approximated or otherwise processed algorithmically, interpret the context as matrix computation."
}

CORE_CONCEPTS {
 MatrixComputation = "Algorithmic and numerical processing of matrices."
 MatrixStorage = "Representation of matrix entries in memory."
 MatrixVectorProduct = "Operation mapping vector x to A*x."
 MatrixMatrixProduct = "Operation computing the composition/product A*B."
 MatrixFactorisation = "Decomposition of a matrix into structured component matrices."
 MatrixInverse = "Matrix A^(-1) satisfying A*A^(-1)=I when it exists."
 Pseudoinverse = "Generalised inverse supporting least-squares and minimum-norm solutions."
 MatrixFunction = "Function defined on a matrix through spectral, polynomial, integral or related constructions."
 SparseMatrix = "Matrix whose zero structure is exploited computationally."
}

RELATIONS {
 MatrixComputation --is_child_of--> LinearAlgebraComputation
 MatrixComputation --uses--> MatrixStorage
 MatrixVectorProduct --operates_on--> Matrix
 MatrixMatrixProduct --composes--> LinearTransformations
 MatrixFactorisation --decomposes--> Matrix
 LUDecomposition --supports--> LinearSystemSolution
 QRDecomposition --supports--> LeastSquaresSolution
 CholeskyDecomposition --requires--> PositiveDefiniteStructure
 SingularValueDecomposition --supports--> RankAndConditionAnalysis
 Pseudoinverse --can_be_computed_from--> SVD
 MatrixConditionNumber --quantifies--> Sensitivity
 Scaling --can_improve--> NumericalBehaviour
 Pivoting --improves--> EliminationRobustness
 Reordering --can_reduce--> FillIn
 SparseStorage --reduces--> MemoryForSparseMatrices
 BlockAlgorithm --improves--> DataLocality
 ParallelMatrixComputation --accelerates--> LargeMatrixOperations
 RandomisedSVD --approximates--> DominantSingularSubspace
 IterativeRefinement --improves--> MatrixSolveAccuracy
}

OPERATORS {
 MATRIX_VECTOR(A,x) := y=A*x
 MATRIX_MATRIX(A,B) := C=A*B
 TRANSPOSE(A) := A^T
 CONJUGATE_TRANSPOSE(A) := A^*
 TRACE(A) := sum_i A_ii
 DETERMINANT(A) := det(A)
 INVERSE(A) := A^(-1) when_nonsingular
 PSEUDOINVERSE(A) := A^+
 LU_FACTOR(A) := P*A=L*U
 QR_FACTOR(A) := A=Q*R
 CHOLESKY_FACTOR(A) := A=L*L^T
 SVD_FACTOR(A) := A=U*Sigma*V^T
 MATRIX_FUNCTION(f,A) := f(A)
 KRONECKER(A,B) := A tensor B
 HADAMARD(A,B) := elementwise_product(A,B)
}

AXIOMS {
 A1 = "Matrix computation requires explicit dimensions and compatible shapes."
 A2 = "Matrix structure should be exploited when it improves accuracy, memory use or computational cost."
 A3 = "Explicit inversion is not generally required to solve linear systems."
 A4 = "Sparse algorithms should preserve sparsity where feasible."
 A5 = "Finite-precision arithmetic can materially alter exact matrix identities."
 A6 = "Conditioning and numerical stability must be distinguished."
 A7 = "Block and tiled algorithms can preserve mathematical semantics while improving data locality."
 A8 = "Matrix computation results require dimension, residual, error and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,structure,sparsity,precision,target_operation)
 R2_STORAGE = choose(dense,sparse,banded,block_or_distributed_representation)
 R3_OPERATION = classify(product,factorisation,solve,eigenproblem,SVD,function,inverse_or_approximation)
 R4_STRUCTURE = detect(symmetry,Hermitian_structure,definiteness,bandwidth,rank,sparsity)
 R5_METHOD = select(structure_appropriate_algorithm)
 R6_STABILITY = assess(pivoting,scaling,conditioning,roundoff_and_backward_error)
 R7_COMPLEXITY = estimate(flops,memory,communication_and_storage_cost)
 R8_SCALE = if_large use(blocking,parallelism,GPU_or_distributed_computation)
 R9_APPROXIMATION = if_low_rank use(truncated_or_randomised_factorisation)
 R10_VALIDATION = check_dimensions,residuals,error_bounds,reference_result_and_reproducibility)
}

CONSTRAINTS {
 C1 = "Matrix multiplication requires dimension compatibility."
 C2 = "Matrix multiplication is generally noncommutative."
 C3 = "An inverse exists only for nonsingular square matrices."
 C4 = "Explicit inversion can be less stable and more expensive than direct solution methods."
 C5 = "Sparse matrix multiplication can generate new nonzero entries."
 C6 = "Fill-in can dominate sparse factorisation memory cost."
 C7 = "Non-normal matrices can have sensitive eigenstructures."
 C8 = "Low-rank approximation quality depends on singular-value decay."
 C9 = "Parallel matrix algorithms can be communication-bound."
 C10 = "Identical mathematical operations can produce different low-order floating-point bits under different evaluation orders."
}

SEMANTIC_EQUIVALENCE {
 "MatrixComputation" <=> "ComputationalMatrixAlgebra"
 "SingularValueDecomposition" <=> "SVD"
 "SparseMatrixVectorProduct" <=> "SpMV"
 "SparseMatrixMatrixProduct" <=> "SpMM"
 "MoorePenrosePseudoinverse" <=> "Pseudoinverse"
 "BlockCyclicDistribution" <=> "BlockCyclicMatrixDistribution"
}

VALIDATION {
 V1 = "Matrix dimensions are explicit and compatible."
 V2 = "Matrix structure and sparsity are documented."
 V3 = "Storage format is appropriate to the operation."
 V4 = "Factorisation assumptions are checked."
 V5 = "Residuals are reported for solves and eigenproblems where relevant."
 V6 = "Conditioning and stability are assessed for sensitive computations."
 V7 = "Sparse fill and memory use are considered."
 V8 = "Parallel and distributed layouts are documented."
 V9 = "Reference or benchmark outputs are used where feasible."
 V10 = "Results are reproducible under documented arithmetic and execution settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 MATRIX_COMPUTATION_DEFINITION = 0.99
 MATRIX_PRODUCT_REASONING = 0.99
 FACTORISATION_REASONING = 0.99
 MATRIX_FUNCTION_REASONING = 0.98
 SPARSE_REASONING = 0.99
 CONDITIONING_REASONING = 0.99
 PARALLEL_REASONING = 0.98
 LOW_RANK_REASONING = 0.98
 POLICY = "Reduce confidence when dimensions, matrix structure, sparsity, arithmetic precision, storage format, conditioning or execution order are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, MatrixComputationReasoning,
  MatrixStorageReasoning, MatrixVectorProductReasoning,
  MatrixMatrixProductReasoning, MatrixFactorisationReasoning,
  MatrixInverseReasoning, PseudoinverseReasoning, MatrixFunctionReasoning,
  SparseMatrixReasoning, ConditioningReasoning, StabilityReasoning,
  LowRankReasoning, RandomisedLinearAlgebraReasoning,
  ParallelMatrixReasoning, GPUReasoning, KnowledgeGraphConstruction,
  RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "matrix computation" -> MatrixComputation
  "computational matrix algebra" -> MatrixComputation
  "SVD" -> SingularValueDecomposition
  "SpMV" -> SparseMatrixVectorProduct
  "SpMM" -> SparseMatrixMatrixProduct
  "pseudoinverse" -> MoorePenrosePseudoinverse
 }
}

EXECUTION_RULES {
 E1 = "If a matrix is processed algorithmically, activate MatrixComputationOntology."
 E2 = "Before an operation, verify matrix dimensions and structural assumptions."
 E3 = "If sparsity is substantial, select sparse storage and algorithms."
 E4 = "If solving rather than explicitly inverting, prefer a structure-appropriate solver."
 E5 = "If factorisation is required, select LU, QR, Cholesky, SVD or related methods according to matrix structure."
 E6 = "If low-rank structure exists, consider truncated or randomised approximations."
 E7 = "If scale is large, consider block, GPU, parallel or distributed matrix algorithms."
 E8 = "If numerical sensitivity matters, assess scaling, conditioning and round-off."
 E9 = "Any matrix computation should be validated for dimensions, residuals, stability, complexity and reproducibility."
}

RECURSION {
 ENTRY = MatrixComputation
 EXPAND(MatrixComputation) -> [
  Matrix, DenseMatrix, SparseMatrix, StructuredMatrix, SquareMatrix,
  RectangularMatrix, SymmetricMatrix, HermitianMatrix,
  PositiveDefiniteMatrix, OrthogonalMatrix, UnitaryMatrix,
  TriangularMatrix, DiagonalMatrix, BandedMatrix, BlockMatrix,
  ToeplitzMatrix, PermutationMatrix, MatrixEntry, MatrixDimension,
  MatrixShape, MatrixStorage, RowMajorStorage, ColumnMajorStorage,
  SparseStorage, CSR, CSC, COO, MatrixAddition, MatrixSubtraction,
  MatrixScaling, MatrixVectorProduct, MatrixMatrixProduct,
  MatrixTranspose, ConjugateTranspose, MatrixTrace, MatrixDeterminant,
  MatrixRank, MatrixNorm, FrobeniusNorm, SpectralNorm, MatrixInverse,
  Pseudoinverse, MatrixPower, MatrixPolynomial, MatrixFunction,
  MatrixExponential, MatrixLogarithm, MatrixSquareRoot, LinearSystem,
  MatrixEquation, LeastSquaresProblem, MatrixFactorisation,
  LUDecomposition, CholeskyDecomposition, QRDecomposition,
  SchurDecomposition, HessenbergReduction, TridiagonalReduction,
  SingularValueDecomposition, TruncatedSVD, EigenvalueProblem,
  PowerMethod, InverseIteration, RayleighQuotientIteration,
  QRAlgorithm, LanczosMethod, ArnoldiMethod, KrylovSubspace,
  MatrixConditionNumber, Conditioning, PerturbationAnalysis,
  Residual, ForwardError, BackwardError, NumericalStability,
  FloatingPointArithmetic, MachinePrecision, RoundOffError, Scaling,
  Equilibration, Pivoting, Reordering, FillIn, BlockAlgorithm,
  TiledAlgorithm, SparseMatrixVectorProduct, SparseMatrixMatrixProduct,
  LowRankApproximation, RankRevealingFactorisation,
  RandomisedLinearAlgebra, RandomisedSVD, Sketching,
  KroneckerProduct, HadamardProduct, ParallelMatrixComputation,
  DistributedMatrix, GPUComputing, MixedPrecision, IterativeRefinement,
  ComputationalComplexity, MemoryComplexity, CommunicationCost,
  Verification, Benchmarking, Reproducibility
 ]
 EXPAND(MatrixFamilies) -> [
  DenseMatrixComputation,
  SparseMatrixComputation,
  MatrixProducts,
  MatrixFactorisations,
  MatrixFunctions,
  EigenAndSingularValueComputation,
  LowRankMatrixComputation,
  ParallelAndDistributedMatrixComputation
 ]
 STOP_CONDITION = "Stop when matrix representation, operation, structure, algorithm, conditioning, stability, cost and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Linear Algebra Computation"
 RELATED_ONTOLOGIES = [
  "Linear Algebra Computation",
  "Numerical Linear Algebra Ontology 2",
  "Linear Algebra Ontologies",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Machine Precision Ontology",
  "Scientific Computing Ontology 2",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "Matrix Computation -> Linear Algebra Computation for parent semantics",
  "Matrix Computation -> Numerical Linear Algebra for numerical matrix algorithms",
  "Matrix Computation -> Linear Algebra Ontologies for abstract matrix structure",
  "Matrix Computation -> Numerical Methods for solver and approximation algorithms",
  "Matrix Computation -> Numerical Analysis for conditioning and stability",
  "Matrix Computation -> Floating Point Arithmetic for finite-precision effects",
  "Matrix Computation -> Scientific Computing for applied matrix models",
  "Matrix Computation -> HPC for large-scale parallel matrix operations"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible matrix operations, storage formats or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve mathematical-matrix-versus-storage representation distinction.",
  "Preserve dense-versus-sparse matrix distinction.",
  "Preserve solve-versus-explicit-inverse distinction.",
  "Preserve exact-factorisation-versus-low-rank approximation distinction.",
  "Preserve conditioning-versus-stability distinction.",
  "Preserve serial-versus-parallel evaluation distinction.",
  "Preserve machine-readable matrix-computation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Matrix computation applies numerical algorithms to represent, transform, multiply, factorise, solve and approximate matrices."
 STORAGE_SUMMARY = "Dense, sparse, banded, block and distributed storage formats support different computational structures."
 PRODUCT_SUMMARY = "Matrix-vector and matrix-matrix products are core operations underlying many numerical algorithms."
 FACTORISATION_SUMMARY = "LU, QR, Cholesky, Schur and SVD methods expose computationally useful structure."
 FUNCTION_SUMMARY = "Matrix exponentials, logarithms, square roots and other matrix functions extend scalar functional calculus to matrices."
 SPARSE_SUMMARY = "Sparse formats, reordering and fill control reduce memory and computation for large sparse problems."
 LOW_RANK_SUMMARY = "Truncated and randomised decompositions approximate matrices when dominant low-dimensional structure exists."
 VALIDATION_SUMMARY = "Matrix computations should be checked for dimensions, structural assumptions, residuals, conditioning, stability, computational cost and reproducibility."
}

FLOW {
 INPUT
 -> detect_matrix_computation_context
 -> identify_matrix_dimensions_structure_sparsity_precision_and_target_operation
 -> choose_dense_sparse_banded_block_or_distributed_storage
 -> classify_product_factorisation_solve_eigenproblem_SVD_function_inverse_or_approximation
 -> exploit_symmetry_definiteness_bandwidth_rank_and_sparsity
 -> select_structure_appropriate_algorithm
 -> assess_conditioning_scaling_pivoting_roundoff_and_stability
 -> estimate_flops_memory_communication_and_storage_cost
 -> if_large_scale_use_blocking_parallelism_GPU_or_distributed_execution
 -> if_low_rank_use_truncated_or_randomised_factorisation
 -> validate_dimensions_residuals_error_bounds_reference_results_and_reproducibility
 -> route_to_linear_algebra_computation_numerical_linear_algebra_linear_algebra_numerical_methods_analysis_floating_point_scientific_computing_or_HPC_ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Matrix Computation Ontology defines algorithmic processing of matrices. It supports dense, sparse, structured, square, rectangular, symmetric, Hermitian, positive-definite, orthogonal, triangular, diagonal, banded, block and Toeplitz matrices, dense and sparse storage formats, matrix addition, scaling, matrix-vector and matrix-matrix products, transpose and conjugate transpose, trace, determinant, rank and norms, inverses and pseudoinverses, matrix powers and functions, linear systems and least squares, LU, LDU, Cholesky, LDLT, QR, Schur, Hessenberg, tridiagonal and SVD factorizations, eigenvalue algorithms, conditioning, residual and error analysis, scaling and pivoting, sparse fill and reordering, block and tiled algorithms, low-rank and randomised matrix methods, Kronecker and Hadamard products, parallel and distributed matrix computation, GPU execution, mixed precision, iterative refinement, complexity, verification, benchmarking and reproducibility."
}

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

}

END_FLOW