Dense Matrix Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Dense Matrix Ontology within the Kireth Research Semantic Library. Dense matrices are matrices represented and processed without relying on sparsity, typically storing all entries explicitly. This ontology supports dense storage layouts, matrix-vector and matrix-matrix products, dense direct solvers, LU, QR, Cholesky, Schur and singular-value decompositions, eigenvalue computation, cache-aware and block algorithms, conditioning, stability, floating-point error, GPU and distributed dense linear algebra and relationships with numerical linear algebra, matrix computation and high-performance computing.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = DenseMatrix
 ENTITY_CLASS = DenseLinearAlgebraFramework
 PRIMARY_CONTEXT = LinearAlgebraComputation
 DEFINITION = "A dense matrix is a matrix whose entries are stored and processed explicitly without assuming that most entries are zero."
 SYMBOLIC_FORMS = [
  "A in R^(m x n)",
  "y=A*x",
  "C=A*B",
  "A=Q*R"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for dense matrix representation, dense arithmetic, direct factorisation, eigenvalue and singular-value computation, memory layout, cache-aware algorithms and scalable dense linear algebra."
}

SCOPE {
 INCLUDE = [
  DenseMatrix,
  DenseLinearAlgebra,
  Matrix,
  SquareMatrix,
  RectangularMatrix,
  SymmetricMatrix,
  HermitianMatrix,
  PositiveDefiniteMatrix,
  PositiveSemidefiniteMatrix,
  OrthogonalMatrix,
  UnitaryMatrix,
  TriangularMatrix,
  UpperTriangularMatrix,
  LowerTriangularMatrix,
  DiagonalMatrix,
  BandedMatrix,
  BlockMatrix,
  MatrixEntry,
  MatrixDimension,
  MatrixShape,
  DenseStorage,
  FullStorage,
  RowMajorStorage,
  ColumnMajorStorage,
  LeadingDimension,
  Stride,
  ContiguousStorage,
  MatrixAddition,
  MatrixSubtraction,
  MatrixScaling,
  MatrixVectorProduct,
  GEMV,
  MatrixMatrixProduct,
  GEMM,
  RankKUpdate,
  SYRK,
  HERK,
  TriangularSolve,
  TRSV,
  TriangularMatrixMatrixSolve,
  TRSM,
  MatrixTranspose,
  ConjugateTranspose,
  MatrixTrace,
  MatrixDeterminant,
  MatrixRank,
  MatrixNorm,
  FrobeniusNorm,
  SpectralNorm,
  LinearSystem,
  DenseLinearSystem,
  LeastSquaresProblem,
  DirectSolver,
  GaussianElimination,
  Pivoting,
  PartialPivoting,
  CompletePivoting,
  RookPivoting,
  ForwardSubstitution,
  BackSubstitution,
  LUDecomposition,
  LDUDecomposition,
  CholeskyDecomposition,
  LDLTDecomposition,
  QRDecomposition,
  HouseholderTransformation,
  GivensRotation,
  GramSchmidtProcess,
  ModifiedGramSchmidt,
  SchurDecomposition,
  HessenbergReduction,
  TridiagonalReduction,
  SingularValueDecomposition,
  SVD,
  EigenvalueProblem,
  GeneralisedEigenvalueProblem,
  QRAlgorithm,
  DivideAndConquerEigenSolver,
  Bidiagonalisation,
  Pseudoinverse,
  MatrixInverse,
  MatrixFunction,
  MatrixExponential,
  MatrixSquareRoot,
  MatrixLogarithm,
  ConditionNumber,
  Conditioning,
  Scaling,
  Equilibration,
  PerturbationAnalysis,
  Residual,
  ForwardError,
  BackwardError,
  NumericalStability,
  BackwardStability,
  GrowthFactor,
  FloatingPointArithmetic,
  MachinePrecision,
  RoundOffError,
  MixedPrecision,
  IterativeRefinement,
  BlockAlgorithm,
  BlockedFactorisation,
  TiledAlgorithm,
  CacheAwareAlgorithm,
  CacheObliviousAlgorithm,
  DataLocality,
  ArithmeticIntensity,
  MemoryBandwidth,
  BLAS,
  BLAS1,
  BLAS2,
  BLAS3,
  LAPACK,
  ScaLAPACK,
  GPUComputing,
  GPUKernel,
  DistributedDenseMatrix,
  BlockCyclicDistribution,
  ParallelDenseLinearAlgebra,
  CommunicationCost,
  ComputationalComplexity,
  MemoryComplexity,
  Verification,
  Benchmarking,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  SparseMatrixWhenZeroStructureIsExplicitlyExploited,
  AbstractMatrixTheoryWithoutComputationalRepresentation,
  TensorComputationWithoutDenseMatrixContext,
  PureArrayProgrammingWithoutLinearAlgebraSemantics
 ]
 DISAMBIGUATION_RULE = "When a matrix is stored and processed essentially as a full array of entries rather than through sparsity structure, interpret the context as dense matrix computation."
}

CORE_CONCEPTS {
 DenseMatrix = "Matrix represented by explicitly storing its entries in a full or near-full layout."
 DenseStorage = "Memory representation containing explicit matrix entries rather than compressed nonzero structure."
 MatrixVectorProduct = "Dense operation computing y=A*x."
 MatrixMatrixProduct = "Dense operation computing C=A*B."
 BlockAlgorithm = "Matrix algorithm organised around submatrices to improve data reuse."
 DenseFactorisation = "LU, QR, Cholesky, Schur, SVD or related factorisation operating on dense matrix storage."
 DataLocality = "Reuse of nearby or cached matrix data to reduce memory-transfer cost."
 ArithmeticIntensity = "Ratio of arithmetic operations to data movement."
}

RELATIONS {
 DenseMatrix --is_child_of--> LinearAlgebraComputation
 DenseMatrix --is_type_of--> Matrix
 DenseStorage --represents--> DenseMatrix
 RowMajorStorage --is_type_of--> DenseStorage
 ColumnMajorStorage --is_type_of--> DenseStorage
 MatrixVectorProduct --operates_on--> DenseMatrix
 MatrixMatrixProduct --operates_on--> DenseMatrix
 GEMV --implements--> MatrixVectorProduct
 GEMM --implements--> MatrixMatrixProduct
 LUDecomposition --factorises--> DenseMatrix
 CholeskyDecomposition --factorises--> DensePositiveDefiniteMatrix
 QRDecomposition --factorises--> DenseMatrix
 SVD --factorises--> DenseMatrix
 SchurDecomposition --factorises--> DenseSquareMatrix
 BlockAlgorithm --improves--> DataLocality
 BLAS3 --supports--> HighArithmeticIntensity
 LAPACK --uses--> BLAS
 ScaLAPACK --supports--> DistributedDenseMatrix
 GPUComputing --accelerates--> DenseMatrixOperations
 ConditionNumber --quantifies--> DenseProblemSensitivity
 Pivoting --controls--> EliminationGrowth
 IterativeRefinement --improves--> DenseSolveAccuracy
}

OPERATORS {
 DENSE_MATVEC(A,x) := y=A*x
 DENSE_MATMAT(A,B) := C=A*B
 TRANSPOSE(A) := A^T
 CONJUGATE_TRANSPOSE(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
 SCHUR_FACTOR(A) := A=Q*T*Q^*
 RESIDUAL(A,x,b) := r=b-A*x
 CONDITION_NUMBER(A) := kappa(A)=||A||*||A^(-1)||
 GEMM_COST(m,n,k) := approximately 2*m*n*k floating_point_operations
}

AXIOMS {
 A1 = "Dense matrix algorithms explicitly process stored matrix entries without relying on dominant zero structure."
 A2 = "Matrix dimensions and storage layout affect both correctness and performance."
 A3 = "BLAS-3-style blocked operations typically provide better data reuse than scalar or vector-level formulations."
 A4 = "Conditioning belongs to the matrix problem, while numerical stability belongs to the algorithm."
 A5 = "Pivoting may be necessary for stable dense elimination."
 A6 = "Orthogonal transformations provide favourable numerical stability for many dense algorithms."
 A7 = "Dense matrix computation is often limited by arithmetic throughput for high-intensity kernels and by memory movement for lower-intensity kernels."
 A8 = "Dense computations require explicit precision, layout, solver and reproducibility semantics."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,structure,precision,target_operation,hardware_context)
 R2_LAYOUT = choose(row_major,column_major,blocked_or_distributed_storage)
 R3_STRUCTURE = detect(symmetry,Hermitian_structure,definiteness,triangularity_and_rank)
 R4_METHOD = select(product,LU,QR,Cholesky,SVD,Schur,eigensolver_or_matrix_function)
 R5_STABILITY = analyse(pivoting,orthogonality,conditioning,roundoff_and_backward_error)
 R6_BLOCKING = choose(block_size_or_tiled_form_to_improve_data_reuse)
 R7_KERNEL = map_operation_to_BLAS_or_equivalent_high_performance_kernel)
 R8_PARALLEL = if_large use(threaded,GPU_or_distributed_dense_algorithm)
 R9_COST = estimate(flops,memory_traffic,arithmetic_intensity_and_communication)
 R10_VALIDATION = compare(residuals,error_bounds,reference_result,performance_and_reproducibility)
}

CONSTRAINTS {
 C1 = "Dense storage requires O(m*n) memory."
 C2 = "Dense matrix multiplication is generally noncommutative."
 C3 = "Explicit matrix inversion is often less desirable than solving linear systems."
 C4 = "Classical Gaussian elimination without pivoting can be numerically unstable."
 C5 = "Normal equations can worsen conditioning in least-squares problems."
 C6 = "Classical Gram-Schmidt can lose orthogonality in finite precision."
 C7 = "GPU or accelerator speedup depends on problem size, transfer cost and kernel efficiency."
 C8 = "Distributed dense algorithms can be communication-bound at scale."
 C9 = "Mixed precision requires explicit tracking of compute and accumulation formats."
 C10 = "Dense treatment can be wasteful when strong sparsity is present."
}

SEMANTIC_EQUIVALENCE {
 "DenseMatrix" <=> "FullMatrix"
 "MatrixVectorProduct" <=> "GEMVInDenseContext"
 "MatrixMatrixProduct" <=> "GEMMInDenseContext"
 "SingularValueDecomposition" <=> "SVD"
 "BlockCyclicDistribution" <=> "BlockCyclicMatrixDistribution"
 "DenseLinearAlgebra" <=> "FullMatrixLinearAlgebra"
}

VALIDATION {
 V1 = "Matrix dimensions are explicit."
 V2 = "Storage layout is documented."
 V3 = "Structural assumptions are verified."
 V4 = "Factorisation and solver residuals are checked."
 V5 = "Conditioning is assessed for sensitive problems."
 V6 = "Pivoting and orthogonality are monitored where relevant."
 V7 = "Arithmetic precision and mixed-precision stages are documented."
 V8 = "Block sizes or tiled strategies are documented when performance matters."
 V9 = "Parallel and distributed execution layouts are documented."
 V10 = "Results are reproducible under documented arithmetic and execution settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 DENSE_MATRIX_DEFINITION = 0.99
 STORAGE_REASONING = 0.99
 GEMM_REASONING = 0.99
 FACTORISATION_REASONING = 0.99
 CONDITIONING_REASONING = 0.99
 BLOCKING_REASONING = 0.98
 GPU_REASONING = 0.98
 DISTRIBUTED_REASONING = 0.98
 POLICY = "Reduce confidence when layout, structure, precision, pivoting, block size, hardware mapping or distributed data layout are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, DenseMatrixReasoning,
  DenseStorageReasoning, GEMVReasoning, GEMMReasoning,
  DenseFactorisationReasoning, LUReasoning, QRReasoning,
  CholeskyReasoning, SVDReasoning, SchurReasoning,
  EigenvalueReasoning, ConditioningReasoning, StabilityReasoning,
  BlockingReasoning, BLASReasoning, GPUReasoning,
  DistributedDenseReasoning, MixedPrecisionReasoning,
  KnowledgeGraphConstruction, RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "dense matrix" -> DenseMatrix
  "full matrix" -> DenseMatrix
  "GEMV" -> MatrixVectorProduct
  "GEMM" -> MatrixMatrixProduct
  "SVD" -> SingularValueDecomposition
  "dense linear algebra" -> DenseLinearAlgebra
 }
}

EXECUTION_RULES {
 E1 = "If a matrix is stored and processed as a full array of entries, activate DenseMatrixOntology."
 E2 = "If structure such as symmetry or positive definiteness is present, choose structure-aware dense algorithms."
 E3 = "If matrix multiplication dominates, map computation to high-intensity GEMM-style kernels."
 E4 = "If solving linear systems, choose LU, Cholesky, QR or related methods according to structure."
 E5 = "If least squares are ill-conditioned, use QR or SVD rather than naive normal equations."
 E6 = "If performance matters, use blocked or tiled algorithms to improve data locality."
 E7 = "If scale is large, consider threaded, GPU or distributed dense linear algebra."
 E8 = "If lower precision is used, consider iterative refinement and higher-precision accumulation."
 E9 = "Any dense matrix result should be validated for dimensions, residuals, conditioning, stability, cost and reproducibility."
}

RECURSION {
 ENTRY = DenseMatrix
 EXPAND(DenseMatrix) -> [
  DenseLinearAlgebra, Matrix, SquareMatrix, RectangularMatrix,
  SymmetricMatrix, HermitianMatrix, PositiveDefiniteMatrix,
  OrthogonalMatrix, UnitaryMatrix, TriangularMatrix, DiagonalMatrix,
  BandedMatrix, BlockMatrix, MatrixEntry, MatrixDimension, MatrixShape,
  DenseStorage, FullStorage, RowMajorStorage, ColumnMajorStorage,
  LeadingDimension, Stride, ContiguousStorage, MatrixAddition,
  MatrixSubtraction, MatrixScaling, MatrixVectorProduct, GEMV,
  MatrixMatrixProduct, GEMM, RankKUpdate, SYRK, HERK,
  TriangularSolve, TRSV, TRSM, MatrixTranspose, ConjugateTranspose,
  MatrixTrace, MatrixDeterminant, MatrixRank, MatrixNorm,
  FrobeniusNorm, SpectralNorm, LinearSystem, DenseLinearSystem,
  LeastSquaresProblem, DirectSolver, GaussianElimination, Pivoting,
  ForwardSubstitution, BackSubstitution, LUDecomposition,
  LDUDecomposition, CholeskyDecomposition, LDLTDecomposition,
  QRDecomposition, HouseholderTransformation, GivensRotation,
  GramSchmidtProcess, ModifiedGramSchmidt, SchurDecomposition,
  HessenbergReduction, TridiagonalReduction, SVD, EigenvalueProblem,
  GeneralisedEigenvalueProblem, QRAlgorithm, Bidiagonalisation,
  Pseudoinverse, MatrixInverse, MatrixFunction, MatrixExponential,
  MatrixSquareRoot, MatrixLogarithm, ConditionNumber, Conditioning,
  Scaling, Equilibration, PerturbationAnalysis, Residual, ForwardError,
  BackwardError, NumericalStability, GrowthFactor,
  FloatingPointArithmetic, MachinePrecision, RoundOffError,
  MixedPrecision, IterativeRefinement, BlockAlgorithm,
  BlockedFactorisation, TiledAlgorithm, CacheAwareAlgorithm,
  DataLocality, ArithmeticIntensity, MemoryBandwidth, BLAS, LAPACK,
  ScaLAPACK, GPUComputing, DistributedDenseMatrix,
  BlockCyclicDistribution, ParallelDenseLinearAlgebra,
  CommunicationCost, ComputationalComplexity, MemoryComplexity,
  Verification, Benchmarking, Reproducibility
 ]
 EXPAND(DenseFamilies) -> [
  DenseStorageAndLayout,
  DenseMatrixProducts,
  DenseDirectSolvers,
  DenseFactorisations,
  DenseEigenvalueAndSVDMethods,
  DenseMatrixFunctions,
  BlockedAndTiledAlgorithms,
  GPUAndDistributedDenseLinearAlgebra
 ]
 STOP_CONDITION = "Stop when storage, structure, operation, algorithm, conditioning, stability, performance and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Linear Algebra Computation"
 RELATED_ONTOLOGIES = [
  "Linear Algebra Computation",
  "Numerical Linear Algebra Ontology 2",
  "Matrix Computation Ontology",
  "Sparse Matrix Ontology 2",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Machine Precision Ontology",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "Dense Matrix -> Linear Algebra Computation for parent semantics",
  "Dense Matrix -> Numerical Linear Algebra for solver and factorisation theory",
  "Dense Matrix -> Matrix Computation for general matrix operations",
  "Dense Matrix -> Sparse Matrix when explicit zero structure should instead be exploited",
  "Dense Matrix -> Numerical Analysis for conditioning and stability",
  "Dense Matrix -> Floating Point Arithmetic for finite-precision effects",
  "Dense Matrix -> HPC for high-performance and distributed dense kernels"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible dense formats, kernels, factorisations or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve dense-versus-sparse distinction.",
  "Preserve mathematical-matrix-versus-memory-layout distinction.",
  "Preserve solve-versus-explicit-inverse distinction.",
  "Preserve scalar/vector-level-versus-blocked computation distinction.",
  "Preserve conditioning-versus-stability distinction.",
  "Preserve local-versus-distributed storage distinction.",
  "Preserve machine-readable dense-matrix semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A dense matrix is a matrix represented and processed by explicitly storing its entries rather than exploiting predominant zero structure."
 STORAGE_SUMMARY = "Row-major, column-major, blocked and distributed layouts organise full matrix entries in memory."
 PRODUCT_SUMMARY = "GEMV and GEMM provide core dense matrix-vector and matrix-matrix kernels."
 FACTORISATION_SUMMARY = "LU, QR, Cholesky, Schur and SVD methods provide structure-aware dense decompositions."
 PERFORMANCE_SUMMARY = "Blocked BLAS-3 algorithms increase data reuse and arithmetic intensity."
 PRECISION_SUMMARY = "Conditioning, pivoting, orthogonality and finite precision determine dense numerical reliability."
 PARALLEL_SUMMARY = "Threaded, GPU and block-cyclic distributed algorithms scale dense computation across modern hardware."
 VALIDATION_SUMMARY = "Dense computations should be checked for dimensions, residuals, conditioning, stability, memory cost, performance and reproducibility."
}

FLOW {
 INPUT
 -> detect_dense_matrix_context
 -> identify_dimensions_structure_precision_target_operation_and_hardware_context
 -> choose_row_major_column_major_blocked_or_distributed_storage
 -> classify_product_solve_factorisation_eigenproblem_SVD_function_or_other_operation
 -> exploit_symmetry_Hermitian_structure_definiteness_triangularity_and_rank
 -> select_structure_appropriate_dense_algorithm
 -> analyse_conditioning_pivoting_orthogonality_roundoff_and_backward_error
 -> choose_blocked_tiled_BLAS_or_accelerator_kernel_if_performance_relevant
 -> if_large_scale_use_threaded_GPU_or_distributed_execution
 -> estimate_flops_memory_traffic_arithmetic_intensity_and_communication
 -> validate_residuals_error_bounds_reference_results_performance_and_reproducibility
 -> route_to_linear_algebra_computation_numerical_linear_algebra_matrix_computation_sparse_matrix_numerical_analysis_floating_point_or_HPC_ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Dense Matrix Ontology defines full matrix representation and computation. It supports square, rectangular, symmetric, Hermitian, positive-definite, orthogonal, triangular, diagonal, banded and block matrices, row-major and column-major storage, matrix addition, scaling, GEMV and GEMM, rank-k updates and triangular solves, trace, determinant, rank and norms, dense linear systems and least squares, Gaussian elimination and pivoting, LU, LDU, Cholesky, LDLT and QR decompositions, Householder and Givens transformations, Gram-Schmidt methods, Schur, Hessenberg and tridiagonal reductions, SVD and eigenvalue methods, matrix inverses, pseudoinverses and functions, conditioning and error analysis, blocking, tiling, cache locality, BLAS and LAPACK, GPU and distributed dense computation, mixed precision, iterative refinement, complexity, verification, benchmarking and reproducibility."
}

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

}

END_FLOW