Scientific computing and algorithms
How computers represent numbers, how fast algorithms grow, how they manipulate formulas and how they estimate what cannot be computed exactly.
5 topics
Topics
Floating point (IEEE 754)
The finite approximation of the real numbers used by every computer: with a 53-bit mantissa in double precision. About 16 significant digits, relative rounding error at most , and a zoo of pitfalls: cancellation, overflow, non-associativity.
Algorithm analysis and complexity
Predicting how the resources of an algorithm grow with the input size. Its tools are pure calculus of sequences: asymptotic notation, limits, sums and integrals, logarithms and exponentials, recurrences.
Symbolic computation (CAS)
Programs that manipulate formulas exactly: simplify, differentiate, integrate, expand in series, solve. Calculus as term rewriting on expression trees.
Scientific computing
The discipline of turning mathematical models into reliable numbers: discretize, solve, estimate the error, repeat. Root-finding, quadrature, ODE/PDE solvers and their error analysis are its everyday tools.
Monte Carlo methods
Estimate an integral (an expectation) by averaging a function at random points. The error is whatever the dimension, which makes it the only practical method for high-dimensional integrals: rendering, Bayesian statistics, physics, finance.
The mathematics this domain runs on
ƒ Foundations ★★★★★
- Real numbers★★★★★→Floating point (IEEE 754), Symbolic computation (CAS)
- Logarithmic functions★★★★★→Floating point (IEEE 754), Algorithm analysis and complexity
- Inequalities★★★★★→Algorithm analysis and complexity
- Inverse functions★★★★★→Monte Carlo methods
- Exponential functions★★★★★→Algorithm analysis and complexity
- Functions★★★★★→Symbolic computation (CAS)
- Domain and range★★★★★→Floating point (IEEE 754)
- Polynomial functions★★★★★→Algorithm analysis and complexity
- +1
lim Sequences and limits ★★★★★
- Limits at infinity★★★★★→Algorithm analysis and complexity
- Orders of growth★★★★★→Algorithm analysis and complexity
- Asymptotic notation (O, o, Ω, Θ)★★★★★→Algorithm analysis and complexity, Scientific computing, Monte Carlo methods
- Sequences★★★★★→Algorithm analysis and complexity, Scientific computing
- Convergence of sequences★★★★★→Scientific computing
- Limit of a function★★★★★→Floating point (IEEE 754), Algorithm analysis and complexity
- Infinitesimals and equivalences★★★★★→Floating point (IEEE 754)
- Infinite limits★★★★★→Floating point (IEEE 754)
f′ Derivatives ★★★★★
≈ Numerical methods ★★★★★
- Absolute and relative error★★★★★→Floating point (IEEE 754), Scientific computing
- Conditioning★★★★★→Scientific computing
- Numerical stability★★★★★→Floating point (IEEE 754)
- Order of convergence★★★★★→Scientific computing
- Newton's method★★★★★→Floating point (IEEE 754), Scientific computing
- Numerical integration (quadrature)★★★★★→Scientific computing
- Bisection method★★★★★→Algorithm analysis and complexity, Scientific computing
- Fixed-point iteration★★★★★→Scientific computing
Tₙ Taylor series ★★★★★
∫ Integrals ★★★★★
Σ Series ★★★★★
- Geometric series★★★★★→Algorithm analysis and complexity
- Numerical series★★★★★→Algorithm analysis and complexity, Scientific computing
- Integral test★★★★★→Algorithm analysis and complexity
- Comparison tests★★★★★→Algorithm analysis and complexity
- Absolute and conditional convergence★★★★★→Floating point (IEEE 754)
- Alternating series★★★★★→Floating point (IEEE 754)