Efficient repair of erasure coded data based on coefficient matrix decomposition

A non-transitory processor readable medium storing instruction that, when executed by a processor of a controller device configured to communicate with storage nodes of a distributed storage system in which erasure codes are used to encode source data onto the storage nodes and ranks of matrices containing coding coefficients associated with the erasure codes indicate whether repairs of failed storage nodes of the distributed storage system are feasible, cause the processor to:

• generate a decomposition structure to be used as a guide for transforming the matrices to upper triangle form (UTF) for use in computing the ranks of the matrices, wherein the decomposition structure defines (i) a break-down of the matrices into submatrices each including a number of rows of coding coefficients less than the number of rows of coding coefficients in each of the matrices, and (ii) mappings among the matrices and the submatrices that indicate how to merge the submatrices in order to transform the matrices to UTF;
• and
• while the distributed storage system is performing repairs of the failed storage nodes, as part of determining feasible repair strategies for subsequent repairs of failed storage nodes, compute the ranks of the matrices by transforming the matrices to UTF using operations on the submatrices according to the decomposition structure.