= Sorted sparse dot product
{title2=$x\cdot y=\sum_{i\in\operatorname{supp}x\cap\operatorname{supp}y}x_i y_i$}
For two <sparse vectors> with the same dimension and sorted nonzero entries, merge their coordinate lists. Equal indices contribute their product and advance both cursors. If one index is smaller, advance only that cursor: the other <vector> has zero at that coordinate, because all its smaller indices have already been processed and all remaining indices are larger. This proves a <loop invariant> consisting of the accumulated <inner product> over settled indices. Every iteration consumes at least one stored entry, giving <time complexity> $O(k_x+k_y+1)$ and constant <auxiliary space> for $k_x,k_y$ nonzero entries. The method avoids work proportional to the ambient dimension. Its <floating-point arithmetic> error remains distinct from its exact <algorithm correctness>.
Back to article page
