Numerical Methods Glossary

Simplest explicit ODE solver: y(t+h) = y(t) + h·f(t,y). First-order accurate (error ∝ h). Can be unstable for stiff problems unless h is small. Used in basic particle systems where stability is not critical.

Updates velocity first (v ← v + a·dt), then position with the new velocity (x ← x + v·dt). Conserves energy better than forward Euler for Hamiltonian systems. Preferred over forward Euler for spring-mass and orbital mechanics.

x(t+h) = 2x(t) - x(t-h) + a(t)·h². Time-reversible, second-order accurate, no explicit velocity needed. Velocity Verlet computes velocity too: v(t+h) = v(t) + (a(t)+a(t+h))·h/2. Standard choice for cloth, hair, rigid body simulations.

Velocity is evaluated at half-step offsets from position; equivalent to Verlet but formulated so velocity is explicit. Used in molecular dynamics and N-body simulations. Symplectic (conserves area in phase space), second-order accurate.

Computes four estimates k1–k4 of the derivative and combines them as y ← y + (k1 + 2k2 + 2k3 + k4)/6 · h. Fourth-order accurate (error ∝ h⁴). Requires 4 function evaluations per step. Workhorse for chaotic ODEs: Lorenz, double pendulum, orbital mechanics.

Adaptive step-size RK solver: computes both 4th- and 5th-order estimates and uses the difference as an error estimate to adjust h automatically. More evaluations per step but fewer total steps when accuracy varies across the trajectory.

Explicit multistep method that reuses derivative evaluations from previous steps. 2nd-order AB: y_{n+1} = y_n + (3f_n - f_{n-1})·h/2. More efficient than RK for smooth functions because past evaluations are recycled.

y(t+h) = y(t) + h·f(t+h, y(t+h)). Requires solving a (possibly nonlinear) equation at each step. Unconditionally stable for linear systems — ideal for stiff physics (fast springs, cloth at high stiffness).

Replaces continuous derivatives with difference quotients on a regular grid. Forward difference: ∂u/∂x ≈ (u_{i+1}-u_i)/h. Central: ≈ (u_{i+1}-u_{i-1})/(2h). Easy to implement, limited to simple domains.

Subdivides domain into small elements (triangles, tetrahedra). The PDE is converted to a weak form over each element and assembled into a global stiffness matrix Ku = f. Handles complex geometries and boundary conditions. Used in structural analysis, fluid mechanics.

Integrates the PDE over control volumes. Fluxes across volume boundaries are conserved exactly. Preferred for conservation laws (Euler/NS equations). Used in CFD, heat transfer.

Reduces dimension by one: only surface (boundary) elements needed instead of volume elements. Highly efficient for unbounded or exterior problems (acoustics, electrostatics). Dense matrix — O(N²) assembly vs O(N) for FEM.

Represents solution as a sum of global basis functions (Fourier, Chebyshev). Exponential convergence for smooth solutions. Used in turbulence simulation, weather modelling, ocean simulations. FFT enables O(N log N) transforms.

Simulates fluid by tracking distribution functions of particle densities on a lattice. Each step: collision (relax toward Maxwell-Boltzmann) + streaming (shift distributions to neighbours). Recovers Navier-Stokes in the macroscopic limit. Naturally parallel, GPU-friendly.

lerp(a, b, t) = a + t·(b - a), t ∈ [0,1]. First degree polynomial connecting two points. Used everywhere: animation blending, texture sampling, per-step physics nudging.

Linear interpolation in two dimensions (4 corner samples → 1 result). Used for texture lookup, grid-based fluid advection. Equivalent to lerping rows then columns.

Cubic polynomial specified by endpoint values AND endpoint derivatives (tangents). C¹ continuous at control points. Used for smooth camera paths, animation curves.

Piecewise cubics with C² continuity (matching second derivatives at joints). Produces the smoothest curve through N points. More expensive than Hermite (need to solve tridiagonal system).

Polynomial curve defined by control points using Bernstein basis. Cubic Bézier: four control points; curve tangent to P0→P1 at start and P2→P3 at end. Used in SVG paths, CSS animations, font outlines.

Interpolation using functions of the distance from data points: f(x) = Σ wᵢ · φ(‖x-xᵢ‖). Common kernels: Gaussian, multiquadric, thin-plate spline. Useful for scattered data; forms basis of SPH kernels.

The error introduced by replacing exact derivatives with finite approximations. For explicit Euler, local truncation error is O(h²); global accumulated error is O(h). Higher-order methods reduce truncation error per step.

Floating-point arithmetic has finite precision (~15–17 decimal digits for double). Accumulated rounding can dominate when subtracting nearly equal numbers (catastrophic cancellation).

A system is stiff when some components change much faster than others. Explicit methods require tiny time steps to stay stable for the fast component, even if only accuracy in the slow component is desired. Implicit methods handle stiffness by solving implicitly, allowing large steps.

Courant-Friedrichs-Lewy: for explicit wave/advection, the time step must satisfy c·Δt/Δx ≤ 1 (1D). Ensures that information doesn't travel more than one cell per step. Guides time-step choice in fluid and wave simulations.

Artificial damping introduced by the discretisation. First-order methods (upwind, forward Euler) are highly dissipative; high-order schemes preserve wave features longer. Useful for stability but suppresses detail in turbulence simulations.

Inserts a Fourier mode ansatz u_j^n = g^n · exp(ikjΔx) into the discretised scheme and checks that the amplification factor g satisfies |g| ≤ 1 for all wavenumbers k. Standard tool for proving stability of FD schemes.

Symplectic integrators (Verlet, leapfrog, symplectic Euler) preserve the symplectic structure of Hamiltonian systems. Total energy oscillates around the correct value rather than drifting, even over long simulations.

Direct solver for Ax = b. Factors A = LU (lower/upper triangular) via elimination. O(N³) for dense N×N matrices. Exact up to round-off. Used for small FEM systems.

Iterative solver for symmetric positive-definite Ax = b. Converges in at most N steps (exact arithmetic) but typically much fewer in practice. Memory-efficient: only matrix-vector products needed. Standard for large sparse FEM systems.

Generalised Minimal Residual — iterative solver for non-symmetric sparse systems. Builds Krylov subspace and minimises residual norm. Used for convection-dominant fluid problems where CG doesn't apply.

Matrix M ≈ A applied to transform Ax = b → M⁻¹Ax = M⁻¹b so that the condition number is reduced, accelerating iterative convergence. Common choices: Jacobi (diagonal M), ILU (incomplete LU factorisation), multigrid.

Specialised Gaussian elimination for tridiagonal systems. O(N) time and memory. Appears in cubic spline fitting, Crank-Nicolson heat equations, and 1D FEM assembly.

Lagrangian method: fluid is a set of particles. Field quantities are interpolated using a kernel W(r,h): A(x) = Σ mⱼ Aⱼ/ρⱼ · W(x-xⱼ, h). Common kernels: cubic spline, Wendland C4. Handles free surfaces naturally; used in our fluid simulation.

The cutoff distance h (smoothing length) beyond which the SPH kernel is zero. Larger h → smoother but less detailed results. Typically set to 2–3 particle spacings. Spatial hashing limits neighbor search to nodes/cells within h.

Maps 3D grid cells to a 1D hash table to efficiently find particles within a given distance. Reduces neighbor search from O(N²) to O(N·k) where k is the average number of neighbors in the support radius.

Predictive-Corrective SPH and Divergence-Free SPH — pressure solvers that enforce incompressibility more accurately than the original pressure-state equation. Divergence-Free SPH also corrects velocity divergence, reducing volume errors by 2–3 orders of magnitude.