Eigenvector Computation Ontology

This Flow Algebra defines the Eigenvector Computation Ontology within the Kireth Research Semantic Library. Eigenvector computation studies numerical methods for determining right and left eigenvectors and invariant subspaces associated with matrix eigenvalues. It covers iterative, Schur and Krylov methods, Ritz vectors, conditioning, residuals, orthogonality and finite-precision validation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
PRIMARY_ENTITY = EigenvectorComputation
 ENTITY_CLASS = NumericalInvariantDirectionComputationFramework
 PRIMARY_CONTEXT = LinearAlgebraComputation
 DEFINITION = "Eigenvector computation is the numerical determination of nonzero vectors associated with matrix eigenvalues and invariant subspaces associated with selected portions of a spectrum."
 SYMBOLIC_FORMS = ["A*v=lambda*v","w^*A=lambda*w^*","r=A*v-lambda*v","A*V=V*T"]
 SEMANTIC_ROLE = "Machine-readable semantics for right and left eigenvectors, invariant subspaces, iterative algorithms, Ritz approximations, conditioning, residuals and orthogonality."
}

SCOPE {
INCLUDE = [
  EigenvectorComputation,Eigenvector,RightEigenvector,LeftEigenvector,Eigenvalue,Eigenpair,
  Eigenspace,InvariantSubspace,SpectralSubspace,AlgebraicMultiplicity,GeometricMultiplicity,
  RepeatedEigenvalue,ClusteredEigenvalue,DefectiveMatrix,NormalMatrix,NonNormalMatrix,
  SymmetricMatrix,HermitianMatrix,OrthogonalEigenvectors,BiorthogonalEigenvectors,
  EigenvectorNormalisation,PhaseAmbiguity,SignAmbiguity,PowerMethod,InverseIteration,
  ShiftedInverseIteration,RayleighQuotient,RayleighQuotientIteration,QRAlgorithm,
  SchurDecomposition,SchurVector,LanczosMethod,ArnoldiMethod,KrylovSubspace,RitzVector,
  RitzValue,HarmonicRitzVector,RefinedRitzVector,SubspaceIteration,OrthogonalIteration,
  BlockIteration,Deflation,Locking,Restart,ImplicitRestart,ThickRestart,KrylovSchurMethod,
  ShiftAndInvert,SpectralTransformation,PolynomialFiltering,RationalFiltering,
  SparseEigenvectorProblem,DenseEigenvectorProblem,GeneralisedEigenvectorProblem,MatrixPencil,
  EigenResidual,ResidualNorm,RelativeResidual,BackwardError,ForwardError,EigenvectorError,
  AngleError,PrincipalAngle,SubspaceAngle,EigenvectorConditionNumber,EigenvalueConditionNumber,
  SpectralGap,Separation,PerturbationAnalysis,DavisKahanTheorem,BauerFikeTheorem,
  Pseudospectrum,LossOfOrthogonality,Reorthogonalisation,NumericalStability,
  FloatingPointArithmetic,MachinePrecision,RoundOffError,Scaling,Balancing,Convergence,
  ConvergenceRate,StoppingCriterion,Tolerance,DenseEigensolver,SparseEigensolver,
  ParallelEigensolver,DistributedEigensolver,GPUEigensolver,MixedPrecisionEigensolver,
  Verification,Benchmarking,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [EigenvalueOnlyComputationWithoutEigenvectors,SingularVectorComputationWithoutEigenvectorContext,AbstractEigenspaceTheoryWithoutNumericalComputation]
 DISAMBIGUATION_RULE = "When the central task is numerical determination of eigenvectors or invariant subspaces associated with matrix eigenvalues, interpret the context as eigenvector computation."
}

CORE_CONCEPTS {
RightEigenvector = "Nonzero vector v satisfying A*v=lambda*v."
 LeftEigenvector = "Nonzero vector w satisfying w^*A=lambda*w^*."
 Eigenspace = "Vector space associated with an eigenvalue."
 InvariantSubspace = "Subspace mapped into itself by a matrix or operator."
 RitzVector = "Approximate eigenvector extracted from a projected eigenproblem."
 SchurVector = "Vector in an orthogonal or unitary basis reducing a matrix to Schur form."
 EigenvectorConditionNumber = "Measure of eigenvector or eigenspace sensitivity to perturbations."
}

RELATIONS {
EigenvectorComputation --is_child_of--> LinearAlgebraComputation
 Eigenvector --is_component_of--> Eigenpair
 EigenvectorsForEigenvalue --span--> Eigenspace
 InvariantSubspace --is_preserved_by--> MatrixAction
 PowerMethod --approximates--> DominantEigenvector
 InverseIteration --approximates--> EigenvectorNearShift
 RayleighQuotientIteration --refines--> Eigenpair
 SchurDecomposition --produces--> SchurVectors
 LanczosMethod --approximates--> SymmetricInvariantSubspace
 ArnoldiMethod --approximates--> GeneralInvariantSubspace
 RitzVector --approximates--> Eigenvector
 ShiftAndInvert --targets--> InteriorEigenvectors
 Deflation --removes--> ConvergedEigencomponents
 Locking --preserves--> ConvergedEigenvectors
 SpectralGap --influences--> EigenvectorConvergence
 Separation --influences--> EigenvectorConditioning
 Reorthogonalisation --controls--> LossOfOrthogonality
}

OPERATORS {
RIGHT_EIGENVECTOR(A,v,lambda) := A*v=lambda*v
 LEFT_EIGENVECTOR(A,w,lambda) := w^*A=lambda*w^*
 EIGEN_RESIDUAL(A,v,lambda) := A*v-lambda*v
 RELATIVE_RESIDUAL(A,v,lambda) := ||A*v-lambda*v||/((||A||+|lambda|)*||v||)
 NORMALISE(v) := v/||v||
 RAYLEIGH_QUOTIENT(A,v) := (v^*A*v)/(v^*v)
 KRYLOV_SPACE(A,v,m) := span{v,A*v,...,A^(m-1)*v}
 ANGLE_ERROR(v,w) := arccos(|v^*w|/(||v||*||w||))
 SUBSPACE_RESIDUAL(A,V,T) := ||A*V-V*T||
}

AXIOMS {
A1 = "An eigenvector is defined only up to multiplication by a nonzero scalar."
 A2 = "Real eigenvector sign and complex eigenvector global phase are not intrinsic."
 A3 = "Repeated eigenvalues can admit multidimensional eigenspaces."
 A4 = "Symmetric and Hermitian matrices admit orthonormal eigenvector bases."
 A5 = "Nonnormal matrices can have highly sensitive eigenvectors."
 A6 = "Eigenvector residual and eigenvector forward error are distinct."
 A7 = "For clustered eigenvalues, invariant-subspace accuracy can be more meaningful than individual eigenvector accuracy."
 A8 = "Eigenvector results require residual, normalisation, conditioning and reproducibility validation."
}

REASONING {
R1_CONTEXT = identify(matrix_structure,eigenvalue_information,sparsity,precision,target_vectors_or_subspace)
 R2_CLASS = classify(right,left,standard,generalised,symmetric,Hermitian,nonsymmetric_problem)
 R3_TARGET = identify(dominant,smallest,interior,clustered_or_selected_eigenvectors)
 R4_METHOD = select(power,inverse,Rayleigh,Schur,Lanczos,Arnoldi,subspace_or_KrylovSchur_method)
 R5_TRANSFORM = if_interior choose(shift_invert,polynomial_or_rational_filter)
 R6_ITERATE = compute_and_normalise_approximate_vectors_or_subspace
 R7_ORTHOGONALITY = maintain_orthogonality_or_biorthogonality_if_required
 R8_CONVERGENCE = track(residuals,angles,Ritz_values,spectral_gap_and_stopping_rule)
 R9_CONDITIONING = assess(separation,nonnormality,left_right_geometry_and_subspace_sensitivity)
 R10_VALIDATION = check(residuals,norms,orthogonality,subspace_angles,reference_vectors,reproducibility)
}

CONSTRAINTS {
C1 = "Direct vector comparison requires resolution of sign or complex phase ambiguity."
 C2 = "Individual eigenvectors associated with repeated eigenvalues are not uniquely defined."
 C3 = "Clustered eigenvalues can make individual eigenvectors sensitive while the invariant subspace remains stable."
 C4 = "Power iteration requires suitable spectral dominance."
 C5 = "Inverse iteration requires stable shifted linear solves."
 C6 = "Lanczos and Arnoldi methods can lose orthogonality in finite precision."
 C7 = "A small residual does not guarantee a small eigenvector angle for poorly separated eigenvalues."
 C8 = "Nonnormal matrices can produce highly sensitive right and left eigenvectors."
 C9 = "Restarting Krylov methods can discard useful subspace information."
 C10 = "Distributed eigenvector computation can be limited by orthogonalisation and communication."
}

SEMANTIC_EQUIVALENCE {
"EigenvectorComputation" <=> "NumericalEigenvectorComputation"
 "RayleighQuotientIteration" <=> "RQI"
 "ImplicitlyRestartedArnoldi" <=> "IRAM"
 "InvariantSubspace" <=> "SpectralInvariantSubspaceInEigenContext"
}

VALIDATION {
V1 = "Matrix structure and eigenproblem class are explicit."
 V2 = "Right versus left eigenvectors are distinguished where relevant."
 V3 = "Eigenvectors are normalised under a documented convention."
 V4 = "Sign or complex phase ambiguity is handled before direct comparison."
 V5 = "Eigenpair residuals are checked."
 V6 = "Orthogonality is checked for symmetric or Hermitian eigenvectors."
 V7 = "Subspace angles are used for repeated or clustered eigenvalues where appropriate."
 V8 = "Conditioning and spectral separation are assessed."
 V9 = "Restart, shift, locking and filtering parameters are documented."
 V10 = "Results are reproducible under documented arithmetic and solver settings."
}

CONFIDENCE {
BASE_CONFIDENCE = 0.99
 EIGENVECTOR_COMPUTATION_DEFINITION = 0.99
 RIGHT_LEFT_EIGENVECTOR_REASONING = 0.99
 INVERSE_ITERATION_REASONING = 0.99
 LANCZOS_REASONING = 0.99
 ARNOLDI_REASONING = 0.99
 SUBSPACE_REASONING = 0.99
 CONDITIONING_REASONING = 0.98
 POLICY = "Reduce confidence when eigenvalue separation, target side, normalisation, phase convention, shift, restart strategy, residual scaling or arithmetic precision are underspecified."
}

AI_CONSUMPTION {
PURPOSES = [SemanticSearch,OntologyGrounding,EigenvectorComputationReasoning,RightEigenvectorReasoning,LeftEigenvectorReasoning,EigenspaceReasoning,InvariantSubspaceReasoning,PowerMethodReasoning,InverseIterationReasoning,RayleighQuotientIterationReasoning,SchurVectorReasoning,LanczosReasoning,ArnoldiReasoning,RitzVectorReasoning,SubspaceIterationReasoning,DeflationReasoning,LockingReasoning,ShiftInvertReasoning,EigenvectorConditioningReasoning,OrthogonalityReasoning,SubspaceAngleReasoning,KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference]
 NORMALISE = ["eigenvector computation -> EigenvectorComputation","right eigenvector -> RightEigenvector","left eigenvector -> LeftEigenvector","RQI -> RayleighQuotientIteration","IRAM -> ImplicitlyRestartedArnoldi"]
}

EXECUTION_RULES {
E1 = "If numerical eigenvectors or invariant subspaces are required, activate EigenvectorComputationOntology."
 E2 = "If the target eigenvalue is dominant, consider power iteration."
 E3 = "If an eigenvalue estimate is available, consider inverse or Rayleigh quotient iteration."
 E4 = "If multiple symmetric or Hermitian eigenvectors are required, preserve orthogonality."
 E5 = "For large sparse symmetric problems, consider Lanczos methods."
 E6 = "For large sparse nonsymmetric problems, consider Arnoldi or Krylov-Schur methods."
 E7 = "For interior eigenvectors, consider shift-and-invert or spectral filtering."
 E8 = "For clustered or repeated eigenvalues, validate invariant subspaces rather than arbitrary basis vectors."
 E9 = "Validate residuals, normalisation, orthogonality or subspace angles, conditioning and reproducibility."
}

RECURSION {
ENTRY = EigenvectorComputation
 EXPAND(EigenvectorComputation) -> [Eigenvector,RightEigenvector,LeftEigenvector,Eigenpair,Eigenspace,InvariantSubspace,PowerMethod,InverseIteration,RayleighQuotientIteration,SchurVector,LanczosMethod,ArnoldiMethod,KrylovSubspace,RitzVector,SubspaceIteration,Deflation,Locking,ShiftAndInvert,EigenResidual,AngleError,SubspaceAngle,EigenvectorConditionNumber,SpectralGap,Separation,PerturbationAnalysis,LossOfOrthogonality,Reorthogonalisation,NumericalStability,FloatingPointArithmetic,MachinePrecision,Convergence,DenseEigensolver,SparseEigensolver,ParallelEigensolver,DistributedEigensolver,Verification,Reproducibility]
 STOP_CONDITION = "Stop when target eigenvectors or subspace, method, convergence, normalisation, conditioning, orthogonality and validation are sufficiently resolved."
}

ROUTING {
PARENT_ONTOLOGY = "Linear Algebra Computation"
 RELATED_ONTOLOGIES = ["Eigenvalue Computation Ontology","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"]
 ROUTE_RULES = ["Eigenvector Computation -> Eigenvalue Computation for eigenpair semantics","Eigenvector Computation -> Numerical Linear Algebra for finite-precision algorithms","Eigenvector Computation -> Matrix Decomposition for Schur vectors","Eigenvector Computation -> Sparse Matrix for large sparse problems","Eigenvector Computation -> Numerical Analysis for perturbation and conditioning"]
}

UPDATE_MODEL {
MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible eigenvector algorithms, subspace methods or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = ["Preserve eigenvalue-versus-eigenvector distinction.","Preserve right-versus-left distinction.","Preserve individual-eigenvector-versus-invariant-subspace distinction.","Preserve sign-or-phase ambiguity.","Preserve residual-versus-angle-error distinction.","Preserve normal-versus-nonnormal behaviour.","Preserve exact-eigenvector-versus-Ritz-vector distinction.","Preserve machine-readable eigenvector semantics."]
}

OUTPUT {
CANONICAL_DEFINITION = "Eigenvector computation numerically determines eigenvectors and invariant subspaces associated with matrix eigenvalues."
 SIDE_SUMMARY = "Right and left eigenvectors encode different spectral directions for general nonsymmetric matrices."
 ITERATIVE_SUMMARY = "Power, inverse and Rayleigh quotient iteration refine selected eigenvectors."
 KRYLOV_SUMMARY = "Lanczos and Arnoldi methods approximate eigenvectors and invariant subspaces through Krylov spaces."
 SUBSPACE_SUMMARY = "For clustered or repeated eigenvalues, invariant-subspace accuracy is often more meaningful than an arbitrary individual eigenvector basis."
 CONDITIONING_SUMMARY = "Spectral separation and nonnormality determine eigenvector sensitivity."
 VALIDATION_SUMMARY = "Eigenvectors should be checked for residuals, normalisation, sign or phase ambiguity, orthogonality or subspace angles, conditioning and reproducibility."
}

FLOW {
INPUT
 -> detect_eigenvector_computation_context
 -> identify_matrix_structure_eigenvalue_information_sparsity_precision_and_target_vectors
 -> classify_right_left_standard_generalised_symmetric_Hermitian_or_nonsymmetric_problem
 -> identify_target_eigenvectors_or_invariant_subspace
 -> select_power_inverse_Rayleigh_Schur_Lanczos_Arnoldi_subspace_or_KrylovSchur_method
 -> apply_shift_invert_or_filtering_if_required
 -> iterate_normalise_and_preserve_orthogonality
 -> track_residuals_angles_Ritz_values_spectral_gap_and_stopping_rule
 -> analyse_conditioning_nonnormality_roundoff_and_subspace_sensitivity
 -> validate_residuals_normalisation_orthogonality_subspace_angles_and_reproducibility
 -> route_to_related_linear_algebra_and_numerical_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
"The Eigenvector Computation Ontology defines numerical determination of right and left eigenvectors and invariant subspaces. It supports eigenspaces, multiplicity, normal and nonnormal matrices, power and inverse iteration, Rayleigh quotient iteration, Schur vectors, Lanczos and Arnoldi methods, Krylov subspaces, Ritz vectors, subspace iteration, deflation, locking and restarting, shift-and-invert and filtering, dense and sparse problems, residuals, vector and subspace errors, conditioning, spectral gaps, perturbation analysis, orthogonality, finite precision, parallel and distributed eigensolvers, verification and reproducibility."
}

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

}

END_FLOW