  We speed up existing decoding algorithms for three code classes in different
metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved
Gabidulin codes in the subspace metric, and linearized Reed-Solomon codes in
the sum-rank metric. The speed-ups are achieved by new algorithms that reduce
the cores of the underlying computational problems of the decoders to one
common tool: computing left and right approximant bases of matrices over skew
polynomial rings. To accomplish this, we describe a skew-analogue of the
existing PM-Basis algorithm for matrices over ordinary polynomials. This
captures the bulk of the work in multiplication of skew polynomials, and the
complexity benefit comes from existing algorithms performing this faster than
in classical quadratic complexity. The new algorithms for the various
decoding-related computational problems are interesting in their own and have
further applications, in particular parts of decoders of several other codes
and foundational problems related to the remainder-evaluation of skew
polynomials.
