An nxn matrix A is rank structured if its submatrices strictly contained 
 in the lower/upper triangular part have "small" rank with respect to n. 
 Most part of companion-like matrices are rank structured. In this talk we 
 present some recent results concerning rank-structured matrices, like 
 semi-separable and quasi-separable matrices, and apply them to the design 
 of effective algorithms for computing the eigenvalues of companion-like 
 matrices.  In particular, we show that the matrix sequence generated by 
 the QR iteration maintains the rank structure for most companion-like 
 matrices. This fact is used to design an implementation of the QR 
 algorithm which requires O(n)$ arithmetic operations per step instead of 
 O(n2). We discuss about using these properties for the design of a new 
 polynomial rootfinding software.