Dense Data Structure Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Dense Data Structure Ontology within the Kireth Research Semantic Library. Dense data structures explicitly materialise most or all positions in a logical data domain rather than omitting default or zero-valued entries. This ontology supports dense vectors, matrices, tensors and arrays, contiguous and strided layouts, indexing, traversal, block organisation, memory alignment, cache locality, arithmetic kernels, vectorisation, GPU execution, parallel and distributed dense structures, numerical precision, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Dense Data Structure Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Computational Mathematics"
 SPECIALISATION = "Computational Data Structures / Dense Data Structure"
 CANONICAL_PAGE = "https://kirethframeworkold.co.uk/books/semantic-library/ai-core/ontologies/mathematical-ontologies/computational-mathematics-ontologies/computational-data-structures/dense-data-structure-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = DenseDataStructure
 ENTITY_CLASS = ExplicitFullDomainRepresentationFramework
 PRIMARY_CONTEXT = ComputationalDataStructures
 DEFINITION = "A dense data structure explicitly stores values for substantially all positions in its logical domain, typically using contiguous or regularly strided memory."
 SYMBOLIC_FORMS = [
  "storage_size approx total_logical_positions",
  "density approx 1",
  "value(i) -> directly_materialised_entry",
  "offset(index)=base+sum_k index_k*stride_k"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for explicit storage, contiguous and strided layout, indexing, traversal, blocking, locality, dense arithmetic kernels, parallel execution and validation."
}

SCOPE {
 INCLUDE = [
  DenseDataStructure,DenseRepresentation,
  DenseArray,DenseVector,DenseMatrix,DenseTensor,
  FullyMaterialisedStructure,
  ExplicitStorage,
  ContiguousStorage,StridedStorage,
  RowMajorOrder,ColumnMajorOrder,
  COrderRelationship,FortranOrderRelationship,
  Shape,Dimension,Axis,
  Length,RowCount,ColumnCount,
  TensorShape,
  Entry,Element,ScalarEntry,
  Index,MultiIndex,
  Offset,LinearIndex,
  LeadingDimension,Stride,
  BasePointer,MemoryAddress,
  MemoryLayout,Alignment,Padding,
  MemoryBlock,MemoryRegion,
  FlatArrayStorage,
  ArrayOfRowsRelationship,
  StructureOfArraysRelationship,
  ArrayOfStructuresRelationship,
  DenseView,ArrayView,MatrixView,TensorView,
  Slice,Subarray,Subvector,Submatrix,Subtensor,
  MutableDenseStructure,ImmutableDenseStructure,
  StaticDenseStructure,DynamicDenseStructure,
  DenseVector,
  DenseMatrix,
  DenseTensor,
  DenseGraphRepresentationRelationship,
  AdjacencyMatrix,
  LookupTable,
  Bitmap,
  BitMatrixRelationship,
  Table,
  RegularGrid,
  StructuredGridRelationship,
  ImageArrayRelationship,
  VolumeArrayRelationship,
  DenseFeatureMatrixRelationship,
  DenseStateVectorRelationship,
  DenseCovarianceMatrixRelationship,
  Access,ElementAccess,
  RandomAccess,SequentialAccess,
  RowAccess,ColumnAccess,
  SliceAccess,
  Traversal,Iteration,
  Gather,Scatter,
  Update,Assignment,
  InsertRelationship,DeleteRelationship,
  Resize,Reallocation,
  Copy,DeepCopy,
  Fill,Initialize,
  ZeroFill,ConstantFill,
  ElementwiseOperation,
  Addition,Subtraction,
  ScalarMultiplication,
  ElementwiseMultiplication,
  ElementwiseDivisionRelationship,
  Reduction,SumReduction,MeanReduction,
  MinReduction,MaxReduction,
  DotProduct,InnerProduct,
  OuterProduct,
  MatrixVectorMultiplication,
  MatrixMatrixMultiplication,
  TensorContraction,
  DenseKernel,
  BLAS,Level1BLASRelationship,
  Level2BLASRelationship,Level3BLASRelationship,
  GEMV,GEMM,
  ConvolutionRelationship,
  StencilComputation,
  Transpose,Permutation,
  Reshape,Flatten,
  BroadcastingRelationship,
  BlockedRepresentation,
  BlockMatrix,BlockedArray,
  Tiling,LoopTiling,CacheBlocking,
  RegisterBlocking,
  Vectorisation,SIMD,
  VectorProcessing,
  Prefetching,
  StreamingAccess,
  MemoryBandwidth,
  MemoryLatency,
  ArithmeticIntensity,
  ComputeBound,MemoryBound,
  RooflineModel,
  Cache,CacheLine,
  L1Cache,L2Cache,L3Cache,
  CacheLocality,SpatialLocality,TemporalLocality,
  CacheMiss,CacheHit,
  FalseSharingRelationship,
  NUMARelationship,
  MemoryFootprint,
  StorageComplexity,
  TimeComplexity,SpaceComplexity,
  ComputationalComplexity,
  DataType,Precision,
  IntegerType,FloatingPointType,
  ComplexType,BooleanType,
  HalfPrecision,FP16,
  BFloat16,BF16,
  SinglePrecision,FP32,
  DoublePrecision,FP64,
  MixedPrecision,
  FloatingPointArithmetic,
  MachinePrecision,RoundOffError,
  Overflow,Underflow,
  NumericalStability,
  ParallelDenseStructure,
  ParallelArray,
  ParallelVector,
  ParallelMatrix,
  ParallelTensor,
  DistributedDenseStructure,
  DistributedArray,
  DistributedVector,
  DistributedMatrix,
  DistributedTensor,
  PartitionedDenseStructure,
  BlockDistribution,
  CyclicDistributionRelationship,
  BlockCyclicDistribution,
  RowDistribution,ColumnDistribution,
  ReplicatedStructure,
  ShardedStructure,
  GPUDataStructure,
  GPUArray,
  GPUVector,
  GPUMatrix,
  GPUTensor,
  DeviceMemory,
  HostMemory,
  HostDeviceTransfer,
  UnifiedMemoryRelationship,
  TensorCoreRelationship,
  HighPerformanceComputing,
  ParallelComputing,
  DistributedComputing,
  GPUComputing,
  ComputationalMatrix,
  VectorComputation,
  TensorComputation,
  Verification,
  ShapeCheck,BoundsCheck,
  StrideCheck,AlignmentCheck,
  LayoutCheck,
  ReferenceResult,
  Benchmark,
  Reproducibility,
  Provenance,
  DenseFormatVersion,
  LibraryVersion,
  ImplementationVersion
 ]
 EXCLUDE_AS_PRIMARY = [
  SparseRepresentationWhereMostLogicalPositionsAreImplicit,
  CompressedRepresentationWhereStorageDependsPrimarilyOnAbsentValues,
  AbstractArrayTheoryWithoutConcreteStorageSemantics
 ]
 DISAMBIGUATION_RULE = "When substantially all logical positions are explicitly materialised in memory, interpret the context as a dense data structure."
}

CORE_CONCEPTS {
 DenseDataStructure = "Representation explicitly storing substantially all logical positions."
 ContiguousStorage = "Storage in which consecutive logical elements occupy adjacent memory locations."
 StridedStorage = "Storage in which adjacent logical positions are separated by a fixed memory stride."
 MemoryLayout = "Mapping from logical indices to physical memory locations."
 DenseArray = "Explicitly stored array representation."
 DenseMatrix = "Explicitly stored two-dimensional matrix representation."
 DenseTensor = "Explicitly stored multidimensional tensor representation."
 DenseKernel = "Computation operating over dense stored values."
}

RELATIONS {
 DenseDataStructure --is_child_of--> ComputationalDataStructures
 DenseArray --is_type_of--> DenseDataStructure
 DenseVector --is_type_of--> DenseDataStructure
 DenseMatrix --is_type_of--> DenseDataStructure
 DenseTensor --is_type_of--> DenseDataStructure
 DenseDataStructure --uses--> ExplicitStorage
 ContiguousStorage --improves--> SpatialLocality
 StridedStorage --defines--> RegularAddressPattern
 RowMajorOrder --orders--> RowsContiguously
 ColumnMajorOrder --orders--> ColumnsContiguously
 BlockedRepresentation --supports--> CacheReuse
 Vectorisation --uses--> RegularDenseAccess
 GPUDataStructure --uses--> DeviceMemory
 Verification --checks--> DenseRepresentationAndOperations
}

OPERATORS {
 LINEAR_OFFSET(index,strides) := sum_k index_k*strides_k
 ACCESS(D,index) := D[index]
 ASSIGN(D,index,value) := update_materialised_entry(D,index,value)
 FILL(D,value) := assign_value_to_all_positions(D,value)
 REDUCE_SUM(D) := sum_over_all_entries(D)
 DENSITY(total,stored) := stored/total
 MEMORY_BYTES(elements,bytes_per_element) := elements*bytes_per_element
 MATMUL(A,B) := dense_matrix_product(A,B)
}

AXIOMS {
 A1 = "Dense structures explicitly store substantially all logical positions."
 A2 = "Dense storage cost grows approximately with total logical size."
 A3 = "Regular memory layout enables efficient sequential access and vectorisation."
 A4 = "Contiguous and blocked layouts can improve cache locality."
 A5 = "Dense structures are inefficient when most values are unused or zero."
 A6 = "Finite precision can alter dense numerical reductions and arithmetic."
 A7 = "Distributed dense structures require explicit partition and communication semantics."
 A8 = "Dense-data-structure reasoning requires explicit shape, layout, precision, operation and validation semantics."
}

REASONING {
 R1_CONTEXT = identify(shape,total_size,data_type,operations,access_pattern,memory_limit,hardware)
 R2_LAYOUT = choose(row_major,column_major,contiguous,strided,blocked_or_specialised_dense_layout)
 R3_ACCESS = analyse(sequential,row,column,slice,gather_scatter_and_traversal_requirements)
 R4_KERNELS = identify(elementwise,reduction,BLAS,convolution,stencil_or_tensor_workload)
 R5_COMPLEXITY = analyse(storage,arithmetic,memory_traffic_and_bandwidth_cost)
 R6_MEMORY = assess(cache_lines,alignment,padding,tiling,prefetch_and_NUMA_effects)
 R7_NUMERICS = assess(precision,roundoff,overflow,underflow_and_reduction_order)
 R8_SCALE = if_large choose_parallel_distributed_block_cyclic_or_GPU_representation
 R9_VERIFY = check(shape,bounds,strides,layout,reference_outputs_and_precision)
 R10_REPRODUCE = document(layout,data_type,library,hardware_and_version_metadata)
}

CONSTRAINTS {
 C1 = "Dense representation wastes memory when logical data are highly sparse."
 C2 = "Unfavourable stride patterns can reduce cache and memory throughput."
 C3 = "Transpose-like access can be expensive under mismatched storage order."
 C4 = "Large dense structures can exceed memory capacity quickly."
 C5 = "Naive kernels can underuse cache, vector and accelerator hardware."
 C6 = "False sharing can reduce parallel performance."
 C7 = "Mixed precision requires explicit accuracy safeguards."
 C8 = "Distributed dense computation can be communication dominated."
 C9 = "Equivalent arithmetic orders can produce different floating-point results."
 C10 = "Peak bandwidth or FLOPS does not guarantee sustained application performance."
}

SEMANTIC_EQUIVALENCE {
 "DenseRepresentation" <=> "DenseDataStructure"
 "SingleInstructionMultipleData" <=> "SIMD"
 "GeneralMatrixVectorMultiply" <=> "GEMV"
 "GeneralMatrixMultiply" <=> "GEMM"
}

VALIDATION {
 V1 = "Shape and data type are documented."
 V2 = "Memory layout and storage order are documented."
 V3 = "Stride and leading-dimension metadata are validated."
 V4 = "Index bounds are checked."
 V5 = "Memory footprint is consistent with shape and element size."
 V6 = "Reference results are used for representative dense kernels."
 V7 = "Precision settings are documented."
 V8 = "Parallel or distributed partitioning is documented where used."
 V9 = "GPU device placement and transfer semantics are documented where used."
 V10 = "Results are reproducible under documented layout, library, precision and implementation versions."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 DENSE_DATA_STRUCTURE_DEFINITION = 0.99
 MEMORY_LAYOUT_REASONING = 0.99
 CONTIGUOUS_STORAGE_REASONING = 0.99
 DENSE_KERNEL_REASONING = 0.99
 PARALLEL_DENSE_REASONING = 0.98
 GPU_DENSE_REASONING = 0.98
 POLICY = "Reduce confidence when shape, layout, strides, storage order, precision, partitioning or hardware placement are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,DenseDataStructureReasoning,
  DenseArrayReasoning,DenseVectorReasoning,DenseMatrixReasoning,DenseTensorReasoning,
  MemoryLayoutReasoning,ContiguousStorageReasoning,StrideReasoning,
  CacheLocalityReasoning,BlockingReasoning,VectorisationReasoning,
  DenseKernelReasoning,ParallelDenseReasoning,DistributedDenseReasoning,
  GPUDenseReasoning,NumericalStabilityReasoning,
  VerificationReasoning,KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "dense data structure" -> DenseDataStructure
  "dense representation" -> DenseDataStructure
  "SIMD" -> SingleInstructionMultipleData
  "GEMV" -> GeneralMatrixVectorMultiply
  "GEMM" -> GeneralMatrixMultiply
 }
}

EXECUTION_RULES {
 E1 = "If substantially all logical positions are explicitly materialised, activate DenseDataStructureOntology."
 E2 = "Determine shape, data type and access pattern before choosing layout."
 E3 = "Choose row-major, column-major, contiguous, strided or blocked layout according to workload."
 E4 = "Use blocking and vectorisation for repeated dense kernels."
 E5 = "Validate shape, bounds, strides and memory footprint before execution."
 E6 = "Assess precision and reduction-order effects for numerical workloads."
 E7 = "Use partitioned or distributed layouts when a dense structure exceeds local scale."
 E8 = "Use GPU-resident dense structures when accelerator execution is beneficial."
 E9 = "Verify representative outputs against trusted references."
}

RECURSION {
 ENTRY = DenseDataStructure
 EXPAND(DenseDataStructure) -> [
  DenseRepresentation,DenseArray,DenseVector,DenseMatrix,DenseTensor,
  ExplicitStorage,ContiguousStorage,StridedStorage,RowMajorOrder,ColumnMajorOrder,
  Shape,Stride,LeadingDimension,MemoryLayout,Alignment,Padding,
  DenseView,Slice,Subarray,Subvector,Submatrix,Subtensor,
  Access,Traversal,Update,Resize,Fill,ElementwiseOperation,Reduction,
  DotProduct,MatrixVectorMultiplication,MatrixMatrixMultiplication,TensorContraction,
  DenseKernel,BLAS,GEMV,GEMM,StencilComputation,
  BlockedRepresentation,Tiling,CacheBlocking,Vectorisation,SIMD,Prefetching,
  MemoryBandwidth,ArithmeticIntensity,CacheLocality,MemoryFootprint,
  MixedPrecision,FloatingPointArithmetic,NumericalStability,
  ParallelDenseStructure,DistributedDenseStructure,GPUDataStructure,
  Verification,Reproducibility
 ]
 EXPAND(DenseDataStructureFamilies) -> [
  DenseArrayRepresentations,
  DenseVectorRepresentations,
  DenseMatrixRepresentations,
  DenseTensorRepresentations,
  BlockedAndCacheOptimisedDenseStructures,
  ParallelAndDistributedDenseStructures,
  GPUDenseStructures,
  DenseValidationAndReproducibility
 ]
 STOP_CONDITION = "Stop when shape, layout, storage order, operations, memory behaviour, precision and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Data Structures"
 RELATED_ONTOLOGIES = [
  "Computational Data Structures",
  "Computational Matrix Ontology",
  "Vector Computation Ontology",
  "Tensor Computation Ontology",
  "Sparse Data Structure Ontology",
  "Matrix Computation Ontology",
  "Numerical Linear Algebra Ontology 2",
  "High Performance Computing Ontology 2",
  "Parallel Computing Ontology",
  "Distributed Computing Ontology",
  "GPU Computing Ontology",
  "Vector Processing Ontology",
  "Floating Point Arithmetic Ontology",
  "Numerical Stability Ontology 2"
 ]
 ROUTE_RULES = [
  "Dense Data Structure -> Computational Data Structures for parent representation semantics",
  "Dense Data Structure -> Computational Matrix for dense matrix representation",
  "Dense Data Structure -> Vector Computation for dense vector representation",
  "Dense Data Structure -> Tensor Computation for dense tensor representation",
  "Dense Data Structure -> Sparse Data Structure for dense-versus-sparse comparison",
  "Dense Data Structure -> Matrix Computation and Numerical Linear Algebra for dense kernels",
  "Dense Data Structure -> HPC, Parallel, Distributed, GPU and Vector Processing for scalable execution",
  "Dense Data Structure -> Floating Point Arithmetic and Numerical Stability for finite-precision behaviour"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible dense layouts, kernels or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve logical-shape-versus-physical-layout distinction.",
  "Preserve contiguous-versus-strided layout distinction.",
  "Preserve row-major-versus-column-major distinction.",
  "Preserve dense-versus-sparse representation distinction.",
  "Preserve local-versus-distributed storage distinction.",
  "Preserve exact-algebra-versus-floating-point-computation distinction.",
  "Preserve machine-readable dense-data-structure semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A dense data structure explicitly stores substantially all logical values, typically using contiguous or regularly strided memory."
 STORAGE_SUMMARY = "Contiguous, strided, row-major, column-major and blocked layouts support different traversal and kernel patterns."
 PERFORMANCE_SUMMARY = "Cache locality, alignment, blocking, memory bandwidth and vectorisation strongly influence dense computation."
 SCALE_SUMMARY = "Parallel, distributed and GPU dense structures partition or relocate explicit values for large-scale execution."
 VALIDATION_SUMMARY = "Dense structures should be checked for shape, bounds, strides, memory footprint, precision, layout and reference-kernel correctness."
}

FLOW {
 INPUT
 -> detect_dense_data_structure_context
 -> identify_shape_total_size_data_type_operations_access_pattern_memory_and_hardware
 -> choose_row_major_column_major_contiguous_strided_blocked_or_specialised_dense_layout
 -> validate_shape_bounds_strides_and_memory_footprint
 -> execute_access_update_elementwise_reduction_BLAS_stencil_or_tensor_kernels
 -> analyse_storage_arithmetic_memory_traffic_and_bandwidth_cost
 -> optimise_alignment_tiling_prefetching_cache_reuse_vectorisation_and_hardware_mapping
 -> assess_precision_roundoff_overflow_underflow_and_reduction_order
 -> if_large_choose_parallel_distributed_block_cyclic_or_GPU_dense_execution
 -> verify_against_reference_results
 -> document_layout_precision_library_versions_device_mapping_and_provenance
 -> route_to_related_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-COMPUTATIONAL-DATA-STRUCTURES-DENSE-DATA-STRUCTURE-ONTOLOGY-V1"
}

}

END_FLOW