QR Decomposition Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the QR Decomposition Ontology within the Kireth Research Semantic Library. QR decomposition factors a matrix into an orthogonal or unitary matrix and an upper-triangular matrix. This ontology supports Householder, Givens and Gram-Schmidt constructions, least-squares solution, rank-revealing QR, pivoted QR, eigenvalue algorithms, sparse and dense QR, numerical stability, orthogonality preservation, condition analysis, low-rank structure, parallel computation and relationships with matrix decomposition, numerical linear algebra and matrix computation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = QRDecomposition
 ENTITY_CLASS = OrthogonalTriangularFactorisationFramework
 PRIMARY_CONTEXT = MatrixDecomposition
 DEFINITION = "QR decomposition is a matrix factorisation that represents a matrix as the product of an orthogonal or unitary matrix Q and an upper-triangular or upper-trapezoidal matrix R."
 SYMBOLIC_FORMS = [
  "A=Q*R",
  "Q^T*Q=I",
  "Q^*Q=I",
  "A*P=Q*R"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for orthogonal-triangular factorisation, least-squares solution, rank revelation, orthogonalisation, eigenvalue iteration, stable matrix computation and scalable QR algorithms."
}

SCOPE {
 INCLUDE = [
  QRDecomposition,
  QRFactorisation,
  OrthogonalMatrix,
  UnitaryMatrix,
  UpperTriangularMatrix,
  UpperTrapezoidalMatrix,
  QFactor,
  RFactor,
  FullQR,
  ThinQR,
  ReducedQR,
  EconomyQR,
  PivotedQR,
  ColumnPivotedQR,
  RankRevealingQR,
  RRQR,
  HouseholderQR,
  GivensQR,
  GramSchmidtQR,
  ClassicalGramSchmidt,
  ModifiedGramSchmidt,
  Reorthogonalisation,
  HouseholderTransformation,
  HouseholderReflector,
  GivensRotation,
  OrthogonalTransformation,
  UnitaryTransformation,
  Orthogonalisation,
  OrthonormalBasis,
  ColumnSpace,
  Range,
  NullSpace,
  MatrixRank,
  NumericalRank,
  RankDeficiency,
  PermutationMatrix,
  ColumnPermutation,
  LinearSystem,
  LeastSquaresProblem,
  OverdeterminedSystem,
  UnderdeterminedSystem,
  MinimumNormSolution,
  NormalEquations,
  BackSubstitution,
  TriangularSolve,
  QRAlgorithm,
  HessenbergReduction,
  EigenvalueProblem,
  SchurDecomposition,
  IterativeQRAlgorithm,
  ShiftedQRAlgorithm,
  ImplicitQRAlgorithm,
  QRIteration,
  ConditionNumber,
  Conditioning,
  PerturbationAnalysis,
  Residual,
  ForwardError,
  BackwardError,
  OrthogonalityError,
  ReconstructionError,
  NumericalStability,
  BackwardStability,
  LossOfOrthogonality,
  FloatingPointArithmetic,
  MachinePrecision,
  RoundOffError,
  DenseQR,
  SparseQR,
  SymbolicFactorisation,
  NumericFactorisation,
  FillIn,
  Reordering,
  BlockQR,
  BlockedQR,
  TiledQR,
  CommunicationAvoidingQR,
  CAQR,
  TallSkinnyQR,
  TSQR,
  ParallelQR,
  DistributedQR,
  GPUQR,
  MixedPrecisionQR,
  IterativeRefinement,
  RankRevealingFactorisation,
  LowRankApproximation,
  ComputationalComplexity,
  MemoryComplexity,
  CommunicationCost,
  Verification,
  Benchmarking,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  LUDecompositionWithoutOrthogonalFactor,
  CholeskyDecompositionWithoutOrthogonalFactor,
  PureOrthogonalisationWithoutMatrixFactorisationContext,
  AbstractInnerProductTheoryWithoutComputationalQR
 ]
 DISAMBIGUATION_RULE = "When a matrix is factorised into orthogonal or unitary and upper-triangular components, interpret the context as QR decomposition."
}

CORE_CONCEPTS {
 QRDecomposition = "Factorisation A=Q R with Q orthogonal or unitary and R upper triangular or trapezoidal."
 HouseholderQR = "QR factorisation formed by successive Householder reflectors."
 GivensQR = "QR factorisation formed by Givens rotations."
 ModifiedGramSchmidt = "Numerically improved Gram-Schmidt orthogonalisation procedure."
 PivotedQR = "QR factorisation with column permutations, often used for numerical rank revelation."
 RankRevealingQR = "QR variant designed to expose numerical rank and column independence."
 OrthogonalityError = "Deviation of Q^T Q or Q^* Q from the identity matrix."
 LeastSquaresProblem = "Problem of minimising ||A x-b||_2."
}

RELATIONS {
 QRDecomposition --is_child_of--> MatrixDecomposition
 QRDecomposition --produces--> QFactor
 QRDecomposition --produces--> RFactor
 QFactor --is_type_of--> OrthogonalOrUnitaryMatrix
 RFactor --is_type_of--> UpperTriangularOrTrapezoidalMatrix
 HouseholderQR --uses--> HouseholderTransformation
 GivensQR --uses--> GivensRotation
 GramSchmidtQR --uses--> Orthogonalisation
 ModifiedGramSchmidt --improves--> ClassicalGramSchmidtStability
 PivotedQR --uses--> ColumnPermutation
 RankRevealingQR --reveals--> NumericalRank
 QRDecomposition --supports--> LeastSquaresSolution
 QRDecomposition --supports--> OrthonormalBasisConstruction
 QRAlgorithm --uses--> QRDecomposition
 QRAlgorithm --computes--> Eigenvalues
 HessenbergReduction --precedes--> QRAlgorithm
 OrthogonalityError --measures--> QFactorQuality
 ReconstructionError --measures--> FactorisationAccuracy
 CommunicationAvoidingQR --reduces--> CommunicationCost
 TallSkinnyQR --optimises--> TallSkinnyMatrixFactorisation
}

OPERATORS {
 QR_FACTOR(A) := A=Q*R
 PIVOTED_QR(A) := A*P=Q*R
 ORTHOGONALITY(Q) := Q^T*Q=I
 UNITARY_PROPERTY(Q) := Q^*Q=I
 RECONSTRUCTION_ERROR(A,Q,R) := ||A-Q*R||/||A||
 ORTHOGONALITY_ERROR(Q) := ||Q^T*Q-I||
 LEAST_SQUARES_QR(A,b) := solve_Rx=Q^T*b
 RANK_FROM_R(R,tau) := count_i(|R_ii|>tau)
 HOUSEHOLDER(v) := H=I-2*v*v^T/(v^T*v)
 GIVENS(c,s) := G=[[c,s],[-s,c]]
}

AXIOMS {
 A1 = "QR decomposition requires an inner-product structure supporting orthogonality or unitarity."
 A2 = "Householder QR is generally highly stable in finite precision."
 A3 = "Classical Gram-Schmidt can lose orthogonality in finite precision."
 A4 = "Modified Gram-Schmidt improves orthogonality but can still require reorthogonalisation."
 A5 = "Pivoted QR can reveal numerical rank and improve column selection."
 A6 = "QR-based least squares avoids explicitly forming normal equations."
 A7 = "Sparse QR can create fill-in and requires ordering strategies."
 A8 = "QR results require reconstruction, orthogonality, residual and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,structure,sparsity,precision,target_use)
 R2_VARIANT = choose(full,thin,economy,pivoted,rank_revealing_or_sparse_QR)
 R3_METHOD = select(Householder,Givens,modified_Gram_Schmidt_or_blocked_QR)
 R4_FACTOR = compute_Q_and_R_with_selected_transformation_sequence)
 R5_LEAST_SQUARES = if_applicable transform_rhs_and_solve_triangular_system)
 R6_RANK = if_rank_revelation inspect_pivoting_and_R_diagonal_or_singular_structure)
 R7_STABILITY = analyse(orthogonality_loss,conditioning,roundoff_and_backward_error)
 R8_SPARSE = if_sparse choose(ordering,symbolic_factorisation_and_fill_management)
 R9_SCALE = if_large use(blocked,tiled,TSQR,CAQR,parallel,GPU_or_distributed_QR)
 R10_VALIDATION = check(reconstruction,orthogonality,residuals,rank,reference_results,reproducibility)
}

CONSTRAINTS {
 C1 = "Classical Gram-Schmidt may lose substantial orthogonality for ill-conditioned column sets."
 C2 = "Pivoted QR rank estimates depend on threshold, scaling and arithmetic precision."
 C3 = "Explicit construction of Q can be more expensive than storing compact reflector representations."
 C4 = "Sparse QR can create significant fill-in."
 C5 = "Normal equations can worsen conditioning relative to direct QR-based least squares."
 C6 = "Givens rotations are attractive for structured updates but may require many transformations."
 C7 = "Householder methods can be communication-heavy without blocked or communication-avoiding formulations."
 C8 = "Tall-skinny matrices benefit from specialised QR strategies."
 C9 = "A small reconstruction error does not by itself guarantee an accurate least-squares solution for ill-conditioned problems."
 C10 = "Distributed QR performance can be limited by synchronisation and communication."
}

SEMANTIC_EQUIVALENCE {
 "QRDecomposition" <=> "QRFactorisation"
 "ReducedQR" <=> "ThinQR"
 "EconomyQR" <=> "ThinQR"
 "RankRevealingQR" <=> "RRQR"
 "CommunicationAvoidingQR" <=> "CAQR"
 "TallSkinnyQR" <=> "TSQR"
}

VALIDATION {
 V1 = "Matrix dimensions are explicit."
 V2 = "QR variant and construction method are documented."
 V3 = "Permutation conventions are explicit for pivoted QR."
 V4 = "Reconstruction error is checked."
 V5 = "Orthogonality or unitarity error is checked."
 V6 = "Least-squares residuals are checked where relevant."
 V7 = "Numerical-rank threshold is documented."
 V8 = "Sparse fill and ordering are documented where relevant."
 V9 = "Parallel or distributed data layout is documented when applicable."
 V10 = "Results are reproducible under documented arithmetic and execution settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 QR_DECOMPOSITION_DEFINITION = 0.99
 HOUSEHOLDER_REASONING = 0.99
 GIVENS_REASONING = 0.99
 MODIFIED_GRAM_SCHMIDT_REASONING = 0.99
 PIVOTED_QR_REASONING = 0.99
 RANK_REVEALING_REASONING = 0.98
 SPARSE_QR_REASONING = 0.98
 COMMUNICATION_AVOIDING_REASONING = 0.98
 POLICY = "Reduce confidence when QR variant, pivoting, rank threshold, sparsity ordering, orthogonality metric or arithmetic precision are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, QRDecompositionReasoning,
  HouseholderReasoning, GivensReasoning, GramSchmidtReasoning,
  ModifiedGramSchmidtReasoning, PivotedQRReasoning,
  RankRevealingQRReasoning, LeastSquaresReasoning,
  OrthogonalityReasoning, QRAlgorithmReasoning,
  SparseQRReasoning, CommunicationAvoidingQRReasoning,
  TSQRReasoning, StabilityReasoning, KnowledgeGraphConstruction,
  RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "QR decomposition" -> QRDecomposition
  "QR factorisation" -> QRDecomposition
  "QR factorization" -> QRDecomposition
  "RRQR" -> RankRevealingQR
  "CAQR" -> CommunicationAvoidingQR
  "TSQR" -> TallSkinnyQR
  "MGS" -> ModifiedGramSchmidt
 }
}

EXECUTION_RULES {
 E1 = "If a matrix is factorised into orthogonal or unitary Q and upper-triangular R, activate QRDecompositionOntology."
 E2 = "If numerical stability is primary, prefer Householder or another robust orthogonal transformation method."
 E3 = "If incremental zeroing or structured updates are needed, consider Givens rotations."
 E4 = "If constructing an orthonormal basis from columns, use modified Gram-Schmidt with reorthogonalisation when needed."
 E5 = "If numerical rank matters, use pivoted or rank-revealing QR."
 E6 = "If solving least squares, use QR to avoid explicitly forming normal equations."
 E7 = "If the matrix is sparse, apply ordering and symbolic analysis before sparse QR where appropriate."
 E8 = "If the matrix is tall and skinny or distributed, consider TSQR or CAQR."
 E9 = "Any QR result should be validated through reconstruction, orthogonality, residuals, rank and reproducibility."
}

RECURSION {
 ENTRY = QRDecomposition
 EXPAND(QRDecomposition) -> [
  QRFactorisation, OrthogonalMatrix, UnitaryMatrix, UpperTriangularMatrix,
  UpperTrapezoidalMatrix, QFactor, RFactor, FullQR, ThinQR, ReducedQR,
  EconomyQR, PivotedQR, ColumnPivotedQR, RankRevealingQR, HouseholderQR,
  GivensQR, GramSchmidtQR, ClassicalGramSchmidt, ModifiedGramSchmidt,
  Reorthogonalisation, HouseholderTransformation, HouseholderReflector,
  GivensRotation, OrthogonalTransformation, UnitaryTransformation,
  Orthogonalisation, OrthonormalBasis, ColumnSpace, Range, NullSpace,
  MatrixRank, NumericalRank, RankDeficiency, PermutationMatrix,
  ColumnPermutation, LinearSystem, LeastSquaresProblem,
  OverdeterminedSystem, UnderdeterminedSystem, MinimumNormSolution,
  NormalEquations, BackSubstitution, TriangularSolve, QRAlgorithm,
  HessenbergReduction, EigenvalueProblem, SchurDecomposition,
  IterativeQRAlgorithm, ShiftedQRAlgorithm, ImplicitQRAlgorithm,
  ConditionNumber, Conditioning, PerturbationAnalysis, Residual,
  ForwardError, BackwardError, OrthogonalityError, ReconstructionError,
  NumericalStability, BackwardStability, LossOfOrthogonality,
  FloatingPointArithmetic, MachinePrecision, RoundOffError, DenseQR,
  SparseQR, SymbolicFactorisation, NumericFactorisation, FillIn,
  Reordering, BlockQR, BlockedQR, TiledQR, CommunicationAvoidingQR,
  TallSkinnyQR, ParallelQR, DistributedQR, GPUQR, MixedPrecisionQR,
  IterativeRefinement, RankRevealingFactorisation,
  LowRankApproximation, ComputationalComplexity, MemoryComplexity,
  CommunicationCost, Verification, Benchmarking, Reproducibility
 ]
 EXPAND(QRFamilies) -> [
  HouseholderQR,
  GivensQR,
  GramSchmidtQR,
  PivotedAndRankRevealingQR,
  SparseQR,
  BlockedAndTiledQR,
  CommunicationAvoidingAndDistributedQR
 ]
 STOP_CONDITION = "Stop when QR variant, construction method, orthogonality, pivoting, rank, stability, 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",
  "Numerical Analysis Ontology 2",
  "Numerical Stability Ontology 2",
  "Round-Off Error Ontology",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "QR Decomposition -> Matrix Decomposition for parent factorisation semantics",
  "QR Decomposition -> Numerical Linear Algebra for least squares and stability theory",
  "QR Decomposition -> Matrix Computation for general matrix operations",
  "QR Decomposition -> Sparse Matrix for sparse QR and fill management",
  "QR Decomposition -> Dense Matrix for blocked dense QR",
  "QR Decomposition -> LU Decomposition for alternative direct factorisation comparison",
  "QR Decomposition -> Numerical Analysis for conditioning and orthogonality error",
  "QR Decomposition -> Numerical Stability for loss-of-orthogonality analysis",
  "QR Decomposition -> HPC for TSQR, CAQR, GPU and distributed QR"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible QR variants, orthogonalisation methods or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve orthogonal-factor-versus-triangular-factor distinction.",
  "Preserve full-versus-thin QR distinction.",
  "Preserve pivoted-versus-unpivoted QR distinction.",
  "Preserve exact-rank-versus-numerical-rank distinction.",
  "Preserve reconstruction-error-versus-orthogonality-error distinction.",
  "Preserve dense-versus-sparse QR distinction.",
  "Preserve explicit-Q-versus-compact-transformation distinction.",
  "Preserve machine-readable QR-decomposition semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "QR decomposition factors a matrix into an orthogonal or unitary factor Q and an upper-triangular or trapezoidal factor R."
 HOUSEHOLDER_SUMMARY = "Householder reflectors provide a robust and widely used route to stable QR factorisation."
 GIVENS_SUMMARY = "Givens rotations selectively annihilate entries and support updates and structured computations."
 GRAM_SCHMIDT_SUMMARY = "Modified Gram-Schmidt improves numerical orthogonality relative to the classical form."
 LEAST_SQUARES_SUMMARY = "QR solves least-squares problems without explicitly squaring the condition number through normal equations."
 RANK_SUMMARY = "Pivoted and rank-revealing QR expose numerical rank and column dependence."
 PARALLEL_SUMMARY = "Blocked, tiled, TSQR and communication-avoiding QR reduce data movement on modern hardware."
 VALIDATION_SUMMARY = "QR results should be checked for reconstruction, orthogonality, residuals, numerical rank, stability and reproducibility."
}

FLOW {
 INPUT
 -> detect_QR_decomposition_context
 -> identify_matrix_shape_structure_sparsity_precision_and_target_use
 -> choose_full_thin_economy_pivoted_rank_revealing_or_sparse_QR
 -> select_Householder_Givens_modified_Gram_Schmidt_or_blocked_method
 -> compute_Q_and_R_or_compact_transformation_representation
 -> if_least_squares_transform_rhs_and_solve_R_system
 -> if_rank_revealing_apply_column_pivoting_and_rank_threshold
 -> analyse_orthogonality_conditioning_roundoff_and_backward_error
 -> if_sparse_apply_ordering_symbolic_analysis_and_fill_management
 -> if_large_scale_use_blocked_tiled_TSQR_CAQR_parallel_GPU_or_distributed_QR
 -> validate_reconstruction_orthogonality_residuals_rank_reference_results_and_reproducibility
 -> route_to_matrix_decomposition_numerical_linear_algebra_matrix_computation_sparse_dense_LU_analysis_stability_roundoff_or_HPC_ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The QR Decomposition Ontology defines orthogonal-triangular matrix factorisation. It supports full, thin, reduced and economy QR, pivoted and column-pivoted QR, rank-revealing QR, Householder, Givens and Gram-Schmidt constructions, modified Gram-Schmidt and reorthogonalisation, orthonormal bases and column-space structure, least-squares and minimum-norm problems, triangular solves, QR eigenvalue algorithms, shifted and implicit QR iteration, conditioning, residual, forward and backward error, orthogonality and reconstruction error, dense and sparse QR, symbolic and numeric factorisation, fill-in and reordering, blocked and tiled QR, communication-avoiding QR, TSQR, parallel, distributed, GPU and mixed-precision QR, iterative refinement, complexity, verification, benchmarking and reproducibility."
}

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

}

END_FLOW