Matrix computation code

Description

Encoding that provides an extra redundancy for distributed matrix computation algorithms such as matrix multiplication. Parallelized algorithms distribute a desired computation over many nodes, and a key performance bottleneck is due to some nodes completing their individual tasks much later than other nodes. Matrix computation codes provide a layer of redundancy such that the computation can be performed without having all nodes finish their piece of the computation.

Protection

Allows computation to complete without waiting for stragglers, or nodes that either do not finish or finish their portion of the computation much later than all other nodes.

Parent

Cousin

Zoo code information

Internal code ID: matrix_computation

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: matrix_computation

Cite as:
“Matrix computation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/matrix_computation
BibTeX:
@incollection{eczoo_matrix_computation, title={Matrix computation code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/matrix_computation} }
Permanent link:
https://errorcorrectionzoo.org/c/matrix_computation

References

[1]
K. Lee et al., “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018). DOI; 1512.02673

Cite as:

“Matrix computation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/matrix_computation

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/matrices/matrix_computation.yml.