Complete Mathematics of "Optimization 1: The `AddDot` Extraction"¶

Optimization 1 keeps the same column-major layout and the same per-row dot-product structure, but extracts the inner dot product into a separate AddDot routine and passes the address of \(A(i,0)\) together with the leading dimension as a stride. This encapsulates the row-dot-product and sets up the pattern that the rest of the ladder refines.

1. The Mathematical Operation¶

Unchanged:

\[ y_i \;\leftarrow\; \sum_{p=0}^{k-1} A_{i,p}\,x_p + y_i, \qquad i=0,\dots,m-1. \]

2. The `AddDot` Routine¶

#define X(i) x[i]
void AddDot(int k, double *a, int stride, double *x, double *gamma){
    for (int p = 0; p < k; p++)
        *gamma += X(p) * a[p*stride];
}

Called from matvec as:

AddDot(k, &A(i,0), lda, x, &y[i]);

2.1 What the pointer `&A(i,0)` means¶

In column-major layout, \(A(i,0) = a[0\cdot\text{lda}+i] = a[i]\). The pointer &A(i,0) is address a + i — the \(i\)-th entry of column 0.

2.2 Why the stride is `lda`¶

Inside AddDot, a[p*stride] with stride = lda computes:

\[ a[p\cdot \text{lda} + i] \;=\; A(i,p). \]

So the p-loop walks across row \(i\) of \(A\): for fixed row \(i\), it reads the elements \(A(i,0), A(i,1), \dots, A(i,k-1)\), each at a stride of lda in the column-major array. The dot product is:

\[ \sum_{p=0}^{k-1} A(i,p)\, x_p. \]

3. The Correct `X(i)` Macro (Contiguity of x)¶

An important correction: the x vector is stored contiguously (length \(k\), stride 1). The macro must be #define X(i) x[i] — not x[(i)*stride]. Applying the A-stride to x would be a bug: it would read x[p*lda], jumping far outside the intended stream. Here X(p)=x[p] correctly reads the contiguous input vector.

Quantity	A element	x element
Address	`p*lda + i` (stride `lda`)	`p` (stride 1)
Stride in loop	\(\text{lda}=m\)	1

4. Memory Access Profile (per row \(i\))¶

Access	Address expression	Stride	Behavior
\(A_{i,p}\)	\(p\cdot\text{lda}+i\)	\(\text{lda}=m\)	strided
\(x_p\)	\(p\)	\(1\)	contiguous
\(y_i\) (gamma)	\(i\)	single	reused

The row of \(A\) is read with stride lda — the same strided matrix access as the naive column-major version. Contiguous-only is \(x\).

5. Function-Call Overhead and Its Negligibility¶

The routine is called once per output element, i.e., \(m\) times. Each call pays one branch and setup, but runs a \(k=2000\)-iteration loop. With -O2 the compiler typically inlines AddDot, removing the call overhead. The encapsulation is primarily for readability and to mirror the matmul ladder's structure; it is not itself an optimization.

6. Why This Is Only a Stepping Stone¶

This version:

still strided-reads \(A\) (stride lda),
still computes one output at a time (single accumulator),
has arithmetic intensity \(O(1)\) and is memory-bound.

Its value is establishing the AddDot idiom — a single accumulator *gamma updated across p — which the following steps will (a) fuse across four rows at once (multi-output kernel, Optimization 7+), (b) hold in registers, and (c) point-advance over packed data.

7. Summary¶

Metric	Naive `gemv_col`	Optim 1 (`AddDot`)
Operation	\(y \mathrel{+}= Ax\)	\(y \mathrel{+}= Ax\)
Layout	column-major	column-major
A access	strided (`lda`)	strided (`lda`)
Outputs at once	1	1
FLOPs	\(2mk\)	\(2mk\)
AddDot extraction	no	yes

Mathematically identical to the naive column-major kernel; the change is purely organizational — extracting the row dot product into AddDot, with the x-macro carefully kept contiguous. The real work of the ladder (multi-output fusion and vectorization) begins later.

Complete Mathematics of "Optimization 1: The AddDot Extraction"¶