  Toeplitz-structured linear systems arise often in practical engineering
problems. Correspondingly, a number of algorithms have been developed that
exploit Toeplitz structure to gain computational efficiency when solving these
systems. The earliest "fast" algorithms for Toeplitz systems required O(n^2)
operations, while more recent "superfast" algorithms reduce the cost to O(n
(log n)^2) or below. In this work, we present a superfast algorithm for
Tikhonov regularization of Toeplitz systems. Using an
"extension-and-transformation" technique, our algorithm translates a
Tikhonov-regularized Toeplitz system into a type of specialized polynomial
problem known as tangential interpolation. Under this formulation, we can
compute the solution in only O(n (log n)^2) operations. We use numerical
simulations to demonstrate our algorithm's complexity and verify that it
returns stable solutions.
