  For matrices with displacement structure, basic operations like
multiplication, inversion, and linear system solving can all be expressed in
terms of the following task: evaluate the product $\mathsf{A}\mathsf{B}$, where
$\mathsf{A}$ is a structured $n \times n$ matrix of displacement rank $\alpha$,
and $\mathsf{B}$ is an arbitrary $n\times\alpha$ matrix. Given $\mathsf{B}$ and
a so-called "generator" of $\mathsf{A}$, this product is classically computed
with a cost ranging from $O(\alpha^2 \mathscr{M}(n))$ to $O(\alpha^2
\mathscr{M}(n)\log(n))$ arithmetic operations, depending on the type of
structure of $\mathsf{A}$; here, $\mathscr{M}$ is a cost function for
polynomial multiplication. In this paper, we first generalize classical
displacement operators, based on block diagonal matrices with companion
diagonal blocks, and then design fast algorithms to perform the task above for
this extended class of structured matrices. The cost of these algorithms ranges
from $O(\alpha^{\omega-1} \mathscr{M}(n))$ to $O(\alpha^{\omega-1}
\mathscr{M}(n)\log(n))$, with $\omega$ such that two $n \times n$ matrices over
a field can be multiplied using $O(n^\omega)$ field operations. By combining
this result with classical randomized regularization techniques, we obtain
faster Las Vegas algorithms for structured inversion and linear system solving.
