  This paper considers fast algorithms for operations on linearized
polynomials. We propose a new multiplication algorithm for skew polynomials (a
generalization of linearized polynomials) which has sub-quadratic complexity in
the polynomial degree $s$, independent of the underlying field extension
degree~$m$. We show that our multiplication algorithm is faster than all known
ones when $s \leq m$. Using a result by Caruso and Le Borgne (2017), this
immediately implies a sub-quadratic division algorithm for linearized
polynomials for arbitrary polynomial degree $s$. Also, we propose algorithms
with sub-quadratic complexity for the $q$-transform, multi-point evaluation,
computing minimal subspace polynomials, and interpolation, whose
implementations were at least quadratic before. Using the new fast algorithm
for the $q$-transform, we show how matrix multiplication over a finite field
can be implemented by multiplying linearized polynomials of degrees at most
$s=m$ if an elliptic normal basis of extension degree $m$ exists, providing a
lower bound on the cost of the latter problem. Finally, it is shown how the new
fast operations on linearized polynomials lead to the first error and erasure
decoding algorithm for Gabidulin codes with sub-quadratic complexity.
