3.4 Exact Algorithms vs Implemented Algorithms

3.4 Exact Algorithms vs Implemented Algorithms

When we learn algorithms from textbooks, we are introduced to the clean, idealized versions: perfect arithmetic, exact divisions, infinite precision, no rounding, and no constraints imposed by hardware or memory layouts. In this world, algorithms behave beautifully. They do exactly what we expect.

But the moment we implement those algorithms on real machines, something fundamental changes. The algorithm we think we are running, and the algorithm the computer is actually running, are not the same thing.

Understanding this difference is one of the defining skills of numerical computing. Many failures in AI systems, optimization pipelines, simulations, and statistical models arise because the engineer focuses on the “textbook algorithm,” while the machine is executing something subtly—but critically—different.

The Platonic Ideal vs the Hardware Reality

A textbook algorithm lives in a universe without constraints. It assumes:

• Real numbers exist and can be represented exactly
• Arithmetic operations have infinite precision
• No rounding, truncation, or cancellation occurs
• No intermediate value ever overflows or underflows
• Operations occur in exact order and exact form

Computers live in a completely different world:

• Numbers are stored in IEEE 754 floating-point format
• Many real numbers cannot be represented exactly
• Arithmetic is approximate and includes rounding
• Certain expressions amplify error dramatically
• Reordering operations changes results

This gap is the source of nearly every numerical surprise a system can produce.

Why “Same Algorithm” Does Not Mean “Same Computation”

Consider a simple example: summing a list of numbers. On paper, the sum

a + b + c + d

is just a sum. Order does not matter. On a computer, the grouping

(a + b) + (c + d)

may produce a different result than

a + (b + (c + d))

Why? Because each intermediate result is rounded, and the rounding depends on magnitude differences between operands. Floating-point addition is not associative.

Textbook: (a + b) + c = a + (b + c) Machine: (a + b) + c ≠ a + (b + c)

This is not a bug in the CPU—this is floating-point arithmetic behaving exactly as defined.

Algorithmic “Equivalence” Breaks in Practice

Many algorithms that are mathematically equivalent produce wildly different numerical behavior when implemented. For example:

• Computing a derivative: (f(x+h) - f(x)) / h is exact in calculus—but numerically unstable for small h.
• Computing least-squares: solving (AᵀA)x = Aᵀb is mathematically valid—but produces poor results due to squared condition numbers.
• Computing x - y: if x and y are close, catastrophic cancellation destroys significant digits.
• Solving linear systems: Gaussian elimination without pivoting is elegant—but can catastrophically fail due to rounding error accumulation.

The moral: Mathematically equivalent ≠ Numerically equivalent.

Exact Algorithms Are Roadmaps. Implemented Algorithms Are Machinery.

An exact algorithm describes the intended transformation:

What operations should be performed to solve the mathematical problem?

An implemented algorithm describes:

How those operations behave under floating-point constraints, memory layouts, data access patterns, and machine architecture.

Understanding this distinction allows you to:

• Select algorithms that remain stable under floating-point arithmetic
• Use reformulations to reduce error amplification
• Predict points of numerical fragility before they occur
• Recognize when a mathematically correct algorithm will fail in practice
• Detect when instability arises from problem conditioning vs algorithmic execution

Case Study: Solving Ax = b

On paper, solving Ax = b can be expressed through:

• Direct inversion: x = A⁻¹b
• Gaussian elimination
• LU decomposition
• QR decomposition

Mathematically, these are equivalent: all give the exact solution. Numerically, they behave very differently:

• Matrix inversion is numerically unstable and almost never used in practice.
• Gaussian elimination without pivoting fails often; with pivoting, it is reasonably stable.
• QR decomposition is more stable for least-squares and ill-conditioned matrices.
• SVD is the most stable—but computationally expensive.

The lesson: The machine chooses winners based on stability—not elegance.

How Engineers Bridge the Gap

Practitioners use a variety of tools to ensure that the implemented algorithm behaves as intended:

• Pivoting to control error in factorization
• Rewriting formulas to avoid cancellation
• Scaling and normalization to improve conditioning
• Using QR or SVD instead of unstable normal equations
• Adopting compensated summation to reduce rounding error
• Choosing stable recurrence relations instead of unstable explicit formulas

This is the art of numerical computing: knowing when the algorithm must be adapted to survive the environment in which it runs.

Why This Distinction Matters in AI and Modern Computation

LLMs, vector search systems, ML training, kernel methods, and large-scale optimizers all rely heavily on linear algebra. And they inherit the numerical quirks of that algebra.

Engineers sometimes assume that because an algorithm is mathematically valid, it will behave well in practice. Many catastrophic AI failures contradict that belief:

• embeddings drifting due to accumulation of rounding error
• gradient updates diverging due to unstable recurrence relations
• ill-conditioned covariance matrices causing NaNs
• catastrophic cancellation affecting normalization layers

These failures are not mysterious. They are symptoms of the gap between the algorithm on the page and the algorithm in the machine.

Transition: Toward the Heart of Numerical Linear Algebra

We now understand the structure of computation:

• how floating-point arithmetic shapes accuracy,
• how norms and errors measure reliability,
• how conditioning defines inherent difficulty,
• and how implemented algorithms differ from their ideal versions.

With this foundation, we can now step into the most fundamental operation in numerical linear algebra: solving linear systems.

Every machine learning pipeline, every simulation, every optimization routine depends on efficiently solving equations of the form Ax = b. The choice of method determines speed, stability, and reliability at scale.

Let’s now enter the core of practical computation:
4.0 Solving Ax = b