  Matrices with the structures of Toeplitz, Hankel, Vandermonde and Cauchy
types are omnipresent in modern computation. The four classes have distinct
features, but in 1990 we showed that Vandermonde and Hankel multipliers
transform all these structures into each other and proposed to employ this
property to extend any successful algorithm that inverts matrices of one of
these classes to inverting matrices of the three other classes. The power of
this approach was widely recognized later, when novel numerically stable
algorithms solved nonsingular Toeplitz linear systems of equations at first in
quadratic and then in nearly linear (versus classical cubic) arithmetic time by
means of transforming Toeplitz into Cauchy matrix structures and then linking
it to the Hierarchical Semiseparable matrix structure, a specialization of
matrix representations employed by the Fast Multipole Method. We first cover
the method of structure transformation comprehensively, then analyze the latter
algorithms for Toeplitz linear systems and extend them to approximate the
products of Vandermonde and Cauchy matrices by a vector and the solutions of
Vandermonde and Cauchy linear systems of equations where they are nonsingular
and well conditioned. We decrease the arithmetic cost of the known algorithms
from quadratic to nearly linear, and similarly for the computations with the
matrices of a more general class having structures of Vandermonde and Cauchy
types and for polynomial and rational evaluation and interpolation. We also
accelerate a little further the known numerical approximation algorithms for a
nonsingular Toeplitz or Toeplitz-like linear system by employing distinct
transformations of matrix structures, and we briefly discuss some natural
research challenges, particularly some promising applications of our techniques
to high precision computations.
