Dear Forum!

I've been thinking about a method to improve filesharing which works by sending linear combinations of parts of a file, instead of the parts themselves. (Nothing new so far, e.g. there are so called online and raptor codes). However there's an overhead associated with this as there are usually linear combinations transferred that are already linear combinations of the ones already received... an improvement would be to determine, with low complexity, if a linear combination offered by some peer would be useful, in order to minimize data transmission overhead.

To state this a bit more mathematically:

You get individual lines of a matrix one by one. Determine the rank of the matrix that you've got so far.
This step would be repeated with a matrix that has just one new line appended at the bottom (possibly enabling some speed - up).

Do you know of any algorithm that does this in less than O(n^2) per line or O(n^3) total?

What if the matrix is sparse? Or if it has special form? Would a speed-up (even linear) be possible if we check multiple new lines in some sort of batch processing?

Looking forward to your answers/suggestions,

Kind regards,
Florian