Eigenvalue Computation Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Eigenvalue Computation Ontology within the Kireth Research Semantic Library. Eigenvalue computation studies numerical methods for determining eigenvalues, eigenvectors and invariant subspaces of matrices and linear operators. This ontology supports characteristic and generalized eigenproblems, power and inverse iteration, Rayleigh quotient iteration, QR algorithms, Hessenberg and tridiagonal reduction, Lanczos and Arnoldi methods, Krylov subspaces, sparse and dense eigenvalue problems, conditioning, pseudospectra, perturbation analysis, convergence, stability and scalable parallel computation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = EigenvalueComputation
 ENTITY_CLASS = NumericalSpectralComputationFramework
 PRIMARY_CONTEXT = LinearAlgebraComputation
 DEFINITION = "Eigenvalue computation is the numerical determination of eigenvalues, eigenvectors and invariant subspaces associated with matrices or matrix pencils."
 SYMBOLIC_FORMS = [
  "A*v=lambda*v",
  "A*v=lambda*B*v",
  "rho(A)=max_i |lambda_i|",
  "r=A*v-lambda*v"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for standard and generalized eigenproblems, dense and sparse eigensolvers, Krylov methods, spectral transformations, conditioning, convergence and finite-precision spectral analysis."
}

SCOPE {
 INCLUDE = [
  EigenvalueComputation,
  EigenvalueProblem,
  StandardEigenvalueProblem,
  GeneralisedEigenvalueProblem,
  MatrixPencil,
  Eigenvalue,
  Eigenvector,
  LeftEigenvector,
  RightEigenvector,
  Eigenpair,
  Spectrum,
  SpectralRadius,
  SpectralGap,
  AlgebraicMultiplicity,
  GeometricMultiplicity,
  RepeatedEigenvalue,
  SimpleEigenvalue,
  DefectiveMatrix,
  DiagonalisableMatrix,
  InvariantSubspace,
  Eigenspace,
  SchurDecomposition,
  RealSchurForm,
  ComplexSchurForm,
  GeneralisedSchurDecomposition,
  QZAlgorithm,
  HessenbergReduction,
  TridiagonalReduction,
  HouseholderTransformation,
  GivensRotation,
  PowerMethod,
  InverseIteration,
  ShiftedInverseIteration,
  RayleighQuotient,
  RayleighQuotientIteration,
  QRAlgorithm,
  ShiftedQRAlgorithm,
  ImplicitQRAlgorithm,
  FrancisQRStep,
  DivideAndConquerEigenSolver,
  BisectionEigenSolver,
  MRRR,
  JacobiEigenvalueMethod,
  LanczosMethod,
  ArnoldiMethod,
  KrylovSubspace,
  RitzValue,
  RitzVector,
  HarmonicRitzValue,
  Residual,
  EigenResidual,
  Restart,
  ImplicitRestart,
  ThickRestart,
  KrylovSchurMethod,
  SubspaceIteration,
  OrthogonalIteration,
  Deflation,
  Locking,
  ShiftAndInvert,
  SpectralTransformation,
  PolynomialFiltering,
  RationalFiltering,
  SparseEigenvalueProblem,
  DenseEigenvalueProblem,
  SymmetricEigenvalueProblem,
  HermitianEigenvalueProblem,
  NonsymmetricEigenvalueProblem,
  PositiveDefiniteGeneralisedEigenproblem,
  ConditionNumber,
  EigenvalueConditionNumber,
  EigenvectorConditioning,
  PerturbationAnalysis,
  BauerFikeTheorem,
  DavisKahanTheorem,
  WeylTheorem,
  Pseudospectrum,
  NonNormalMatrix,
  TransientGrowth,
  BackwardError,
  ForwardError,
  NumericalStability,
  RoundOffError,
  FloatingPointArithmetic,
  MachinePrecision,
  Scaling,
  Balancing,
  Convergence,
  ConvergenceRate,
  StoppingCriterion,
  Tolerance,
  DenseEigensolver,
  SparseEigensolver,
  ParallelEigensolver,
  DistributedEigensolver,
  GPUEigensolver,
  MixedPrecisionEigensolver,
  ComputationalComplexity,
  MemoryComplexity,
  CommunicationCost,
  Verification,
  Benchmarking,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  SingularValueComputationWithoutEigenvalueContext,
  SymbolicCharacteristicPolynomialManipulationWithoutNumericalEigensolver,
  DynamicalSystemStabilityWithoutMatrixSpectralComputation,
  TensorEigenproblemWithoutMatrixOrOperatorContext
 ]
 DISAMBIGUATION_RULE = "When the central task is numerical determination of eigenvalues, eigenvectors or invariant subspaces of a matrix or matrix pencil, interpret the context as eigenvalue computation."
}

CORE_CONCEPTS {
 EigenvalueComputation = "Numerical calculation of eigenvalues, eigenvectors and invariant subspaces."
 EigenvalueProblem = "Problem A v=lambda v."
 GeneralisedEigenvalueProblem = "Problem A v=lambda B v."
 EigenResidual = "Residual r=A v-lambda v measuring eigenpair consistency."
 InvariantSubspace = "Subspace mapped into itself by the matrix or operator."
 KrylovSubspace = "Subspace generated from repeated applications of a matrix to a starting vector."
 SchurDecomposition = "Stable spectral factorisation reducing a matrix to triangular or quasi-triangular form."
 SpectralTransformation = "Transformation such as shift-and-invert used to target selected eigenvalues."
 Pseudospectrum = "Set describing spectral sensitivity under perturbations."
}

RELATIONS {
 EigenvalueComputation --is_child_of--> LinearAlgebraComputation
 EigenvalueProblem --has_solution--> Eigenpair
 Eigenpair --contains--> Eigenvalue
 Eigenpair --contains--> Eigenvector
 GeneralisedEigenvalueProblem --uses--> MatrixPencil
 HessenbergReduction --precedes--> NonsymmetricQRAlgorithm
 TridiagonalReduction --precedes--> SymmetricEigenvalueSolver
 QRAlgorithm --computes--> SchurForm
 SchurDecomposition --reveals--> Eigenvalues
 PowerMethod --targets--> DominantEigenvalue
 InverseIteration --targets--> EigenvalueNearShift
 RayleighQuotientIteration --uses--> RayleighQuotient
 LanczosMethod --builds--> KrylovSubspace
 ArnoldiMethod --builds--> KrylovSubspace
 RitzValue --approximates--> Eigenvalue
 ShiftAndInvert --transforms--> TargetSpectrum
 Deflation --removes--> ConvergedEigencomponents
 EigenResidual --measures--> ApproximateEigenpairQuality
 Pseudospectrum --describes--> SpectralSensitivity
 NonNormalMatrix --can_exhibit--> TransientGrowth
}

OPERATORS {
 EIGENPAIR(A,v,lambda) := A*v=lambda*v
 GENERALISED_EIGENPAIR(A,B,v,lambda) := A*v=lambda*B*v
 EIGEN_RESIDUAL(A,v,lambda) := r=A*v-lambda*v
 RELATIVE_EIGEN_RESIDUAL(A,v,lambda) := ||A*v-lambda*v||/((||A||+|lambda|)*||v||)
 RAYLEIGH_QUOTIENT(A,x) := (x^*A*x)/(x^*x)
 POWER_ITERATION(A,x) := x_next=A*x/||A*x||
 SHIFT_INVERT(A,sigma) := (A-sigma*I)^(-1)
 KRYLOV_SPACE(A,v,m) := span{v,A*v,...,A^(m-1)*v}
 SPECTRAL_RADIUS(A) := max_i |lambda_i|
}

AXIOMS {
 A1 = "Eigenvalues are invariant under similarity transformations."
 A2 = "Schur decomposition provides a numerically stable canonical route to dense eigenvalue computation."
 A3 = "Symmetric or Hermitian eigenproblems have real eigenvalues and admit orthogonal or unitary eigenvector bases."
 A4 = "Nonsymmetric eigenvectors can be highly sensitive to perturbations."
 A5 = "Residual size and eigenvalue forward error are distinct."
 A6 = "Krylov methods are suited to computing selected eigenpairs of large sparse matrices."
 A7 = "Shift-and-invert transformations alter computational cost while preserving targeted spectral information through a known mapping."
 A8 = "Eigenvalue computations require residual, conditioning, convergence and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(matrix_shape,structure,sparsity,precision,target_spectrum,number_of_eigenpairs)
 R2_CLASS = classify(standard,generalised,symmetric,Hermitian,nonsymmetric,dense_or_sparse_problem)
 R3_REDUCTION = if_dense choose(Hessenberg,tridiagonal_or_generalised_reduction)
 R4_METHOD = select(QR,power,inverse,Rayleigh,Lanczos,Arnoldi,KrylovSchur_or_other_method)
 R5_TARGET = if_selected_spectrum choose(shift_invert,filtering_or_restart_strategy)
 R6_CONVERGENCE = track(Ritz_values,residuals,spectral_gap_and_stopping_criterion)
 R7_CONDITIONING = assess(eigenvalue_and_eigenvector_sensitivity,pseudospectrum_if_needed)
 R8_STABILITY = analyse(orthogonality,roundoff,balancing_and_backward_error)
 R9_SCALE = if_large use(sparse,parallel,GPU_or_distributed_eigensolver)
 R10_VALIDATION = check(residuals,orthogonality,invariant_subspaces,reference_results_and_reproducibility)
}

CONSTRAINTS {
 C1 = "Characteristic-polynomial computation is generally not the preferred numerical route to eigenvalues."
 C2 = "Power iteration converges only under suitable spectral dominance conditions."
 C3 = "Inverse iteration requires solving shifted linear systems."
 C4 = "Repeated or clustered eigenvalues can slow convergence and make eigenvectors nonunique within invariant subspaces."
 C5 = "Nonnormal matrices can have highly sensitive eigenvalues and large transient effects."
 C6 = "Lanczos methods require control of loss of orthogonality in finite precision."
 C7 = "Arnoldi and GMRES-style Krylov bases can become memory intensive without restarting."
 C8 = "Shift-and-invert can improve convergence but may make factorisation or linear solves expensive."
 C9 = "A small residual does not necessarily imply a small eigenvalue forward error for ill-conditioned eigenproblems."
 C10 = "Distributed eigensolvers can be communication- and synchronisation-bound."
}

SEMANTIC_EQUIVALENCE {
 "EigenvalueComputation" <=> "NumericalEigenvalueComputation"
 "GeneralisedEigenvalueProblem" <=> "GeneralizedEigenvalueProblem"
 "RayleighQuotientIteration" <=> "RQI"
 "ImplicitlyRestartedArnoldi" <=> "IRAM"
 "GeneralisedSchurDecomposition" <=> "QZDecomposition"
 "MultipleRelativelyRobustRepresentations" <=> "MRRR"
}

VALIDATION {
 V1 = "Matrix dimensions and eigenproblem class are explicit."
 V2 = "Symmetry, Hermitian structure or definiteness assumptions are verified."
 V3 = "Target spectrum and number of required eigenpairs are documented."
 V4 = "Eigenpair residuals are checked."
 V5 = "Eigenvector orthogonality is checked for symmetric or Hermitian problems."
 V6 = "Conditioning is assessed where spectral sensitivity matters."
 V7 = "Restart, shift and filtering parameters are documented."
 V8 = "Convergence tolerances are scale-aware."
 V9 = "Reference or benchmark eigenvalues are used where feasible."
 V10 = "Results are reproducible under documented arithmetic and solver settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 EIGENVALUE_COMPUTATION_DEFINITION = 0.99
 DENSE_QR_REASONING = 0.99
 POWER_ITERATION_REASONING = 0.99
 INVERSE_ITERATION_REASONING = 0.99
 LANCZOS_REASONING = 0.99
 ARNOLDI_REASONING = 0.99
 CONDITIONING_REASONING = 0.98
 PSEUDOSPECTRAL_REASONING = 0.98
 POLICY = "Reduce confidence when matrix structure, target spectrum, shift, restart strategy, conditioning, residual scaling or arithmetic precision are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, EigenvalueComputationReasoning,
  EigenpairReasoning, GeneralisedEigenproblemReasoning,
  PowerMethodReasoning, InverseIterationReasoning,
  RayleighQuotientReasoning, QRAlgorithmReasoning,
  SchurReasoning, LanczosReasoning, ArnoldiReasoning,
  KrylovSubspaceReasoning, RitzValueReasoning,
  ShiftInvertReasoning, SpectralFilteringReasoning,
  EigenvalueConditioningReasoning, PseudospectrumReasoning,
  SparseEigenvalueReasoning, ParallelEigensolverReasoning,
  KnowledgeGraphConstruction, RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "eigenvalue computation" -> EigenvalueComputation
  "eigenvalue calculation" -> EigenvalueComputation
  "generalized eigenvalue problem" -> GeneralisedEigenvalueProblem
  "RQI" -> RayleighQuotientIteration
  "QZ decomposition" -> GeneralisedSchurDecomposition
  "MRRR" -> MultipleRelativelyRobustRepresentations
 }
}

EXECUTION_RULES {
 E1 = "If numerical eigenvalues, eigenvectors or invariant subspaces are required, activate EigenvalueComputationOntology."
 E2 = "If the matrix is symmetric or Hermitian, use structure-preserving eigensolver reasoning."
 E3 = "If the matrix is dense and general, reduce to Hessenberg form before QR-based eigenvalue computation where appropriate."
 E4 = "If only dominant eigenvalues are required, consider power or Krylov methods."
 E5 = "If eigenvalues near a target shift are required, consider inverse iteration or shift-and-invert."
 E6 = "If a large sparse symmetric problem is present, consider Lanczos methods."
 E7 = "If a large sparse nonsymmetric problem is present, consider Arnoldi or Krylov-Schur methods."
 E8 = "If nonnormal sensitivity matters, assess pseudospectral or left-right eigenvector conditioning."
 E9 = "Validate eigenpairs through residuals, orthogonality, convergence, conditioning and reproducibility."
}

RECURSION {
 ENTRY = EigenvalueComputation
 EXPAND(EigenvalueComputation) -> [
  EigenvalueProblem, StandardEigenvalueProblem, GeneralisedEigenvalueProblem,
  MatrixPencil, Eigenvalue, Eigenvector, LeftEigenvector, RightEigenvector,
  Eigenpair, Spectrum, SpectralRadius, SpectralGap, AlgebraicMultiplicity,
  GeometricMultiplicity, RepeatedEigenvalue, SimpleEigenvalue,
  DefectiveMatrix, InvariantSubspace, Eigenspace, SchurDecomposition,
  RealSchurForm, ComplexSchurForm, GeneralisedSchurDecomposition,
  QZAlgorithm, HessenbergReduction, TridiagonalReduction,
  HouseholderTransformation, GivensRotation, PowerMethod,
  InverseIteration, ShiftedInverseIteration, RayleighQuotient,
  RayleighQuotientIteration, QRAlgorithm, ShiftedQRAlgorithm,
  ImplicitQRAlgorithm, FrancisQRStep, DivideAndConquerEigenSolver,
  BisectionEigenSolver, MRRR, JacobiEigenvalueMethod, LanczosMethod,
  ArnoldiMethod, KrylovSubspace, RitzValue, RitzVector,
  HarmonicRitzValue, Residual, Restart, ImplicitRestart, ThickRestart,
  KrylovSchurMethod, SubspaceIteration, OrthogonalIteration, Deflation,
  Locking, ShiftAndInvert, SpectralTransformation, PolynomialFiltering,
  RationalFiltering, SparseEigenvalueProblem, DenseEigenvalueProblem,
  SymmetricEigenvalueProblem, HermitianEigenvalueProblem,
  NonsymmetricEigenvalueProblem, ConditionNumber,
  EigenvalueConditionNumber, EigenvectorConditioning,
  PerturbationAnalysis, BauerFikeTheorem, DavisKahanTheorem,
  WeylTheorem, Pseudospectrum, NonNormalMatrix, BackwardError,
  ForwardError, NumericalStability, FloatingPointArithmetic,
  MachinePrecision, Scaling, Balancing, Convergence, StoppingCriterion,
  DenseEigensolver, SparseEigensolver, ParallelEigensolver,
  DistributedEigensolver, GPUEigensolver, MixedPrecisionEigensolver,
  Verification, Benchmarking, Reproducibility
 ]
 STOP_CONDITION = "Stop when eigenproblem class, target spectrum, method, convergence, conditioning, stability and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Linear Algebra Computation"
 RELATED_ONTOLOGIES = [
  "Linear Algebra Computation",
  "Numerical Linear Algebra Ontology 2",
  "Matrix Computation Ontology",
  "Matrix Decomposition Ontology 2",
  "Singular Value Decomposition Ontology",
  "Sparse Matrix Ontology 2",
  "Dense Matrix Ontology",
  "QR Decomposition Ontology",
  "Numerical Analysis Ontology 2",
  "Numerical Stability Ontology 2",
  "High Performance Computing Ontologies"
 ]
 ROUTE_RULES = [
  "Eigenvalue Computation -> Linear Algebra Computation for parent semantics",
  "Eigenvalue Computation -> Numerical Linear Algebra for finite-precision spectral algorithms",
  "Eigenvalue Computation -> Matrix Decomposition for Schur and reduction methods",
  "Eigenvalue Computation -> SVD for singular-value and condition relationships",
  "Eigenvalue Computation -> Sparse Matrix for large sparse eigenproblems",
  "Eigenvalue Computation -> Dense Matrix for dense QR and divide-and-conquer algorithms",
  "Eigenvalue Computation -> QR Decomposition for QR iteration",
  "Eigenvalue Computation -> Numerical Analysis for perturbation and conditioning",
  "Eigenvalue Computation -> HPC for parallel, distributed and GPU eigensolvers"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible eigensolvers, spectral transformations or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve eigenvalue-versus-singular-value distinction.",
  "Preserve standard-versus-generalised eigenproblem distinction.",
  "Preserve left-versus-right eigenvector distinction.",
  "Preserve dense-versus-sparse eigensolver distinction.",
  "Preserve residual-versus-forward-error distinction.",
  "Preserve exact-spectrum-versus-approximate-Ritz distinction.",
  "Preserve normal-versus-nonnormal spectral behaviour distinction.",
  "Preserve machine-readable eigenvalue-computation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Eigenvalue computation numerically determines eigenvalues, eigenvectors and invariant subspaces of matrices or matrix pencils."
 DENSE_SUMMARY = "Dense eigensolvers use Hessenberg or tridiagonal reductions followed by QR, divide-and-conquer, bisection or related methods."
 KRYLOV_SUMMARY = "Lanczos and Arnoldi methods approximate selected eigenpairs through Krylov subspaces."
 TARGETING_SUMMARY = "Shift-and-invert and filtering transformations focus computation on selected spectral regions."
 CONDITIONING_SUMMARY = "Eigenvalue and eigenvector sensitivity depends strongly on matrix normality, separation and left-right eigenvector geometry."
 RESIDUAL_SUMMARY = "Eigenpair residuals quantify equation consistency but must be interpreted with conditioning."
 VALIDATION_SUMMARY = "Eigenvalue results should be checked for residuals, orthogonality, convergence, sensitivity and reproducibility."
}

FLOW {
 INPUT
 -> detect_eigenvalue_computation_context
 -> identify_matrix_shape_structure_sparsity_precision_target_spectrum_and_required_eigenpairs
 -> classify_standard_generalised_symmetric_Hermitian_nonsymmetric_dense_or_sparse_problem
 -> if_dense_reduce_to_Hessenberg_tridiagonal_or_generalised_Schur_form
 -> select_QR_power_inverse_Rayleigh_Lanczos_Arnoldi_KrylovSchur_or_other_method
 -> if_targeted_choose_shift_invert_filtering_restart_or_deflation
 -> iterate_and_track_Ritz_values_residuals_spectral_gap_and_stopping_criterion
 -> analyse_conditioning_pseudospectrum_orthogonality_roundoff_and_backward_error
 -> if_large_scale_use_sparse_parallel_GPU_or_distributed_eigensolver
 -> validate_residuals_orthogonality_invariant_subspaces_reference_results_and_reproducibility
 -> route_to_related_linear_algebra_matrix_decomposition_SVD_sparse_dense_QR_analysis_stability_and_HPC_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Eigenvalue Computation Ontology defines numerical spectral computation for matrices and matrix pencils. It supports standard and generalised eigenvalue problems, left and right eigenvectors, spectra, spectral radius and gaps, multiplicity and invariant subspaces, Schur and generalised Schur forms, Hessenberg and tridiagonal reductions, power and inverse iteration, Rayleigh quotient iteration, shifted and implicit QR algorithms, divide-and-conquer, bisection, MRRR and Jacobi methods, Lanczos and Arnoldi Krylov methods, Ritz values and vectors, restarting, deflation and locking, shift-and-invert and spectral filtering, dense and sparse eigenproblems, eigenvalue conditioning, perturbation theory, pseudospectra and nonnormality, residual and error analysis, scaling and balancing, parallel, distributed, GPU and mixed-precision eigensolvers, verification, benchmarking and reproducibility."
}

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

}

END_FLOW