Cholesky Decomposition Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Cholesky Decomposition Ontology within the Kireth Research Semantic Library. Cholesky decomposition factors a symmetric or Hermitian positive-definite matrix into triangular factors and supports stable linear solves, determinant computation, sparse factorisation, preconditioning and scalable computation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = CholeskyDecomposition
 ENTITY_CLASS = PositiveDefiniteTriangularFactorisationFramework
 PRIMARY_CONTEXT = MatrixDecomposition
 DEFINITION = "Cholesky decomposition is a factorisation of a symmetric or Hermitian positive-definite matrix into the product of a triangular matrix and its transpose or conjugate transpose."
 SYMBOLIC_FORMS = ["A=L*L^T","A=L*L^*","A=R^T*R","A=R^*R"]
 SEMANTIC_ROLE = "Provides machine-readable semantics for positive-definite triangular factorisation, efficient linear-system solution, sparse factorisation, incomplete preconditioning, numerical stability and scalable computation."
}

SCOPE {
 INCLUDE = [
  CholeskyDecomposition, CholeskyFactorisation, LowerCholesky, UpperCholesky,
  LowerTriangularMatrix, UpperTriangularMatrix, SymmetricMatrix, HermitianMatrix,
  PositiveDefiniteMatrix, PositiveSemidefiniteMatrix, PositiveDefiniteness,
  SylvesterCriterion, PrincipalMinor, Pivot, Breakdown, NonPositivePivot,
  LinearSystem, SymmetricPositiveDefiniteSystem, SPDSystem, ForwardSubstitution,
  BackSubstitution, MultipleRightHandSides, Determinant, LogDeterminant,
  CovarianceMatrix, GramMatrix, NormalEquations, LeastSquaresProblem,
  DenseCholesky, SparseCholesky, PivotedCholesky, IncompleteCholesky, IC, IC0,
  DropTolerance, Preconditioner, CholeskyUpdate, CholeskyDowndate, RankOneUpdate,
  RankOneDowndate, BlockCholesky, BlockedCholesky, TiledCholesky,
  SupernodalCholesky, MultifrontalCholesky, EliminationTree,
  SymbolicFactorisation, NumericFactorisation, FillIn, Reordering,
  FillReducingOrdering, ApproximateMinimumDegree, AMD, NestedDissection,
  ConditionNumber, Conditioning, Residual, ReconstructionError, ForwardError,
  BackwardError, NumericalStability, BackwardStability, RoundOffError,
  FloatingPointArithmetic, MachinePrecision, Scaling, Equilibration,
  MixedPrecisionCholesky, IterativeRefinement, ParallelCholesky,
  DistributedCholesky, GPUCholesky, CommunicationAvoidingCholesky,
  ComputationalComplexity, MemoryComplexity, CommunicationCost,
  Verification, Benchmarking, Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [LUDecompositionForGeneralMatrices,LDLTForIndefiniteMatrices,QRDecompositionWithoutPositiveDefiniteStructure]
 DISAMBIGUATION_RULE = "When a symmetric or Hermitian positive-definite matrix is factorised into triangular factors related by transpose or conjugate transpose, interpret the context as Cholesky decomposition."
}

CORE_CONCEPTS {
 CholeskyDecomposition = "Triangular factorisation of a symmetric or Hermitian positive-definite matrix."
 PositiveDefiniteMatrix = "Matrix satisfying x^T A x>0 or x^* A x>0 for every nonzero vector x."
 CholeskyFactor = "Triangular factor whose product with its transpose or conjugate transpose reconstructs the matrix."
 SparseCholesky = "Cholesky factorisation exploiting sparse positive-definite matrix structure."
 IncompleteCholesky = "Approximate Cholesky factorisation commonly used as a preconditioner."
 PivotedCholesky = "Pivoted Cholesky-like factorisation useful in semidefinite or low-rank contexts."
}

RELATIONS {
 CholeskyDecomposition --is_child_of--> MatrixDecomposition
 CholeskyDecomposition --requires--> PositiveDefiniteMatrix
 CholeskyDecomposition --produces--> CholeskyFactor
 CholeskyDecomposition --supports--> SPDLinearSystemSolution
 ForwardSubstitution --solves--> LowerTriangularSystem
 BackSubstitution --solves--> UpperTriangularSystem
 CholeskyDecomposition --supports--> LogDeterminantComputation
 SparseCholesky --can_create--> FillIn
 Reordering --can_reduce--> FillIn
 EliminationTree --represents--> SparseFactorisationDependencies
 IncompleteCholesky --supports--> Preconditioning
 IterativeRefinement --can_improve--> CholeskySolveAccuracy
}

OPERATORS {
 LOWER_CHOLESKY(A) := A=L*L^T_or_L*L^*
 UPPER_CHOLESKY(A) := A=R^T*R_or_R^*R
 FORWARD_SOLVE(L,b) := solve_Ly=b
 BACK_SOLVE(L,y) := solve_L^T*x=y_or_L^*x=y
 DETERMINANT_FROM_CHOLESKY(L) := det(A)=(prod_i L_ii)^2
 LOGDET_FROM_CHOLESKY(L) := log(det(A))=2*sum_i log(L_ii)
 RECONSTRUCTION_ERROR(A,L) := ||A-L*L^T||/||A||
 RELATIVE_RESIDUAL(A,x,b) := ||b-A*x||/(||A||*||x||+||b||)
}


AXIOMS {
 A1 = "Standard Cholesky decomposition requires symmetric or Hermitian positive-definite structure."
 A2 = "For a positive-definite matrix, standard Cholesky factors with positive diagonal entries are unique."
 A3 = "Cholesky exploits positive-definite structure more efficiently than general dense LU."
 A4 = "General pivoting is unnecessary for standard positive-definite Cholesky."
 A5 = "A non-positive pivot indicates violated assumptions or numerical difficulty."
 A6 = "Sparse Cholesky can generate fill-in."
 A7 = "Incomplete Cholesky intentionally sacrifices exact reconstruction to reduce cost."
 A8 = "Cholesky results require structural, reconstruction, residual, stability and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,symmetry_or_Hermitian_structure,definiteness,sparsity,precision,target_use)
 R2_VALIDATE_STRUCTURE = verify(square_and_symmetric_or_Hermitian_structure)
 R3_DEFINITENESS = establish_or_test_positive_definiteness
 R4_FACTOR = compute_lower_or_upper_Cholesky_factor
 R5_SOLVE = if_rhs_present apply_forward_and_back_substitution
 R6_STABILITY = analyse(conditioning,roundoff,reconstruction_and_backward_error)
 R7_SPARSE = if_sparse choose(ordering,symbolic_factorisation_and_fill_management)
 R8_VARIANT = if_semidefinite_low_rank_or_preconditioning choose(pivoted_or_incomplete_Cholesky)
 R9_SCALE = if_large use(blocked,tiled,parallel,GPU_or_distributed_Cholesky)
 R10_VALIDATION = check(structure,reconstruction,residuals,positive_diagonal,reference_results,reproducibility)
}

CONSTRAINTS {
 C1 = "Standard Cholesky fails when the matrix is not positive definite."
 C2 = "Positive semidefinite matrices can require pivoted or rank-revealing treatment."
 C3 = "Normal equations can square the condition number in least-squares problems."
 C4 = "A small residual does not guarantee small forward error for an ill-conditioned system."
 C5 = "Sparse Cholesky memory can be dominated by fill-in."
 C6 = "Incomplete Cholesky can break down without suitable shifts, dropping or modification."
 C7 = "Rank-one downdates can destroy positive definiteness."
 C8 = "Log determinants should avoid explicitly forming extremely large or small determinants."
 C9 = "Mixed-precision Cholesky requires sufficiently accurate residual correction."
 C10 = "Distributed Cholesky can become communication-bound."
}

SEMANTIC_EQUIVALENCE {
 "CholeskyDecomposition" <=> "CholeskyFactorisation"
 "SPDSystem" <=> "SymmetricPositiveDefiniteSystem"
 "IncompleteCholesky" <=> "IC"
 "ApproximateMinimumDegree" <=> "AMD"
 "LowerCholesky" <=> "LLTDecompositionInRealSPDContext"
}

VALIDATION {
 V1 = "Matrix is square."
 V2 = "Symmetry or Hermitian structure is verified."
 V3 = "Positive definiteness is established or computationally checked."
 V4 = "Computed diagonal pivots are positive under standard assumptions."
 V5 = "Reconstruction error is checked."
 V6 = "Linear-system residuals are checked."
 V7 = "Conditioning is assessed for sensitive systems."
 V8 = "Sparse ordering and fill are documented where relevant."
 V9 = "Incomplete or pivoted variants report approximation or rank criteria."
 V10 = "Results are reproducible under documented arithmetic and execution settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 CHOLESKY_DECOMPOSITION_DEFINITION = 0.99
 POSITIVE_DEFINITE_REASONING = 0.99
 DENSE_CHOLESKY_REASONING = 0.99
 SPARSE_CHOLESKY_REASONING = 0.98
 PIVOTED_CHOLESKY_REASONING = 0.98
 INCOMPLETE_CHOLESKY_REASONING = 0.98
 UPDATE_DOWNDATE_REASONING = 0.98
 POLICY = "Reduce confidence when symmetry, positive definiteness, sparsity ordering, incomplete-factor tolerance or arithmetic precision are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [SemanticSearch,OntologyGrounding,CholeskyDecompositionReasoning,PositiveDefiniteMatrixReasoning,TriangularFactorReasoning,SPDLinearSystemReasoning,DeterminantReasoning,LogDeterminantReasoning,SparseCholeskyReasoning,FillInReasoning,OrderingReasoning,PivotedCholeskyReasoning,IncompleteCholeskyReasoning,PreconditioningReasoning,CholeskyUpdateReasoning,NumericalStabilityReasoning,MixedPrecisionReasoning,ParallelCholeskyReasoning,KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference]
 NORMALISE {
  "Cholesky decomposition" -> CholeskyDecomposition
  "Cholesky factorisation" -> CholeskyDecomposition
  "Cholesky factorization" -> CholeskyDecomposition
  "SPD" -> PositiveDefiniteMatrix
  "IC" -> IncompleteCholesky
  "AMD" -> ApproximateMinimumDegree
 }
}

EXECUTION_RULES {
 E1 = "If a symmetric or Hermitian positive-definite matrix is factorised into triangular transpose-related factors, activate CholeskyDecompositionOntology."
 E2 = "Verify positive-definite structure before relying on standard Cholesky semantics."
 E3 = "If solving A x=b, factor once and reuse triangular solves."
 E4 = "If determinant or log determinant is required, use Cholesky diagonal entries."
 E5 = "If sparse, apply fill-reducing ordering and symbolic analysis."
 E6 = "If a preconditioner is needed, consider incomplete Cholesky."
 E7 = "If semidefinite or approximately low rank, consider pivoted Cholesky."
 E8 = "For rank-one modifications, use update or downdate with definiteness checks."
 E9 = "Validate structure, reconstruction, residuals, conditioning and reproducibility."
}


RECURSION {
 ENTRY = CholeskyDecomposition
 EXPAND(CholeskyDecomposition) -> [
  CholeskyFactorisation, LowerCholesky, UpperCholesky, LowerTriangularMatrix,
  UpperTriangularMatrix, SymmetricMatrix, HermitianMatrix,
  PositiveDefiniteMatrix, PositiveSemidefiniteMatrix, PositiveDefiniteness,
  SylvesterCriterion, Pivot, Breakdown, NonPositivePivot, LinearSystem,
  SymmetricPositiveDefiniteSystem, ForwardSubstitution, BackSubstitution,
  MultipleRightHandSides, Determinant, LogDeterminant, CovarianceMatrix,
  GramMatrix, NormalEquations, LeastSquaresProblem, DenseCholesky,
  SparseCholesky, PivotedCholesky, IncompleteCholesky, IC0, DropTolerance,
  Preconditioner, CholeskyUpdate, CholeskyDowndate, RankOneUpdate,
  RankOneDowndate, BlockedCholesky, TiledCholesky, SupernodalCholesky,
  MultifrontalCholesky, EliminationTree, SymbolicFactorisation,
  NumericFactorisation, FillIn, Reordering, ApproximateMinimumDegree,
  NestedDissection, ConditionNumber, Conditioning, Residual,
  ReconstructionError, ForwardError, BackwardError, NumericalStability,
  RoundOffError, FloatingPointArithmetic, MachinePrecision, Scaling,
  MixedPrecisionCholesky, IterativeRefinement, ParallelCholesky,
  DistributedCholesky, GPUCholesky, ComputationalComplexity,
  MemoryComplexity, CommunicationCost, Verification, Benchmarking,
  Reproducibility
 ]
 STOP_CONDITION = "Stop when definiteness, factor form, solve semantics, stability, sparsity, variant choice, cost and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Matrix Decomposition Ontology 2"
 RELATED_ONTOLOGIES = ["Matrix Decomposition Ontology 2","Numerical Linear Algebra Ontology 2","Matrix Computation Ontology","Sparse Matrix Ontology 2","Dense Matrix Ontology","LU Decomposition Ontology","QR Decomposition Ontology","Numerical Analysis Ontology 2","Numerical Stability Ontology 2","High Performance Computing Ontologies"]
 ROUTE_RULES = [
  "Cholesky Decomposition -> Matrix Decomposition for parent factorisation semantics",
  "Cholesky Decomposition -> Numerical Linear Algebra for SPD solve and stability theory",
  "Cholesky Decomposition -> Sparse Matrix for sparse fill and ordering",
  "Cholesky Decomposition -> Dense Matrix for blocked dense Cholesky",
  "Cholesky Decomposition -> LU Decomposition for general-system comparison",
  "Cholesky Decomposition -> QR Decomposition for least-squares alternatives",
  "Cholesky Decomposition -> Numerical Analysis for conditioning and error",
  "Cholesky Decomposition -> HPC for parallel and GPU Cholesky"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible Cholesky variants, sparse methods or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = ["Preserve positive-definite-versus-indefinite distinction.","Preserve lower-versus-upper Cholesky convention.","Preserve exact-versus-incomplete Cholesky distinction.","Preserve dense-versus-sparse Cholesky distinction.","Preserve factorisation-versus-update/downdate distinction.","Preserve determinant-versus-log-determinant distinction.","Preserve machine-readable Cholesky-decomposition semantics."]
}

OUTPUT {
 CANONICAL_DEFINITION = "Cholesky decomposition factors a symmetric or Hermitian positive-definite matrix into triangular factors related by transpose or conjugate transpose."
 STRUCTURE_SUMMARY = "Standard Cholesky exploits positive-definite structure without general pivoting."
 SOLVE_SUMMARY = "Positive-definite linear systems are solved through forward and back substitution."
 DETERMINANT_SUMMARY = "Determinants and log determinants follow directly from Cholesky diagonal entries."
 SPARSE_SUMMARY = "Sparse Cholesky requires ordering, elimination-tree analysis and fill management."
 INCOMPLETE_SUMMARY = "Incomplete Cholesky approximates the factor and is widely used for preconditioning."
 VALIDATION_SUMMARY = "Cholesky results should be checked for structure, reconstruction, residuals, conditioning, fill and reproducibility."
}

FLOW {
 INPUT
 -> detect_Cholesky_decomposition_context
 -> identify_matrix_shape_symmetry_definiteness_sparsity_precision_and_target_use
 -> verify_square_symmetric_or_Hermitian_positive_definite_structure
 -> choose_lower_or_upper_Cholesky_variant
 -> compute_triangular_factor
 -> if_rhs_present_apply_forward_and_back_substitution
 -> analyse_conditioning_roundoff_reconstruction_and_backward_error
 -> if_sparse_apply_ordering_symbolic_factorisation_and_fill_management
 -> if_needed_choose_pivoted_or_incomplete_Cholesky
 -> if_large_scale_use_blocked_parallel_GPU_or_distributed_Cholesky
 -> validate_reconstruction_residuals_positive_diagonal_reference_results_and_reproducibility
 -> route_to_related_matrix_and_numerical_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Cholesky Decomposition Ontology defines positive-definite triangular matrix factorisation. It supports lower and upper Cholesky forms, symmetric and Hermitian positive-definite matrices, definiteness tests, triangular solves, repeated right-hand sides, determinant and log-determinant computation, covariance and Gram matrices, dense and sparse Cholesky, pivoted and incomplete Cholesky, preconditioning, rank-one updates and downdates, blocked, tiled, supernodal and multifrontal methods, elimination trees, symbolic and numeric factorisation, fill-in and ordering, conditioning, residual and reconstruction error, numerical stability, mixed precision, iterative refinement, parallel, distributed and GPU Cholesky, complexity, verification, benchmarking and reproducibility."
}

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

}

END_FLOW