Linear Solver Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Linear Solver Ontology within the Kireth Research Semantic Library. A linear solver is a computational method for determining vectors that satisfy linear systems such as A*x=b. This ontology supports dense and sparse systems, direct and iterative solvers, matrix factorisation, stationary methods, Krylov methods, preconditioning, residuals, conditioning, numerical stability, convergence, mixed precision, parallel execution and verification.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Linear Solver Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Computational Mathematics"
 SPECIALISATION = "Solving Equations / Linear Solver"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/computational-mathematics-ontologies/solving-equations/linear-solver-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = LinearSolver
 ENTITY_CLASS = ComputationalLinearSystemSolutionFramework
 PRIMARY_CONTEXT = SolvingEquations
 DEFINITION = "A linear solver is an algorithm or computational procedure for determining an unknown vector x satisfying a linear system A*x=b, exactly or approximately."
 SYMBOLIC_FORMS = [
  "A*x=b",
  "x=A^(-1)*b",
  "r=b-A*x",
  "M^(-1)A*x=M^(-1)b"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for direct and iterative solution of linear systems, factorisation, residuals, conditioning, preconditioning, convergence and finite-precision validation."
}

SCOPE {
 INCLUDE = [
  LinearSolver, LinearSystemSolver, LinearSystem, MatrixEquation,
  CoefficientMatrix, RightHandSide, SolutionVector, DirectSolver,
  IterativeSolver, DenseLinearSolver, SparseLinearSolver,
  SymmetricLinearSolver, HermitianLinearSolver, PositiveDefiniteSolver,
  BandedLinearSolver, BlockLinearSolver, TriangularSolver,
  GaussianElimination, ForwardSubstitution, BackSubstitution,
  LUDecomposition, QRDecomposition, CholeskyDecomposition,
  LDLTDecomposition, SparseLU, SparseCholesky, SparseQR,
  StationaryIteration, JacobiMethod, GaussSeidelMethod,
  SuccessiveOverRelaxation, SOR, WeightedJacobi,
  KrylovSubspaceMethod, ConjugateGradientMethod, CG,
  MINRES, GMRES, BiCG, BiCGSTAB, QMR, TFQMR,
  LSQR, LSMR, Multigrid, AlgebraicMultigrid, AMG,
  DomainDecomposition, SchwarzMethod, Preconditioner,
  LeftPreconditioning, RightPreconditioning, SplitPreconditioning,
  JacobiPreconditioner, BlockJacobiPreconditioner,
  IncompleteLU, ILU, IncompleteCholesky, IC,
  ApproximateInversePreconditioner, Scaling, Equilibration,
  Pivoting, PartialPivoting, CompletePivoting,
  Reordering, FillReducingOrdering, InitialGuess,
  Residual, ResidualNorm, RelativeResidual, ForwardError,
  BackwardError, ComponentwiseError, NormwiseError,
  ConditionNumber, Conditioning, Sensitivity, NumericalStability,
  BackwardStability, FloatingPointArithmetic, MachinePrecision,
  RoundOffError, Convergence, ConvergenceRate, SpectralRadius,
  StoppingCriterion, AbsoluteTolerance, RelativeTolerance,
  ResidualTolerance, MaximumIterations, Stagnation, Breakdown,
  IterativeRefinement, MixedPrecisionSolver, MultipleRightHandSides,
  FactorReuse, SolverStatus, Success, Failure, Warning,
  ComputationalComplexity, MemoryComplexity, CommunicationCost,
  ParallelLinearSolver, DistributedLinearSolver, GPULinearSolver,
  Verification, Benchmarking, Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  NonlinearEquationSolver,
  EigenvalueSolverWithoutLinearSystemSemantics,
  OptimisationSolverWithoutLinearEquationContext,
  ExactSymbolicLinearAlgebraWithoutComputationalSolverSemantics
 ]
 DISAMBIGUATION_RULE = "When the task is to compute x satisfying A*x=b or an equivalent linear system, interpret the context as a linear solver."
}

CORE_CONCEPTS {
 LinearSolver = "Computational method for solving a linear system."
 DirectSolver = "Method that obtains a solution through matrix factorisation or elimination without iterative convergence as the primary mechanism."
 IterativeSolver = "Method that generates successive approximations to a linear-system solution."
 Residual = "Vector r=b-A*x measuring equation mismatch."
 Preconditioner = "Transformation designed to improve iterative convergence."
 ConditionNumber = "Measure of sensitivity of the solution to perturbations in matrix or right-hand-side data."
 KrylovSubspaceMethod = "Iterative method operating in spaces generated by repeated matrix-vector products."
 IterativeRefinement = "Correction process using residuals to improve a computed linear-system solution."
}

RELATIONS {
 LinearSolver --is_child_of--> EquationSolver
 LinearSolver --solves--> LinearSystem
 DirectSolver --uses--> MatrixFactorisation
 GaussianElimination --solves--> LinearSystem
 LUDecomposition --supports--> LinearSystemSolution
 QRDecomposition --supports--> LeastSquaresAndLinearSystemSolution
 CholeskyDecomposition --solves--> PositiveDefiniteSystem
 JacobiMethod --is_type_of--> StationaryIteration
 GaussSeidelMethod --is_type_of--> StationaryIteration
 ConjugateGradientMethod --is_type_of--> KrylovSubspaceMethod
 GMRES --is_type_of--> KrylovSubspaceMethod
 Preconditioner --improves--> IterativeConvergence
 Residual --measures--> LinearSystemMismatch
 ConditionNumber --quantifies--> ProblemSensitivity
 NumericalStability --describes--> SolverErrorPropagation
 IterativeRefinement --improves--> ComputedSolution
 Reordering --can_reduce--> SparseFactorisationFill
 FactorReuse --reduces--> RepeatedSolveCost
}

OPERATORS {
 LINEAR_SYSTEM(A,x,b) := A*x=b
 RESIDUAL(A,x,b) := r=b-A*x
 RELATIVE_RESIDUAL(A,x,b) := ||b-A*x||/(||A||*||x||+||b||)
 DIRECT_SOLVE(A,b) := factorise_and_solve(A,b)
 PRECONDITIONED_SYSTEM(M,A,x,b) := M^(-1)*A*x=M^(-1)*b
 JACOBI_STEP(D,L,U,x,b) := x_next=D^(-1)*(b-(L+U)*x)
 GAUSS_SEIDEL_STEP(D,L,U,x,b) := x_next=(D+L)^(-1)*(b-U*x)
 CG_SPACE(A,r,k) := K_k(A,r)
 ITERATIVE_REFINEMENT_STEP(A,x,b) := solve(A,delta=b-A*x); x_next=x+delta
}

AXIOMS {
 A1 = "A linear solver must preserve the semantics of the original system A*x=b."
 A2 = "Problem conditioning and solver stability are distinct."
 A3 = "Residual and forward solution error are distinct."
 A4 = "Direct solvers and iterative solvers have different computational and convergence semantics."
 A5 = "Matrix structure should be exploited when it improves reliability or efficiency."
 A6 = "Preconditioning may alter convergence behaviour while preserving the intended exact solution."
 A7 = "Iterative stopping criteria must be explicit and scale appropriate."
 A8 = "Linear-solver results require residual, conditioning, error and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,structure,sparsity,precision,rhs_count,accuracy_goal)
 R2_CLASS = classify(square,rectangular,symmetric,Hermitian,positive_definite,sparse_or_dense)
 R3_METHOD = select(direct,stationary,Krylov,multigrid_or_hybrid_solver)
 R4_PREPARE = choose(scaling,pivoting,reordering,preconditioner,initial_guess)
 R5_SOLVE = execute_factorisation_or_iterative_process
 R6_CONVERGENCE = if_iterative monitor(residual,rate,stagnation,breakdown)
 R7_ERROR = assess(conditioning,forward_error,backward_error,roundoff)
 R8_PRECISION = if_mixed_precision apply_iterative_refinement_if_appropriate
 R9_SCALE = if_large use_sparse_parallel_distributed_or_GPU_solver
 R10_VALIDATE = check(residual,error_bounds,reference_solution,status_and_reproducibility)
}

CONSTRAINTS {
 C1 = "A small residual does not guarantee a small forward error for an ill-conditioned system."
 C2 = "Explicit inversion is generally unnecessary for solving A*x=b."
 C3 = "Conjugate gradients require symmetric positive-definite structure in standard form."
 C4 = "MINRES requires symmetric or Hermitian structure."
 C5 = "GMRES memory cost grows with Krylov basis size unless restarted."
 C6 = "Stationary iterations converge only under suitable spectral conditions."
 C7 = "Sparse direct methods can create large fill-in."
 C8 = "Poor preconditioning can provide little benefit or increase total cost."
 C9 = "Stopping tolerances below attainable precision can cause stagnation."
 C10 = "Parallel linear solvers can be limited by communication and synchronisation."
}

SEMANTIC_EQUIVALENCE {
 "LinearSolver" <=> "LinearSystemSolver"
 "ConjugateGradientMethod" <=> "CG"
 "SuccessiveOverRelaxation" <=> "SOR"
 "IncompleteLU" <=> "ILU"
 "IncompleteCholesky" <=> "IC"
 "AlgebraicMultigrid" <=> "AMG"
}

VALIDATION {
 V1 = "Matrix dimensions are explicit."
 V2 = "Matrix structure and sparsity are documented."
 V3 = "Solver family and configuration are documented."
 V4 = "Residuals are checked using the original system."
 V5 = "Conditioning is assessed where relevant."
 V6 = "Iterative stopping criteria are documented."
 V7 = "Preconditioner and scaling are documented where used."
 V8 = "Solver termination status is explicit."
 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_SOLVER_DEFINITION = 0.99
 DIRECT_SOLVER_REASONING = 0.99
 ITERATIVE_SOLVER_REASONING = 0.99
 KRYLOV_REASONING = 0.99
 PRECONDITIONING_REASONING = 0.98
 CONDITIONING_REASONING = 0.99
 MIXED_PRECISION_REASONING = 0.98
 POLICY = "Reduce confidence when matrix structure, conditioning, sparsity, initial guess, preconditioner, stopping criteria or arithmetic precision are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, LinearSolverReasoning,
  DirectSolverReasoning, IterativeSolverReasoning,
  GaussianEliminationReasoning, LUReasoning, QRReasoning,
  CholeskyReasoning, StationaryIterationReasoning,
  ConjugateGradientReasoning, GMRESReasoning,
  KrylovReasoning, PreconditioningReasoning,
  MultigridReasoning, ResidualReasoning,
  ConditioningReasoning, NumericalStabilityReasoning,
  IterativeRefinementReasoning, SolverStatusReasoning,
  KnowledgeGraphConstruction, RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "linear solver" -> LinearSolver
  "linear system solver" -> LinearSolver
  "CG" -> ConjugateGradientMethod
  "SOR" -> SuccessiveOverRelaxation
  "ILU" -> IncompleteLU
  "IC" -> IncompleteCholesky
  "AMG" -> AlgebraicMultigrid
 }
}

EXECUTION_RULES {
 E1 = "If the task is to compute x satisfying A*x=b, activate LinearSolverOntology."
 E2 = "Detect matrix structure before selecting a solver."
 E3 = "For dense general systems, consider pivoted LU."
 E4 = "For symmetric positive-definite systems, consider Cholesky or conjugate gradients."
 E5 = "For large sparse systems, consider Krylov methods with preconditioning."
 E6 = "For repeated right-hand sides, reuse factorisations or preconditioners where appropriate."
 E7 = "For iterative methods, monitor residual, convergence rate, stagnation and breakdown."
 E8 = "For mixed precision, consider higher-precision residual evaluation and iterative refinement."
 E9 = "Validate solver output using the original system, conditioning and reproducibility."
}

RECURSION {
 ENTRY = LinearSolver
 EXPAND(LinearSolver) -> [
  LinearSystemSolver,LinearSystem,MatrixEquation,CoefficientMatrix,
  RightHandSide,SolutionVector,DirectSolver,IterativeSolver,
  DenseLinearSolver,SparseLinearSolver,SymmetricLinearSolver,
  PositiveDefiniteSolver,GaussianElimination,ForwardSubstitution,
  BackSubstitution,LUDecomposition,QRDecomposition,CholeskyDecomposition,
  LDLTDecomposition,SparseLU,SparseCholesky,SparseQR,
  StationaryIteration,JacobiMethod,GaussSeidelMethod,
  SuccessiveOverRelaxation,WeightedJacobi,KrylovSubspaceMethod,
  ConjugateGradientMethod,MINRES,GMRES,BiCGSTAB,LSQR,LSMR,
  Multigrid,AlgebraicMultigrid,DomainDecomposition,Preconditioner,
  LeftPreconditioning,RightPreconditioning,JacobiPreconditioner,
  IncompleteLU,IncompleteCholesky,Scaling,Equilibration,Pivoting,
  Reordering,InitialGuess,Residual,ResidualNorm,RelativeResidual,
  ForwardError,BackwardError,ConditionNumber,Conditioning,
  NumericalStability,FloatingPointArithmetic,MachinePrecision,
  RoundOffError,Convergence,ConvergenceRate,SpectralRadius,
  StoppingCriterion,AbsoluteTolerance,RelativeTolerance,
  MaximumIterations,Stagnation,Breakdown,IterativeRefinement,
  MixedPrecisionSolver,MultipleRightHandSides,FactorReuse,
  SolverStatus,ParallelLinearSolver,DistributedLinearSolver,
  GPULinearSolver,Verification,Benchmarking,Reproducibility
 ]
 EXPAND(LinearSolverFamilies) -> [
  DirectLinearSolvers,
  StationaryIterativeSolvers,
  KrylovSubspaceSolvers,
  MultigridSolvers,
  PreconditionedSolvers,
  SparseLinearSolvers,
  ParallelAndMixedPrecisionLinearSolvers
 ]
 STOP_CONDITION = "Stop when matrix structure, solver family, configuration, convergence, conditioning, error, status and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Equation Solver Ontology"
 RELATED_ONTOLOGIES = [
  "Equation Solver Ontology",
  "Solving Equations",
  "Numerical Linear Algebra Ontology 2",
  "Linear Algebra Computation",
  "Matrix Decomposition Ontology 2",
  "Sparse Matrix Ontology 2",
  "Dense Matrix Ontology",
  "Numerical Analysis Ontology 2",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology"
 ]
 ROUTE_RULES = [
  "Linear Solver -> Equation Solver for parent solver semantics",
  "Linear Solver -> Numerical Linear Algebra for solver algorithms and conditioning",
  "Linear Solver -> Matrix Decomposition for direct factorisation methods",
  "Linear Solver -> Sparse Matrix for sparse storage and sparse solvers",
  "Linear Solver -> Dense Matrix for dense direct solvers",
  "Linear Solver -> Numerical Analysis for convergence and sensitivity",
  "Linear Solver -> Numerical Stability for finite-precision behaviour",
  "Linear Solver -> Numerical Convergence for iterative stopping behaviour"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible linear solver classes, preconditioners or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve direct-versus-iterative solver distinction.",
  "Preserve dense-versus-sparse solver distinction.",
  "Preserve residual-versus-forward-error distinction.",
  "Preserve conditioning-versus-stability distinction.",
  "Preserve solver-versus-preconditioner distinction.",
  "Preserve exact-factorisation-versus-iterative-approximation distinction.",
  "Preserve original-system-versus-preconditioned-system distinction.",
  "Preserve machine-readable linear-solver semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A linear solver computes an unknown vector satisfying a linear system A*x=b."
 DIRECT_SUMMARY = "Gaussian elimination and matrix factorisations provide direct solution methods."
 ITERATIVE_SUMMARY = "Stationary, Krylov and multigrid methods generate successive approximations for large or structured systems."
 PRECONDITIONING_SUMMARY = "Preconditioners transform systems to improve iterative convergence while preserving the intended exact solution."
 ERROR_SUMMARY = "Residuals, forward error, backward error and conditioning provide complementary measures of solution quality."
 PRECISION_SUMMARY = "Finite precision and mixed-precision refinement affect attainable accuracy and convergence."
 VALIDATION_SUMMARY = "Linear-solver results should be checked for residuals, conditioning, convergence, termination status and reproducibility."
}

FLOW {
 INPUT
 -> detect_linear_solver_context
 -> identify_matrix_dimensions_structure_sparsity_precision_rhs_count_and_accuracy_goal
 -> classify_dense_sparse_symmetric_Hermitian_positive_definite_or_general_system
 -> select_direct_stationary_Krylov_multigrid_or_hybrid_solver
 -> choose_scaling_pivoting_reordering_preconditioner_and_initial_guess
 -> execute_factorisation_or_iterative_process
 -> if_iterative_monitor_residual_convergence_rate_stagnation_and_breakdown
 -> assess_conditioning_forward_backward_and_roundoff_error
 -> if_mixed_precision_apply_iterative_refinement_if_appropriate
 -> classify_solver_status
 -> validate_solution_against_original_system_and_reference_information
 -> route_to_related_equation_solver_linear_algebra_and_numerical_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Linear Solver Ontology defines computational methods for solving A*x=b. It supports dense and sparse linear systems, direct and iterative solvers, Gaussian elimination, LU, QR, Cholesky and LDLT factorisations, stationary Jacobi, Gauss-Seidel and SOR methods, Krylov methods including CG, MINRES, GMRES and BiCGSTAB, LSQR and LSMR, multigrid and domain decomposition, preconditioning, scaling, pivoting and reordering, residual and error analysis, conditioning, numerical stability, finite precision, convergence and stopping criteria, iterative refinement, mixed precision, repeated right-hand sides, parallel, distributed and GPU solvers, verification, benchmarking and reproducibility."
}

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

}

END_FLOW