  Straggler nodes are well-known bottlenecks of distributed matrix computations
which induce reductions in computation/communication speeds. A common strategy
for mitigating such stragglers is to incorporate Reed-Solomon based MDS
(maximum distance separable) codes into the framework; this can achieve
resilience against an optimal number of stragglers. However, these codes assign
dense linear combinations of submatrices to the worker nodes. When the input
matrices are sparse, these approaches increase the number of non-zero entries
in the encoded matrices, which in turn adversely affects the worker computation
time. In this work, we develop a distributed matrix computation approach where
the assigned encoded submatrices are random linear combinations of a small
number of submatrices. In addition to being well suited for sparse input
matrices, our approach continues have the optimal straggler resilience in a
certain range of problem parameters. Moreover, compared to recent sparse matrix
computation approaches, the search for a "good" set of random coefficients to
promote numerical stability in our method is much more computationally
efficient. We show that our approach can efficiently utilize partial
computations done by slower worker nodes in a heterogeneous system which can
enhance the overall computation speed. Numerical experiments conducted through
Amazon Web Services (AWS) demonstrate up to 30% reduction in per worker node
computation time and 100x faster encoding compared to the available methods.
