Linear Algebra Computation

AI INTERPRETATION NOTE
This Flow Algebra defines the Linear Algebra Computation layer within the Kireth Research Semantic Library. Linear algebra computation studies the numerical and algorithmic solution of matrix and vector problems, including linear systems, matrix factorisation, eigenvalue problems, singular-value decomposition, sparse matrices, iterative solvers, conditioning, stability, preconditioning, low-rank approximation and scalable matrix computation. This parent ontology connects numerical linear algebra, computational mathematics, numerical methods, optimisation, scientific computing and high-performance computing.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = LinearAlgebraComputation
 ENTITY_CLASS = ComputationalLinearAlgebraFramework
 PRIMARY_CONTEXT = ComputationalMathematicsOntologies
 DEFINITION = "Linear algebra computation is the algorithmic and numerical study of matrix and vector operations, linear systems, decompositions, eigenproblems and related computational structures."
 SYMBOLIC_FORMS = [
  "A x=b",
  "A=P L U",
  "A=Q R",
  "A=U Sigma V^T"
 ]
 SEMANTIC_ROLE = "Provides the parent semantic framework for matrix computation, linear-system solving, matrix factorisation, eigenvalue analysis, singular-value decomposition, sparse computation, iterative methods, conditioning, stability and scalable numerical linear algebra."
}

SCOPE {
 INCLUDE = [
  LinearAlgebraComputation,
  ComputationalLinearAlgebra,
  NumericalLinearAlgebra,
  MatrixComputation,
  VectorComputation,
  Matrix,
  Vector,
  Scalar,
  Tensor,
  DenseMatrix,
  SparseMatrix,
  StructuredMatrix,
  SymmetricMatrix,
  HermitianMatrix,
  PositiveDefiniteMatrix,
  PositiveSemidefiniteMatrix,
  OrthogonalMatrix,
  UnitaryMatrix,
  TriangularMatrix,
  DiagonalMatrix,
  BandedMatrix,
  BlockMatrix,
  ToeplitzMatrix,
  LinearSystem,
  OverdeterminedSystem,
  UnderdeterminedSystem,
  LeastSquaresProblem,
  MatrixEquation,
  MatrixVectorProduct,
  MatrixMatrixProduct,
  InnerProduct,
  OuterProduct,
  Norm,
  VectorNorm,
  MatrixNorm,
  FrobeniusNorm,
  SpectralNorm,
  Rank,
  NullSpace,
  ColumnSpace,
  RowSpace,
  Range,
  Kernel,
  Basis,
  Dimension,
  DirectSolver,
  GaussianElimination,
  Pivoting,
  PartialPivoting,
  CompletePivoting,
  ForwardSubstitution,
  BackSubstitution,
  LUDecomposition,
  LDUDecomposition,
  CholeskyDecomposition,
  QRDecomposition,
  HouseholderTransformation,
  GivensRotation,
  GramSchmidtProcess,
  ModifiedGramSchmidt,
  MatrixDecomposition,
  SingularValueDecomposition,
  SVD,
  TruncatedSVD,
  Eigenvalue,
  Eigenvector,
  EigenvalueProblem,
  GeneralisedEigenvalueProblem,
  SchurDecomposition,
  HessenbergReduction,
  PowerMethod,
  InverseIteration,
  RayleighQuotientIteration,
  QRAlgorithm,
  LanczosMethod,
  ArnoldiMethod,
  KrylovSubspace,
  IterativeSolver,
  JacobiMethod,
  GaussSeidelMethod,
  SuccessiveOverRelaxation,
  SOR,
  ConjugateGradientMethod,
  MINRES,
  GMRES,
  BiCGSTAB,
  Preconditioner,
  DiagonalPreconditioner,
  IncompleteLU,
  ILU,
  IncompleteCholesky,
  Multigrid,
  ConditionNumber,
  Conditioning,
  PerturbationAnalysis,
  Sensitivity,
  Residual,
  ForwardError,
  BackwardError,
  NumericalStability,
  BackwardStability,
  RoundOffError,
  FloatingPointArithmetic,
  MachinePrecision,
  Convergence,
  ConvergenceRate,
  SpectralRadius,
  SparseStorage,
  CSR,
  CSC,
  CoordinateFormat,
  FillIn,
  Reordering,
  PermutationMatrix,
  LowRankApproximation,
  RankRevealingFactorisation,
  RandomisedLinearAlgebra,
  RandomisedSVD,
  MatrixFunction,
  MatrixExponential,
  MatrixSquareRoot,
  Pseudoinverse,
  MoorePenrosePseudoinverse,
  KroneckerProduct,
  TensorProduct,
  ParallelLinearAlgebra,
  DistributedMatrix,
  GPUComputing,
  BLAS,
  LAPACK,
  ScaLAPACK,
  ComputationalComplexity,
  Verification,
  Benchmarking,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  AbstractLinearAlgebraWithoutComputationalMethod,
  TensorComputationWithoutMatrixVectorContext,
  PureSoftwareImplementationWithoutLinearAlgebraSemantics,
  StatisticalMatrixUseWithoutComputationalLinearAlgebraReasoning
 ]
 DISAMBIGUATION_RULE = "When matrices, vectors or linear transformations are manipulated primarily through numerical algorithms and computational procedures, interpret the context as linear algebra computation."
}

CORE_CONCEPTS {
 LinearAlgebraComputation = "Algorithmic and numerical computation with matrices, vectors and linear transformations."
 LinearSystem = "System of linear equations represented as A x=b."
 MatrixDecomposition = "Factorisation of a matrix into structured component matrices."
 NumericalLinearAlgebra = "Study of numerical methods for matrix and vector problems."
 SparseMatrix = "Matrix containing predominantly zero entries and represented to exploit sparsity."
 EigenvalueProblem = "Problem of finding scalar-vector pairs satisfying A v=lambda v."
 SingularValueDecomposition = "Factorisation A=U Sigma V^T revealing rank, conditioning and low-rank structure."
 Preconditioner = "Transformation designed to improve iterative-solver convergence."
 ConditionNumber = "Measure of sensitivity of a linear-algebra problem to perturbations."
}

RELATIONS {
 LinearAlgebraComputation --is_child_of--> ComputationalMathematicsOntologies
 LinearAlgebraComputation --uses--> Matrix
 LinearAlgebraComputation --uses--> Vector
 LinearSystem --is_represented_by--> MatrixEquation
 GaussianElimination --solves--> LinearSystem
 Pivoting --improves--> GaussianEliminationStability
 LUDecomposition --factorises--> Matrix
 CholeskyDecomposition --factorises--> SymmetricPositiveDefiniteMatrix
 QRDecomposition --factorises--> Matrix
 SingularValueDecomposition --factorises--> Matrix
 TruncatedSVD --produces--> LowRankApproximation
 EigenvalueProblem --uses--> Matrix
 KrylovSubspace --supports--> IterativeSolver
 ConjugateGradientMethod --solves--> SymmetricPositiveDefiniteSystem
 GMRES --solves--> GeneralNonsymmetricSystem
 Preconditioner --improves--> IterativeConvergence
 ConditionNumber --quantifies--> ProblemSensitivity
 Residual --measures--> EquationMismatch
 BackwardError --measures--> NearbyProblemPerturbation
 SparseStorage --reduces--> MemoryCost
 Reordering --can_reduce--> FillIn
 ParallelLinearAlgebra --accelerates--> MatrixComputation
}

OPERATORS {
 LINEAR_SYSTEM(A,x,b) := A*x=b
 RESIDUAL(A,x,b) := r=b-A*x
 CONDITION_NUMBER(A) := kappa(A)=||A||*||A^(-1)||
 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
 EIGENPAIR(A,v,lambda) := A*v=lambda*v
 LEAST_SQUARES(A,x,b) := x_hat=argmin_x ||A*x-b||_2
 PSEUDOINVERSE_SOLUTION(A,b) := x=A^+*b
 POWER_ITERATION(A,x) := x_next=A*x/||A*x||
 KRYLOV_SPACE(A,r,m) := span{r,A*r,...,A^(m-1)*r}
}

AXIOMS {
 A1 = "Computational linear algebra requires explicit matrix, vector and arithmetic representations."
 A2 = "Matrix structure should be exploited whenever it materially improves accuracy or efficiency."
 A3 = "Conditioning belongs to the mathematical problem, while numerical stability belongs to the algorithm."
 A4 = "A small residual does not necessarily imply a small forward error for ill-conditioned systems."
 A5 = "Sparse structure should be preserved when feasible in large-scale problems."
 A6 = "Iterative convergence depends on spectral properties, conditioning and preconditioning."
 A7 = "Orthogonal transformations generally provide favourable numerical stability."
 A8 = "Computational linear-algebra results require error, convergence and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,structure,sparsity,problem_type,accuracy_goal)
 R2_CLASS = classify(linear_system,least_squares,eigenproblem,SVD,matrix_function_or_other)
 R3_STRUCTURE = detect(symmetry,positive_definiteness,sparsity,bandedness,rank_structure)
 R4_METHOD = choose(direct,iterative,factorisation,Krylov,randomised_or_low_rank_method)
 R5_CONDITIONING = analyse(condition_number,scaling,sensitivity)
 R6_STABILITY = analyse(pivoting,orthogonality,roundoff_and_backward_error)
 R7_ITERATIVE = if_iterative analyse(residual,spectral_radius,preconditioner,stopping_rule)
 R8_SPARSE = if_sparse choose(storage,reordering_and_fill_reduction)
 R9_SCALE = if_large analyse(memory,parallelism,communication_and_complexity)
 R10_VALIDATION = compare(residual,error_bounds,reference_solution,convergence_and_reproducibility)
}

CONSTRAINTS {
 C1 = "Explicit matrix inversion is often unnecessary and less stable than solving the associated linear system."
 C2 = "Normal equations can square the condition number in least-squares problems."
 C3 = "Cholesky decomposition requires appropriate positive-definite structure."
 C4 = "Conjugate gradients require symmetric positive-definite structure in its standard form."
 C5 = "Sparse direct factorisation can create substantial fill-in."
 C6 = "Eigenvalues of non-normal matrices can be highly sensitive to perturbations."
 C7 = "Classical Gram-Schmidt can lose orthogonality in finite precision."
 C8 = "Iterative stopping criteria must be interpreted relative to conditioning and scale."
 C9 = "Low-rank approximations depend on singular-value decay."
 C10 = "Parallel speedup can be limited by communication, synchronisation and memory bandwidth."
}

SEMANTIC_EQUIVALENCE {
 "LinearAlgebraComputation" <=> "ComputationalLinearAlgebra"
 "NumericalLinearAlgebra" <=> "ComputationalNumericalLinearAlgebra"
 "SingularValueDecomposition" <=> "SVD"
 "SuccessiveOverRelaxation" <=> "SOR"
 "IncompleteLU" <=> "ILU"
 "MoorePenrosePseudoinverse" <=> "Pseudoinverse"
}

VALIDATION {
 V1 = "Matrix dimensions and structure are explicit."
 V2 = "Sparsity and storage representation are documented where relevant."
 V3 = "Conditioning is assessed for sensitive problems."
 V4 = "Residuals and solution errors are distinguished."
 V5 = "Factorisation assumptions are verified."
 V6 = "Iterative solver convergence and stopping criteria are documented."
 V7 = "Preconditioner behaviour is assessed."
 V8 = "Sparse fill and memory costs are considered."
 V9 = "Reference or benchmark solutions are used where feasible."
 V10 = "Results are reproducible under documented arithmetic and solver settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 LINEAR_ALGEBRA_COMPUTATION_DEFINITION = 0.99
 LINEAR_SYSTEM_REASONING = 0.99
 FACTORISATION_REASONING = 0.99
 EIGENVALUE_REASONING = 0.99
 SVD_REASONING = 0.99
 ITERATIVE_SOLVER_REASONING = 0.99
 SPARSE_MATRIX_REASONING = 0.98
 PRECONDITIONING_REASONING = 0.98
 POLICY = "Reduce confidence when matrix structure, conditioning, sparsity, arithmetic precision, solver tolerance, preconditioner or spectral information are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, LinearAlgebraComputationReasoning,
  MatrixComputationReasoning, LinearSystemReasoning, FactorisationReasoning,
  LUReasoning, QRReasoning, CholeskyReasoning, SVDReasoning,
  EigenvalueReasoning, LeastSquaresReasoning, SparseMatrixReasoning,
  IterativeSolverReasoning, KrylovReasoning, PreconditioningReasoning,
  ConditioningReasoning, StabilityReasoning, LowRankReasoning,
  ParallelLinearAlgebraReasoning, KnowledgeGraphConstruction,
  RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "linear algebra computation" -> LinearAlgebraComputation
  "computational linear algebra" -> LinearAlgebraComputation
  "numerical linear algebra" -> NumericalLinearAlgebra
  "SVD" -> SingularValueDecomposition
  "SOR" -> SuccessiveOverRelaxation
  "ILU" -> IncompleteLU
  "pseudoinverse" -> MoorePenrosePseudoinverse
 }
}

EXECUTION_RULES {
 E1 = "If matrices or vectors are manipulated through numerical algorithms, activate LinearAlgebraComputation."
 E2 = "If solving A x=b, exploit symmetry, definiteness, sparsity and conditioning."
 E3 = "If matrix factorisation is required, select LU, QR, Cholesky, SVD or another factorisation appropriate to structure."
 E4 = "If an eigenproblem is large and sparse, consider Krylov-subspace methods."
 E5 = "If an iterative solver converges slowly, consider scaling and preconditioning."
 E6 = "If least squares are ill-conditioned, prefer stable QR or SVD approaches over naive normal equations."
 E7 = "If matrices are sparse, use sparse storage and fill-reducing orderings."
 E8 = "If low-rank structure exists, consider truncated or randomised decompositions."
 E9 = "Any computational linear-algebra result should be validated for conditioning, stability, convergence and reproducibility."
}

RECURSION {
 ENTRY = LinearAlgebraComputation
 EXPAND(LinearAlgebraComputation) -> [
  ComputationalLinearAlgebra, NumericalLinearAlgebra, MatrixComputation,
  VectorComputation, Matrix, Vector, DenseMatrix, SparseMatrix,
  StructuredMatrix, SymmetricMatrix, HermitianMatrix,
  PositiveDefiniteMatrix, OrthogonalMatrix, TriangularMatrix,
  DiagonalMatrix, BandedMatrix, BlockMatrix, LinearSystem,
  OverdeterminedSystem, UnderdeterminedSystem, LeastSquaresProblem,
  MatrixEquation, MatrixVectorProduct, MatrixMatrixProduct, Norm,
  Rank, NullSpace, ColumnSpace, RowSpace, Kernel, DirectSolver,
  GaussianElimination, Pivoting, ForwardSubstitution, BackSubstitution,
  LUDecomposition, CholeskyDecomposition, QRDecomposition,
  HouseholderTransformation, GivensRotation, GramSchmidtProcess,
  MatrixDecomposition, SingularValueDecomposition, TruncatedSVD,
  Eigenvalue, Eigenvector, EigenvalueProblem, SchurDecomposition,
  HessenbergReduction, PowerMethod, InverseIteration,
  RayleighQuotientIteration, QRAlgorithm, LanczosMethod, ArnoldiMethod,
  KrylovSubspace, IterativeSolver, JacobiMethod, GaussSeidelMethod,
  SuccessiveOverRelaxation, ConjugateGradientMethod, MINRES, GMRES,
  BiCGSTAB, Preconditioner, IncompleteLU, IncompleteCholesky,
  Multigrid, ConditionNumber, Conditioning, PerturbationAnalysis,
  Residual, ForwardError, BackwardError, NumericalStability,
  RoundOffError, FloatingPointArithmetic, MachinePrecision,
  Convergence, SpectralRadius, SparseStorage, CSR, CSC, FillIn,
  Reordering, PermutationMatrix, LowRankApproximation,
  RankRevealingFactorisation, RandomisedLinearAlgebra, RandomisedSVD,
  MatrixFunction, MatrixExponential, Pseudoinverse, KroneckerProduct,
  ParallelLinearAlgebra, DistributedMatrix, GPUComputing,
  ComputationalComplexity, Verification, Benchmarking, Reproducibility
 ]
 EXPAND(ComputationFamilies) -> [
  LinearSystemSolvers,
  MatrixFactorisations,
  EigenvalueMethods,
  SingularValueMethods,
  IterativeAndKrylovMethods,
  SparseMatrixComputation,
  LowRankAndRandomisedMethods,
  ParallelLinearAlgebra
 ]
 STOP_CONDITION = "Stop when matrix structure, computational problem, algorithm, conditioning, stability, convergence, sparsity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Mathematics Ontologies"
 RELATED_ONTOLOGIES = [
  "Linear Algebra Ontologies",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology",
  "Machine Precision Ontology",
  "Scientific Computing Ontology 2",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "Linear Algebra Computation -> Computational Mathematics Ontologies for parent semantics",
  "Linear Algebra Computation -> Linear Algebra Ontologies for mathematical structure",
  "Linear Algebra Computation -> Numerical Methods for algorithms",
  "Linear Algebra Computation -> Numerical Analysis for conditioning and stability",
  "Linear Algebra Computation -> Numerical Error for residual and forward/backward error",
  "Linear Algebra Computation -> Numerical Convergence for iterative solver behaviour",
  "Linear Algebra Computation -> Floating Point Arithmetic for finite-precision effects",
  "Linear Algebra Computation -> Scientific Computing for applied matrix systems",
  "Linear Algebra Computation -> HPC for scalable parallel matrix computation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible matrix algorithms, decompositions or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve abstract-versus-computational linear algebra distinction.",
  "Preserve dense-versus-sparse matrix distinction.",
  "Preserve direct-versus-iterative solver distinction.",
  "Preserve residual-versus-solution-error distinction.",
  "Preserve conditioning-versus-stability distinction.",
  "Preserve full-rank-versus-low-rank distinction.",
  "Preserve serial-versus-parallel computation distinction.",
  "Preserve machine-readable linear-algebra-computation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Linear algebra computation applies numerical and algorithmic methods to matrix and vector problems."
 SYSTEM_SUMMARY = "Direct and iterative solvers compute solutions of linear systems while exploiting matrix structure and sparsity."
 FACTORISATION_SUMMARY = "LU, QR, Cholesky, Schur and SVD decompositions expose useful numerical structure."
 EIGEN_SUMMARY = "Power, inverse, QR, Lanczos and Arnoldi methods solve eigenvalue problems at different scales."
 SPARSE_SUMMARY = "Sparse storage, reordering and preconditioning reduce memory and computational cost."
 CONDITIONING_SUMMARY = "Condition numbers and perturbation analysis quantify sensitivity of matrix problems."
 LOW_RANK_SUMMARY = "Truncated SVD and related methods compress matrices when singular values decay."
 VALIDATION_SUMMARY = "Computational linear-algebra results should be checked for residuals, conditioning, stability, convergence, memory cost and reproducibility."
}

FLOW {
 INPUT
 -> detect_linear_algebra_computation_context
 -> identify_matrix_dimensions_structure_sparsity_problem_type_and_accuracy_goal
 -> classify_linear_system_least_squares_eigenvalue_SVD_matrix_function_or_other_problem
 -> detect_symmetry_definiteness_rank_structure_and_sparsity
 -> select_direct_iterative_factorisation_Krylov_randomised_or_low_rank_method
 -> analyse_conditioning_and_scaling
 -> analyse_stability_roundoff_and_backward_error
 -> if_iterative_assess_residual_spectral_properties_preconditioner_and_stopping_rule
 -> if_sparse_select_storage_reordering_and_fill_reduction
 -> if_large_scale_assess_memory_parallelism_communication_and_complexity
 -> validate_with_residuals_error_bounds_reference_solutions_and_reproducibility
 -> route_to_computational_mathematics_linear_algebra_numerical_methods_analysis_error_stability_convergence_floating_point_scientific_computing_or_HPC_ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Linear Algebra Computation layer defines algorithmic and numerical computation with matrices and vectors. It supports dense, sparse, structured, symmetric, Hermitian, positive-definite, triangular, diagonal, banded and block matrices, linear and least-squares systems, matrix-vector and matrix-matrix products, norms, rank and subspaces, Gaussian elimination and pivoting, forward and back substitution, LU, LDU, Cholesky, QR, Schur and SVD decompositions, Householder and Givens transformations, Gram-Schmidt methods, eigenvalue algorithms, power and inverse iteration, QR, Lanczos and Arnoldi methods, Krylov subspaces, Jacobi, Gauss-Seidel, SOR, conjugate-gradient, MINRES, GMRES and BiCGSTAB solvers, preconditioning, conditioning, residuals and numerical errors, sparse storage and fill reduction, low-rank and randomised methods, matrix functions, pseudoinverses, parallel linear algebra, GPU computation, complexity, verification, benchmarking and reproducibility."
}

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

}

END_FLOW