In large-scale distributed matrix-vector multiplications, e.g., for generative AI, straggling nodes can slow down or even jeopardize the whole operation. Coded distributed computing (CDC) uses erasure codes to create redundant computations and combat stragglers. This requires encoding very large matrices. Moreover, encoding must be repeated whenever system parameters (e.g., weight matrices in AI models) evolve. This paper introduces a general framework for reducing encoding complexity in CDC. We propose the notion of an encoding blueprint, a construction schedule that specifies how each coded symbol is constructed from data and previously computed coded symbols. An optimal blueprint minimizes the number of arithmetic operations required for a given code. We first design blueprints using addition-only operations. We then extend the framework to also allow subtraction, which further decreases the number of required operations. The optimization problem is cast as a mixed-integer program (MIP), and solved. Numerical results on matrix–vector multiplication show that optimized blueprints reduce encoding operations by up to 60 percent compared to standard methods, saving billions of operations in large-scale applications. Our techniques can be used for efficient decoding as well.

In high-rate or long-haul optical fiber transmissions, correcting chromatic dispersion (CD) is critical but challenging and energy-intensive due to the large filter tap size required for CD compensation (CDC). Overlap-save (OLS) is a common frequency-domain CDC technique that uses fast Fourier transform (FFT). However, hardware constraints-such as power, memory, latency, and chip area-limit the FFT size. This limitation makes OLS too complex or even infeasible in dispersive channels where the number of taps approaches or exceeds the FFT size. We introduce the time-segmented overlap-free (TS-OLF) technique, a novel frequency-domain block filtering method to enable low-complexity CDC under FFT-size limitations. TS-OLF divides the signal into non-overlapping blocks and segments the filter accordingly to enable filtering operations with any FFT size. It aggregates the results of different filter segments directly in the frequency domain, therefore, using a minimum number of FFT operations. We show that TS-OLF achieves consistently lower complexity than OLS when the filter size is more than half the FFT size, and unlike OLS, can handle filter sizes that exceed the FFT size. TS-OLF also outperforms other filter segmenting methods, providing significant complexity improvements.