### Parallel Matrix Multiply on Hadoop Map/Reduce: 2D blocking

In matrix multiplication, calculating one element of C requires reading an entire row of A and an entire column of B. Calculating an entire column of C (m elements) requires reading all rows (m rows) of A once and re-reading one column of B m times. Thus, Calculating n columns of C requires reading all rows of A n times and all columns of B m times.

In blocking, matrix multiplication of the original arrays is transformed into matrix multiplication of blocks. For example,

C_block(1,1)=A_block(1,1)*B_block(1,1) + A_block(1,2)*B_block(2,1)

This is a well-known Cache Blocking technique for efficient memory accesses. Then, We can think about a Memory Blocking technique for efficient disk accesses and parallelism (or distributed?) on the Hadoop MapReduce as describe below.

Each mapper processes a matrix multiplication of blocks and reducer processes sum up all sub-matrices.

map(BlockID, TwoDArrayWritable)   -> <C_block(1,1), A_block(1,1)*B_block(1,1)>, ...reduce(BlockID’, <TwoDArrayWritable>*)    -> <C_block(1,1), A_block(1,1)*B_block(1,1) + A_block(1,2)*B_block(2,1)>, ...

In my own work, It runs greatly. But, I'm not sure it can be auto-optimized.

1. It seems very interesting!

2. Would be really great if you could post a tutorial on using hadoop pipes to do matrix multiplication.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8132707,"math_prob":0.95247686,"size":1307,"snap":"2019-51-2020-05","text_gpt3_token_len":335,"char_repetition_ratio":0.14504988,"word_repetition_ratio":0.0,"special_character_ratio":0.25325173,"punctuation_ratio":0.16603774,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9954145,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,2,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-18T08:18:58Z\",\"WARC-Record-ID\":\"<urn:uuid:149430a6-838a-4440-a816-120203b01f55>\",\"Content-Length\":\"146688\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:07d956fa-4b09-4e27-8701-f81b48fa60c5>\",\"WARC-Concurrent-To\":\"<urn:uuid:fe63c9cd-403a-43ec-b229-c6908025be13>\",\"WARC-IP-Address\":\"172.217.7.211\",\"WARC-Target-URI\":\"https://blog.udanax.org/2008/10/parallel-matrix-multiply-on-hadoop.html\",\"WARC-Payload-Digest\":\"sha1:N4V3T4NBDKMSD556VRKBLERJPYJP2QTY\",\"WARC-Block-Digest\":\"sha1:SRQ2VGNR4YKGYRTJP44SQBMGGKXCQHFE\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250592394.9_warc_CC-MAIN-20200118081234-20200118105234-00136.warc.gz\"}"}