Ah, okay thanks. My coding theory is a bit weak, but it looks like this algorithm depends on the specific form of RS codes that you mentioned. I think the presentation outlines a form of RS erasure codes which is more general (e.g., allows Cauchy parity matrices instead of Vandermonde-derived ones).

Using a general matrix inversion is indeed inefficient, and becomes impractical for large k. However, the special-purpose row reduction algorithm I mentioned gets to O(nm^2) which is much better, although worse than the O(nm) algorithm you mentioned, which makes sense given that that one handles more specific RS codes.

Thanks for elaborating! It's reminding me that I really should brush up on coding theory, though -- do you have any resources/textbooks you'd recommend for someone familiar with the mathematical background? (Finite fields, etc.)