= Sparse dot product by merging indices
For two <sparse vectors> stored as increasing nonzero-coordinate streams, advance whichever current index is smaller; that coordinate has no possible partner in the other remaining stream. At equal indices, accumulate the product and advance both. The <loop invariant> accounts for all matched coordinates already passed and excludes any future match for skipped smaller coordinates. Termination occurs when either stream ends. The method uses $O(k_1+k_2)$ time and constant <auxiliary space>, with floating-point results subject to the chosen evaluation order.
Back to article page
