Faster erasure codes

[catid]

Please consider this newer O(N Log N) time approach for future versions of ISA-L erasure codes, which supports up to 65536 symbols:

https://github.com/catid/leopard

[catid]

Without modifying ISA-L too much there are some quick optimizations possible:

(1) Modify the Cauchy matrix structure to make the first row all ones similar to Vandermonde matrix by dividing each column by the first element in that column.
Demonstrated here: https://github.com/catid/cm256/blob/master/cm256.cpp#L128
This means you can just XOR the first row:
https://github.com/catid/cm256/blob/master/cm256.cpp#L153
It's much faster if you have a lot of input data but just a few outputs..

(2) Use faster Schur-type-direct-Cauchy algorithm to produce LDU-decomposition of the generator matrix directly in O(N^2) instead of O(N^3).
Demonstrated here: https://github.com/catid/cm256/blob/master/cm256.cpp#L345

[dong-liuliu]

thanks for the suggestion, Catid.
Let's start to understand these algorithms first.

[gbtucker]

Thanks for the suggestions. Note that ec_encode_data() functions work for any encoding matrix. On (2) do I understand this correctly that it will only work on Cauchy encoding matrices? We did write a general matrix inverse using LU decomposition and a vectorized version but it seems the LU one was only marginally faster and only for very large n. We could add more example encoding matrices gf_gen_cauchy2_matrix(), etc. if useful.

[catid]

Yeah I think it’s slower for small matrices. The Cauchy specific LDU method was faster past 16 or so IIRC but it has been a while since I tested that. Also it doesn’t improve performance for banded matrices found in streaming erasure codes