Scribd
Upload
31 views5 pages

MapReduce for Matrix Multiplication

The document explains sparse matrices, which have significantly more zero elements than non-zero elements, making them efficient for storage and computation. It details the process of matrix multiplication using MapReduce, including the roles of mappers and reducers to handle non-zero elements. The example provided illustrates how to compute the product of two 2x2 matrices through mapping and reducing steps.

Uploaded by

Maithili Divecha
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
31 views5 pages

MapReduce for Matrix Multiplication

The document explains sparse matrices, which have significantly more zero elements than non-zero elements, making them efficient for storage and computation. It details the process of matrix multiplication using MapReduce, including the roles of mappers and reducers to handle non-zero elements. The example provided illustrates how to compute the product of two 2x2 matrices through mapping and reducing steps.

Uploaded by

Maithili Divecha
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Matrix Multiplication with MapReduce

Sparse matrix
• A sparse matrix is a special case of a matrix in which the number of zero elements
is much higher than the number of non-zero elements.
• As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be
called a sparse matrix.
• Why to use Sparse Matrix instead of simple matrix ?
• Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to
store only those elements.
• Computing time: Computing time can be saved by logically designing a data structure
traversing only non-zero elements.
• Sparse matrix is used while working with matrix–vector multiplication.
• Input file has one-line for each non-zero element Mij of matrix M.
• <M><i><j><mij>
• Let us consider the matrix multiplication example to visualize MapReduce. Consider the following matrix

• Here matrix A is a 2×2 matrix which means the number of rows(i)=2 and the number of columns(j)=2.
• Matrix B is also a 2×2 matrix where number of rows(j)=2 and number of columns(k)=2.
• Each cell of the matrix is labelled as Aij and Bij. Ex. element 3 in matrix A is called A 21 i.e. 2nd-row 1st column.
• Now One step matrix multiplication has 1 mapper and 1 reducer.
• The Formula is:

Mapper for Matrix A (k, v)=((i, k), (A, j, Aij)) for all k
Mapper for Matrix B (k, v)=((i, k), (B, j, Bjk)) for all i
Therefore computing the mapper for Matrix A: Computing the mapper for Matrix B:

# k, i, j computes the number of times it occurs. i=1 j=1 k=1 ((1, 1), (B, 1, 5))
# Here all are 2, therefore when k=1, i can have 2 values k=2 ((1, 2), (B, 1, 6))
1 & 2, each case can have 2 further values of j=1 and j=2 k=1 ((1, 1), (B, 2, 7))
j=2. k=2 ((1, 2), (B, 2, 8))
Substituting all values in formula
i=2 j=1 k=1 ((2, 1), (B, 1, 5))
k=1 i=1 j=1 ((1, 1), (A, 1, 1)) k=2 ((2, 2), (B, 1, 6))
j=2 ((1, 1), (A, 2, 2)) j=2 k=1 ((2, 1), (B, 2, 7))
i=2 j=1 ((2, 1), (A, 1, 3)) k=2 ((2, 2), (B, 2, 8))
j=2 ((2, 1), (A, 2, 4))

k=2 i=1 j=1 ((1, 2), (A, 1, 1))


j=2 ((1, 2), (A, 2, 2))
i=2 j=1 ((2, 2), (A, 1, 3)) The formula for Reducer is:
j=2 ((2, 2), (A, 2, 4))
Reducer (k, v)=(i, k)=>Make sorted Alist and Blist
(i, k) => Summation (Aij * Bjk)) for j
Output =>((i, k), sum)
computing the reducer:
• (1, 1) =>Alist ={(A, 1, 1), (A, 2, 2)}
Blist ={(B, 1, 5), (B, 2, 7)}
Now Aij x Bjk: [(1*5) + (2*7)] =19 -------(i)

From (i), (ii), (iii) and (iv) we conclude that


• (1, 2) =>Alist ={(A, 1, 1), (A, 2, 2)} ((1, 1), 19)
Blist ={(B, 1, 6), (B, 2, 8)} ((1, 2), 22)
Now Aij x Bjk: [(1*6) + (2*8)] =22 -------(ii) ((2, 1), 43)
((2, 2), 50)
• (2, 1) =>Alist ={(A, 1, 3), (A, 2, 4)}
Blist ={(B, 1, 5), (B, 2, 7)}
Now Aij x Bjk: [(3*5) + (4*7)] =43 -------(iii)

• (2, 2) =>Alist ={(A, 1, 3), (A, 2, 4)}


Blist ={(B, 1, 6), (B, 2, 8)}
Now Aij x Bjk: [(3*6) + (4*8)] =50 -------(iv)

You might also like