The CM256 block erasure codec is up here: https://github.com/catid/cm256

It uses a Cauchy matrix modified so that the first row is all ones, for better performance.

The encoder is just a matrix-vector product. I think there might be a way to speed that up more.

The latest version of the decoder takes some subset of the matrix and LDU-decomposes it into three matrices that can be used to solve the linear system with effectively another matrix-vector product.

Interestingly the decomposition has at least N ones in it, if it involves the first matrix row, for a NxN matrix, so the decoder runs similarly fast as the encoder on the first row.

The decomposition is quite a bit faster than normal Gaussian elimination, which takes (N/2)*N^2 matrix multiplications to eliminate the lower left triangle. Instead it takes about 4 * N^2 matrix multiplications.

This means the new decoder is slightly slower for N = 3, about the same for N = 2 and 4, and faster for N > 4.

My solver is based on the Schur-type-direct-Cauchy algorithm 2.5 from

"Pivoting and Backward Stability of Fast Algorithms for Solving Cauchy Linear Equations" (T. Boros, T. Kailath, V. Olshevsky)

It uses a Cauchy matrix modified so that the first row is all ones, for better performance.

The encoder is just a matrix-vector product. I think there might be a way to speed that up more.

The latest version of the decoder takes some subset of the matrix and LDU-decomposes it into three matrices that can be used to solve the linear system with effectively another matrix-vector product.

Interestingly the decomposition has at least N ones in it, if it involves the first matrix row, for a NxN matrix, so the decoder runs similarly fast as the encoder on the first row.

The decomposition is quite a bit faster than normal Gaussian elimination, which takes (N/2)*N^2 matrix multiplications to eliminate the lower left triangle. Instead it takes about 4 * N^2 matrix multiplications.

This means the new decoder is slightly slower for N = 3, about the same for N = 2 and 4, and faster for N > 4.

My solver is based on the Schur-type-direct-Cauchy algorithm 2.5 from

"Pivoting and Backward Stability of Fast Algorithms for Solving Cauchy Linear Equations" (T. Boros, T. Kailath, V. Olshevsky)

last edit by catid
edited (>30 days ago) 8:31pm Fri. Oct 30th 2015 PDT