58
Comment: converted to 1.6 markup

← Revision 3 as of 20091012 09:24:42 ⇥
3791

Deletions are marked like this.  Additions are marked like this. 
Line 4:  Line 4: 
== Performance Models ==  == M/R Algorithms == === Basic Algorithms === ==== Addition ==== ==== Addition of multiple matrices ==== * https://issues.apache.org/jira/browse/HAMA154 ==== Multiplication ==== * Iterative Approach {{{ For i = 0 step 1 until N 1 Job: Computes the ith row of C = MatrixVector multiplication Iterative job:  A map task receives a row n of B as a key, and vector of row as its value  Multiplying by all columns of ith row of A  Reduce task find and add the ith product 1st + + + +  a11 a12 a13   a11 a21 a31   ... ... ...  X  a12 a22 a32   ... ... ...   a13 a23 a33  + + + + 2nd + + + +  ... ... ...   a11 a21 a31   a21 a22 a23  X  a12 a22 a32   ... ... ...   a13 a23 a33  + + + + .... }}} * Blocking Algorithm Approach To mutliply two dense matrices A and B, We collect the blocks to 'collectionTable' firstly using map/reduce. Rows are named as c(i, j) with sequential number ((N^2 * i) + ((j * N) + k) to avoid duplicated records. {{{ CollectionTable: matrix A matrix B + block(0, 0)0 block(0, 0) block(0, 0) block(0, 0)1 block(0, 1) block(1, 0) block(0, 0)2 block(0, 2) block(2, 0) ... N ... block(N1, n1)(N^31) block(N1, N1) block(N1, N1) }}} Each row has a two sub matrices of a(i, k) and b(k, j) so that minimized data movement and network cost. {{{ Blocking jobs: Collect the blocks to 'collectionTable' from A and B.  A map task receives a row n as a key, and vector of each row as its value  emit (blockID, subvector) pairs  Reduce task merges block structures based on the information of blockID Multiplication job:  A map task receives a blockID n as a key, and two submatrices of A and B as its value  Multiply two submatrices: a[i][j] * b[j][k]  Reduce task computes sum of blocks  c[i][k] += multiplied blocks }}} ==== Matrix Norm ==== * Find the maximum absolute row sum of matrix Matrix.Norm.One is that find the maximum absolute row sum of matrix. Comparatively, it's a good fit with !MapReduce model because doesn't need iterative jobs or table/file JOIN operations. {{{ j=n The maximum absolute row sum = max ( sum  a_{i,j}  ) 1<=i<=n j=1  A map task receives a row n as a key, and vector of each row as its value  emit (row, the sum of the absolute value of each entries)  Reduce task select the maximum one }}} NOTE: Matrix.infinity, Matrix.Maxvalue and Matrix.Frobenius are almost same with this. ==== Compute the transpose of matrix ==== The transpose of a matrix is another matrix in which the rows and columns have been reversed. The matrix must be square for this work. {{{ + + + +  a11 a12 a13   a11 a21 a31   a21 a22 a23  =>  a12 a22 a32   a31 a32 a33   a13 a23 a33  + + + +  A map task receives a row n as a key, and vector of each row as its value  emit (Reversed index, the entry with the given index)  Reduce task sets the reversed values }}} ==== Compute the determinant of square matrix ==== * http://issues.apache.org/jira/browse/HAMA66 === Decomposition Algorithms === ==== Cholesky Decomposition ==== * http://issues.apache.org/jira/browse/HAMA94 ==== Singular Value Decompostion ==== * http://issues.apache.org/jira/browse/HAMA176 
Contents
M/R Algorithms
Basic Algorithms
Addition
Addition of multiple matrices
Multiplication
 Iterative Approach
For i = 0 step 1 until N 1 Job: Computes the ith row of C = MatrixVector multiplication Iterative job:  A map task receives a row n of B as a key, and vector of row as its value  Multiplying by all columns of ith row of A  Reduce task find and add the ith product 1st + + + +  a11 a12 a13   a11 a21 a31   ... ... ...  X  a12 a22 a32   ... ... ...   a13 a23 a33  + + + + 2nd + + + +  ... ... ...   a11 a21 a31   a21 a22 a23  X  a12 a22 a32   ... ... ...   a13 a23 a33  + + + + ....
 Blocking Algorithm Approach
To mutliply two dense matrices A and B, We collect the blocks to 'collectionTable' firstly using map/reduce. Rows are named as c(i, j) with sequential number ((N^2 * i) + ((j * N) + k) to avoid duplicated records.
CollectionTable: matrix A matrix B + block(0, 0)0 block(0, 0) block(0, 0) block(0, 0)1 block(0, 1) block(1, 0) block(0, 0)2 block(0, 2) block(2, 0) ... N ... block(N1, n1)(N^31) block(N1, N1) block(N1, N1)
Each row has a two sub matrices of a(i, k) and b(k, j) so that minimized data movement and network cost.
Blocking jobs: Collect the blocks to 'collectionTable' from A and B.  A map task receives a row n as a key, and vector of each row as its value  emit (blockID, subvector) pairs  Reduce task merges block structures based on the information of blockID Multiplication job:  A map task receives a blockID n as a key, and two submatrices of A and B as its value  Multiply two submatrices: a[i][j] * b[j][k]  Reduce task computes sum of blocks  c[i][k] += multiplied blocks
Matrix Norm
 Find the maximum absolute row sum of matrix
Matrix.Norm.One is that find the maximum absolute row sum of matrix. Comparatively, it's a good fit with MapReduce model because doesn't need iterative jobs or table/file JOIN operations.
j=n The maximum absolute row sum = max ( sum  a_{i,j}  ) 1<=i<=n j=1  A map task receives a row n as a key, and vector of each row as its value  emit (row, the sum of the absolute value of each entries)  Reduce task select the maximum one
NOTE: Matrix.infinity, Matrix.Maxvalue and Matrix.Frobenius are almost same with this.
Compute the transpose of matrix
The transpose of a matrix is another matrix in which the rows and columns have been reversed. The matrix must be square for this work.
+ + + +  a11 a12 a13   a11 a21 a31   a21 a22 a23  =>  a12 a22 a32   a31 a32 a33   a13 a23 a33  + + + +  A map task receives a row n as a key, and vector of each row as its value  emit (Reversed index, the entry with the given index)  Reduce task sets the reversed values
Compute the determinant of square matrix
Decomposition Algorithms
Cholesky Decomposition