§ 2.6Module 2

Matrix-Vector Multiplication by MapReduce

On this page

2.6 Matrix–Vector Multiplication by MapReduce

Recall first

For y = A v, what is y_i? If a matrix entry is A[i,j], which vector value must travel with it?

First principles

For an m × n matrix A and an n-element vector v:

y_i = \sum_{j=1}^{n} A_{ij}v_j, \quad i=1,\ldots,m.

The result can be distributed by row. Store each nonzero matrix entry as (i,j,aij). A mapper looks up v_j, computes the partial product aij × v_j, and emits key i. The reducer receives all partial products for row i and sums them.

This is a MapReduce expression of the matrix-vector method discussed in Mining of Massive Datasets, Chapter 2. It is especially useful for a sparse matrix: do not materialize zero entries.

Algorithm

Input: entries (i,j,aij) and vector v.

map((i,j,aij)):
    emit(i, aij * v[j])

reduce(i, partials):
    emit(i, sum(partials))

The vector must be available to every mapper, for example as a small read-only distributed file/cache, or by a preceding distribution step. If the vector is too large for convenient broadcast, use a block/partitioned algorithm that joins matrix blocks with the needed vector pieces; the simple algorithm’s communication assumption then changes.

Worked trace

Let

A = \begin{bmatrix} 1&2&0\ 0&3&4 \end{bmatrix}, \quad v = \begin{bmatrix} 5\ 6\ 7 \end{bmatrix}.

Nonzero entries produce:

map (1,1,1) -> (1, 1*5) = (1,5)
map (1,2,2) -> (1, 2*6) = (1,12)
map (2,2,3) -> (2, 3*6) = (2,18)
map (2,3,4) -> (2, 4*7) = (2,28)

Grouping gives 1 → [5,12] and 2 → [18,28]. Reducers emit y_1=17 and y_2=46, so y=[17,46]^T.

Assumptions and trade-offs

Matrix entries can be processed independently once the needed vector value is available.
Addition is associative, so local partial sums can be combined safely.
The vector is read by many mappers: broadcasting is cheap only when the vector fits the distribution mechanism and network budget.
The result is one key per row, so an unusually dense row can create a reducer hotspot.
One MapReduce round computes one multiplication; iterative algorithms such as repeated PageRank need many rounds and repeatedly materialize state, which is a performance limitation.

Exercise — revealed answer

Exercise: For entries (2,1,3) and (2,3,5) with v_1=4 and v_3=10, what does reducer 2 emit?

Answer: The mapper emits (2,12) and (2,50). Reducer 2 sums them and emits (2,62).

Exam lens

Write the formula first, then the two lines mapper emits (row, partial); reducer sums by row. State how the vector reaches mappers and why sparse input avoids zero work. A small numerical trace prevents a vague answer.

Rapid revision checklist

Write y_i = Σ_j Aij vj.
Identify mapper key as row i.
Compute partial products using v_j.
Sum by row in the reducer.
Mention vector broadcast, sparsity, skew, and iterative-round costs.

Key takeaways

MapReduce turns each matrix entry into a row-keyed partial product.
The reducer reconstructs one output coordinate by summing that row’s contributions.
The simple algorithm is efficient when the vector is distributable and the matrix is sparse enough.

Sources

Mining of Massive Datasets — online book.
Apache Hadoop MapReduce Tutorial.
Google MapReduce paper.
Syllabus-aligned supplement: the sparse-entry notation and broadcast assumption are an exam-oriented elaboration of the matrix-vector MapReduce algorithm; the cited online MMDS text is the primary topic source.