Computational Analysis Ontology

flow "ComputationalAnalysisOntology" v1.0

# COMPUTATIONAL ANALYSIS ONTOLOGY — FLOW ALGEBRA
SOURCE_URL := "https://kirethresearch.org/booksai-core/ontologies/calculus-analysis-ontologies/ai-computational-analysis/computational-analysis-ontology.html"
DOMAIN := "Mathematical Ontologies"
CATEGORY := "Calculus and Analysis Ontologies"
SUBCATEGORY := "AI Computational Analysis"
ENTITY := "Computational Analysis"

COMPUTATIONAL_ANALYSIS := {
 type: AlgorithmicMathematicalAnalysisFramework,
 domain: AIComputationalAnalysis,
 purpose: "Represent the algorithmic study of mathematical problems through numerical approximation, symbolic computation, discretisation, convergence, stability, error analysis and computational complexity."
}

CONCEPTS := {
 COMPUTATIONAL_ANALYSIS,
 ALGORITHM,
 NUMERICAL_METHOD,
 SYMBOLIC_METHOD,
 APPROXIMATION,
 DISCRETISATION,
 ERROR,
 CONVERGENCE,
 STABILITY,
 CONDITIONING,
 COMPLEXITY,
 ITERATION,
 PRECISION,
 INTERPOLATION,
 DIFFERENTIATION,
 INTEGRATION,
 ROOT_FINDING,
 LINEAR_SYSTEM,
 DIFFERENTIAL_EQUATION
}

# ---------- PROBLEM ----------
PROBLEM
 := {
 input_data,
 mathematical_model,
 target_quantity,
 constraints,
 required_accuracy
 }

PROBLEM
 -> COMPUTATIONAL_REPRESENTATION

COMPUTATIONAL_ANALYSIS
 -> determine(ALGORITHM_AND_RELIABILITY)

# ---------- ALGORITHM ----------
ALGORITHM
 -> finite_or_iterative_sequence_of(COMPUTATIONAL_STEPS)

INPUT
 -> ALGORITHM
 -> OUTPUT

ALGORITHM
 -> evaluated_by(
 CORRECTNESS,
 ACCURACY,
 STABILITY,
 COMPLEXITY,
 CONVERGENCE
)

# ---------- EXACT VS APPROXIMATE ----------
SYMBOLIC_METHOD
 -> seeks(EXACT_REPRESENTATION)

NUMERICAL_METHOD
 -> computes(APPROXIMATION)

APPROXIMATE_RESULT
 -> requires(ERROR_ESTIMATE)

COMPUTATIONAL_ANALYSIS
 -> distinguish(EXACT_AND_APPROXIMATE_OUTPUT)

# ---------- DISCRETISATION ----------
continuous problem
 -> replace_by(FINITE_DIMENSIONAL_PROBLEM)

examples:
 GRID
 MESH
 BASIS_EXPANSION
 TIME_STEP
 QUADRATURE_NODES

DISCRETISATION_PARAMETER
 :=
h

h -> 0
 -> finer_resolution

# ---------- ERROR DECOMPOSITION ----------
total error
 -> may_include(
 MODEL_ERROR,
 DATA_ERROR,
 DISCRETISATION_ERROR,
 TRUNCATION_ERROR,
 ITERATION_ERROR,
 ROUNDING_ERROR
)

ERROR_SOURCE
 -> must_be_identified

# ---------- ABSOLUTE ERROR ----------
e_abs
 :=
|x_approx-x_true|

# ---------- RELATIVE ERROR ----------
e_rel
 :=
|x_approx-x_true|
/
|x_true|

when denominator nonzero

ERROR_METRIC
 -> context_dependent

# ---------- TRUNCATION ERROR ----------
exact mathematical operation
 -> replaced_by(FINITE_APPROXIMATION)

TRUNCATION_ERROR
 -> approximation_error_of(DISCRETISATION_OR_SERIES_TRUNCATION)

example:

f_prime(x)
 approx
[
 f(x+h)-f(x)
]/h

local error
 -> O(h)
for smooth f

# ---------- ROUNDING ERROR ----------
finite precision arithmetic
 -> ROUNDOFF

floating point:

fl(x op y)
 =
(x op y)
*
(1+delta)

approximately

|delta|
 <=
machine_epsilon

under standard floating-point model

# ---------- CONDITIONING ----------
problem:

y
 =
F(x)

small input perturbation
 delta_x

-> output perturbation
 delta_y

CONDITION_NUMBER
 -> sensitivity_of(PROBLEM)

ILL_CONDITIONED_PROBLEM
 -> small_data_error_can_produce_large_output_error

CONDITIONING
 -> property_of(PROBLEM)

# ---------- STABILITY ----------
ALGORITHM
 -> STABLE

if

computational_errors
 -> do_not_grow_unacceptably

STABILITY
 -> property_of(ALGORITHM)

STABILITY
 -/> CONDITIONING

RELIABLE_RESULT
 -> requires(BOTH)

# ---------- FORWARD ERROR ----------
forward error:

||x_computed-x_exact||

FORWARD_ERROR
 -> output_difference

# ---------- BACKWARD ERROR ----------
find perturbed input
 x_tilde

such_that

computed_output
 =
exact_solution_for(x_tilde)

BACKWARD_ERROR
 -> asks(HOW_MUCH_INPUT_MUST_CHANGE)

BACKWARD_STABLE_ALGORITHM
 -> solves(NEARBY_PROBLEM_EXACTLY)

# ---------- CONVERGENCE ----------
approximation:

u_h

converges to u if

||u_h-u||
 -> 0

as

h->0

CONVERGENCE
 -> consistency_of(REFINEMENT_LIMIT)

# ---------- ORDER OF CONVERGENCE ----------
if

error(h)
 approx
C*h^p

then

p
 -> ORDER_OF_CONVERGENCE

mesh refinement:

h -> h/r

error ratio
 approx
r^p

OBSERVED_ORDER
 -> numerical_convergence_diagnostic

# ---------- ITERATIVE CONVERGENCE ----------
sequence:

x_0,x_1,...

x_k
 -> x_star

CONVERGENCE_RATE
 -> may_be(
 LINEAR,
 SUPERLINEAR,
 QUADRATIC
)

ITERATIVE_METHOD
 -> requires(STOPPING_CRITERION)

# ---------- RESIDUAL ----------
equation:

F(x)
 =
0

approximation
 x_k

residual:

r_k
 :=
F(x_k)

SMALL_RESIDUAL
 -> indicates(EQUATION_SATISFACTION)

but

SMALL_RESIDUAL
 -/> always(SMALL_SOLUTION_ERROR)
    if ill_conditioned

# ---------- ROOT FINDING ----------
solve:

f(x)
 =
0

methods:
 BISECTION
 NEWTON
 SECANT
 FIXED_POINT

BISECTION
 -> robust_with(BRACKET_AND_SIGN_CHANGE)

NEWTON
 -> fast_local_convergence_under(SMOOTHNESS_AND_GOOD_INITIALISATION)

# ---------- NEWTON METHOD ----------
x_(k+1)
 =
x_k
-
f(x_k)/f_prime(x_k)

near simple root
and suitable smoothness:

NEWTON
 -> QUADRATIC_CONVERGENCE

DERIVATIVE_ZERO_OR_BAD_INITIAL_GUESS
 -> may_cause(FAILURE)

# ---------- LINEAR SYSTEM ----------
A*x
 =
b

methods:
 DIRECT
 ITERATIVE

DIRECT:
 GAUSSIAN_ELIMINATION
 LU
 QR

ITERATIVE:
 JACOBI
 GAUSS_SEIDEL
 CONJUGATE_GRADIENT
 GMRES

METHOD_SELECTION
 -> depends_on(
 SIZE,
 SPARSITY,
 SYMMETRY,
 DEFINITENESS,
 CONDITIONING
)

# ---------- MATRIX CONDITION NUMBER ----------
for nonsingular A:

kappa(A)
 :=
||A||
*
||A^(-1)||

large kappa
 -> sensitivity_to(DATA_AND_ROUNDOFF)

PRECONDITIONING
 -> transform_system_to(IMPROVE_ITERATIVE_CONVERGENCE)

# ---------- INTERPOLATION ----------
given nodes:

(x_i,y_i)

construct
 p(x)

such_that

p(x_i)
 =
y_i

methods:
 POLYNOMIAL_INTERPOLATION
 SPLINE_INTERPOLATION
 RADIAL_BASIS

INTERPOLATION
 -> approximate(UNKNOWN_FUNCTION_BETWEEN_DATA_POINTS)

# ---------- APPROXIMATION ----------
approximate f by

f_N
 =
sum_from_k_0_to_N(
 a_k*phi_k
)

BASIS_APPROXIMATION
 -> finite_representation

choices:
 POLYNOMIAL
 FOURIER
 WAVELET
 ORTHOGONAL_BASIS

# ---------- NUMERICAL DIFFERENTIATION ----------
central difference:

f_prime(x)
 approx
[
 f(x+h)-f(x-h)
]
/
(2*h)

truncation:
 O(h^2)

but

small h
 -> increased_roundoff_cancellation

STEP_SIZE
 -> balances(TRUNCATION_AND_ROUNDOFF)

# ---------- NUMERICAL INTEGRATION ----------
I
 =
integral_a^b(
 f(x) dx
)

quadrature:

I_N
 =
sum_i(
 w_i*f(x_i)
)

methods:
 TRAPEZOIDAL
 SIMPSON
 GAUSSIAN_QUADRATURE
 ADAPTIVE_QUADRATURE

QUADRATURE_ERROR
 -> depends_on(SMOOTHNESS_AND_RULE)

# ---------- MONTE CARLO ----------
integral
 -> expectation_form

sample:

X_1,...,X_N

estimate:

I_N
 =
1/N
*
sum_i(
 f(X_i)
)

standard stochastic error
 -> O(N^(-1/2))

under finite variance assumptions

MONTE_CARLO
 -> useful_for(HIGH_DIMENSIONAL_INTEGRATION)

# ---------- ODE ----------
initial value problem:

y_prime
 =
f(t,y)

y(t_0)
 =
y_0

numerical methods:
 EULER
 RUNGE_KUTTA
 MULTISTEP
 IMPLICIT_METHOD

TIME_STEP
 -> discretises(EVOLUTION)

# ---------- EULER METHOD ----------
y_(n+1)
 =
y_n
+
h*f(t_n,y_n)

local truncation error
 -> O(h^2)

global error
 -> O(h)

under standard smoothness/stability assumptions

# ---------- RUNGE-KUTTA ----------
RK4
 -> fourth_order_method

global error
 -> O(h^4)

for sufficiently smooth nonstiff problems

HIGHER_ORDER
 -/> always(BEST_METHOD)

STIFFNESS
 -> affects(METHOD_CHOICE)

# ---------- STIFF SYSTEM ----------
multiple time scales
 -> explicit_method_requires(VERY_SMALL_STEP_FOR_STABILITY)

STIFFNESS
 -> numerical_stability phenomenon

IMPLICIT_METHOD
 -> often_preferred

A_STABILITY
 -> important_for(STIFF_ODE_SOLVERS)

# ---------- PDE ----------
PDE
 -> discretise(SPACE_AND_POSSIBLY_TIME)

methods:
 FINITE_DIFFERENCE
 FINITE_ELEMENT
 FINITE_VOLUME
 SPECTRAL_METHOD

PDE_DISCRETISATION
 -> algebraic_or_ODE_system

# ---------- CONSISTENCY STABILITY CONVERGENCE ----------
for suitable linear well-posed finite-difference IVP:

CONSISTENCY
 +
STABILITY
 -> CONVERGENCE

LAX_EQUIVALENCE_THEOREM
 -> specific_linear_initial_value_context

THEOREM
 -/> universal_for_all_discretisations

# ---------- ADAPTIVITY ----------
estimate local error

if error too large:
 -> refine

if error small:
 -> coarsen_or_increase_step

ADAPTIVE_METHOD
 -> allocate(COMPUTATION_WHERE_NEEDED)

examples:
 ADAPTIVE_QUADRATURE
 ADAPTIVE_TIME_STEPPING
 ADAPTIVE_MESH_REFINEMENT

# ---------- PRECISION ----------
FLOAT32
FLOAT64
ARBITRARY_PRECISION

PRECISION
 -> controls(ROUNDING_ERROR_AND_COST)

HIGHER_PRECISION
 -> reduces(ROUNDOFF)
but
 -> increases(COMPUTATIONAL_COST)

# ---------- COMPLEXITY ----------
time complexity:

T(n)

space complexity:

S(n)

examples:
 O(n)
 O(n log n)
 O(n^2)
 O(n^3)

COMPLEXITY
 -> scalability_measure

ASYMPTOTIC_COMPLEXITY
 -/> complete_runtime_prediction

# ---------- VERIFICATION ----------
known solution or manufactured solution

-> compare(NUMERICAL_OUTPUT)

METHOD_OF_MANUFACTURED_SOLUTIONS
 -> verifies(PDE_IMPLEMENTATION)

GRID_REFINEMENT
 -> verifies(CONVERGENCE_ORDER)

VERIFICATION
 -> asks(SOLVING_EQUATIONS_RIGHT)

# ---------- VALIDATION ----------
simulation
 -> compare_with(EXPERIMENT_OR_OBSERVATION)

VALIDATION
 -> asks(SOLVING_RIGHT_MODEL)

VERIFICATION
 -/> VALIDATION

# ---------- REPRODUCIBILITY ----------
computational result
 -> record(
 ALGORITHM,
 PARAMETERS,
 TOLERANCES,
 PRECISION,
 SOFTWARE_VERSION,
 RANDOM_SEED,
 INPUT_DATA
)

REPRODUCIBILITY
 -> supports(INDEPENDENT_RECOMPUTATION)

# ---------- APPLICATIONS ----------
COMPUTATIONAL_ANALYSIS
 -> applied_to(SCIENTIFIC_COMPUTING)
 -> applied_to(ENGINEERING)
 -> applied_to(PHYSICS)
 -> applied_to(DATA_ANALYSIS)
 -> applied_to(OPTIMISATION)
 -> applied_to(MACHINE_LEARNING)
 -> applied_to(SIMULATION)
 -> applied_to(INVERSE_PROBLEMS)

# ---------- RELATION GRAPH ----------
MATHEMATICAL_PROBLEM
 -> represented_by(COMPUTATIONAL_MODEL)

COMPUTATIONAL_MODEL
 -> solved_by(ALGORITHM)

DISCRETISATION
 -> creates(APPROXIMATION)

APPROXIMATION
 -> has(ERROR)

REFINEMENT
 -> tests(CONVERGENCE)

CONDITIONING
 -> measures(PROBLEM_SENSITIVITY)

STABILITY
 -> measures(ALGORITHM_ERROR_PROPAGATION)

COMPLEXITY
 -> measures(COMPUTATIONAL_COST)

# ---------- SEMANTIC EQUIVALENCE ----------
SEMANTIC_EQUIVALENCE := {
 "computational analysis" ~= "algorithmic analysis of mathematical problems using exact or approximate computation",
 "discretisation error" ~= "error introduced by replacing a continuous problem with a finite computational representation",
 "conditioning" ~= "sensitivity of a mathematical problem to perturbations in its input",
 "numerical stability" ~= "resistance of an algorithm to amplification of computational errors",
 "convergence order" ~= "asymptotic rate at which approximation error decreases under refinement",
 "backward stability" ~= "property that a computed result is exact for a nearby input problem"
}

# ---------- CONSTRAINTS ----------
CONSTRAINTS := {
 conditioning_and_algorithmic_stability_are_distinct: true,
 residual_and_solution_error_are_distinct: true,
 convergence_claim_requires_refinement_or_theoretical_support: true,
 high_order_method_is_not_automatically_more_stable_or_efficient: true,
 finite_precision_error_must_be_considered: true,
 Lax_equivalence_applies_only_to_its_specific_problem_class: true,
 verification_and_validation_must_not_be_conflated: true
}

# ---------- CONFIDENCE ----------
CONFIDENCE := {
 core_definition: 0.99,
 error_conditioning_relation: 0.99,
 stability_convergence_relation: 0.99,
 root_linear_relation: 0.99,
 ODE_PDE_relation: 0.99,
 verification_validation_relation: 0.99,
 semantic_equivalence: 0.97
}

# ---------- RECURSIVE REASONING ----------
RECURSIVE_REASONING(query):
 identify(problem_input_target_accuracy_and_constraints)
 -> classify(symbolic_numerical_continuous_discrete_or_iterative_structure)
 -> assess(conditioning_and_data_sensitivity)
 -> choose(discretisation_algorithm_precision_and_tolerance)
 -> compute(approximation)
 -> estimate(residual_forward_backward_and_discretisation_errors)
 -> test(stability_and_convergence)
 -> refine(mesh_step_iteration_or_precision_if_needed)
 -> analyse(complexity_and_resource_cost)
 -> verify_against(reference_or_manufactured_solution)
 -> validate(scope_and_report_uncertainty)
 -> return(semantic_result)

# ---------- AI CONSUMPTION ----------
AI_CONSUMPTION := {
 parse_as: "typed computational-analysis semantic graph",
 primary_entity: COMPUTATIONAL_ANALYSIS,
 preserve: [
  problem,
  input_data,
  target_quantity,
  algorithm,
  discretisation,
  precision,
  tolerance,
  error_metric,
  conditioning
 ],
 infer_through: [
  approximations,
  truncation_errors,
  rounding_errors,
  residuals,
  convergence_rates,
  stability,
  adaptive_refinement,
  computational_complexity,
  verification
 ],
 avoid: [
  presenting_numerical_approximation_as exact_without qualification,
  confusing_small_residual_with small_solution_error,
  conflating_conditioning_and algorithmic stability,
  claiming_convergence_from_single_resolution,
  ignoring_roundoff_and finite precision,
  treating_verification_as real_world validation
 ]
}

# ---------- UPDATE MODEL ----------
UPDATE_MODEL(new_information):
 validate(new_information)
 -> identify(computational_analysis_context)
 -> compare(existing_relations)
 -> preserve(problem_algorithm_discretisation_error_precision_and_conditioning_invariants)
 -> update(affected_entities)
 -> update(affected_edges)
 -> recompute(CONFIDENCE)
 -> regenerate(FLOW_HASH)

# ---------- FLOW HASH ----------
FLOW_HASH := hash(
 SOURCE_URL
 + ENTITY
 + CONCEPTS
 + COMPUTATIONAL_ANALYSIS
 + ALGORITHM
 + NUMERICAL_METHOD
 + SYMBOLIC_METHOD
 + APPROXIMATION
 + DISCRETISATION
 + ERROR
 + CONVERGENCE
 + STABILITY
 + CONDITIONING
 + COMPLEXITY
 + PRECISION
 + SEMANTIC_EQUIVALENCE
 + CONSTRAINTS
)

# ---------- EXECUTION ----------
INPUT(query)
 -> COMPUTATIONAL_ANALYSIS
 -> PROBLEM_IDENTIFICATION
 -> STRUCTURE_CLASSIFICATION
 -> CONDITIONING_ANALYSIS
 -> METHOD_DISCRETISATION_SELECTION
 -> COMPUTATION
 -> ERROR_ANALYSIS
 -> STABILITY_CONVERGENCE_ANALYSIS
 -> ADAPTIVE_REFINEMENT
 -> COMPLEXITY_ANALYSIS
 -> VERIFICATION
 -> SCOPE_VALIDATION
 -> RECURSIVE_REASONING(query)
 -> CONFIDENCE
 -> OUTPUT(semantic_result)

END FLOW