The arithmetic cost bounds for solving a Toeplitz or Hankel linear system of equations is O(n lg² n). The progression of algorithmic development that led to this bound includes what have come to be referred to as “fast” and “superfast” algorithms. First came the “fast” algorithms crafted by Levinson in 1947, Durbin in 1959, and Trench in 1964 and 1965. The “fast” algorithms each perform O(n ²) arithmetic operations. Later “superfast” algorithms were devised, in particular the BYG algorithm by Brent, Gustavson, and Yun in 1980 [BGY80] and the MBA divide and conquer algorithm by Morf in 1974 [M74] and 1980 [M80] and Bitmead and Anderson in 1980 [BA80]. These “superfast” algorithms both require O(n lg² n) arithmetic operations and can be implemented numerically with finite precision.

Unfortunately, numerical instability plagues these Toeplitz and Hankel “superfast” numerical linear solvers (see Bunch 1985 [B85]) and some large and important classes of Toeplitz and Hankel matrices are ill-conditioned (see Tyrtyshnikov 1994 [T94]). Therefore, absent application of exceedingly high precision these “superfast” numerical linear solvers produce invalid results for many highly significant Toeplitz and Hankel linear systems. This dilemma led to the development of algebraic (or symbolic) techniques to simultaneously bound the arithmetic cost and the precision of computation. Such techniques have resulted in implementations of the algorithms that are slower, but error free for ill-conditioned Toeplitz and Hankel input matrices. Algebraic (or symbolic) implementations typically rely upon utilization of the Chinese remainder algorithm (see [GG99]], [PW02], and [WP03]).

Herein Hensel’s p-adic lifting has been leveraged in alternative algebraic methods for implementing “superfast” Toeplitz/Hankel linear solvers. This approach holds important advantages over those using the Chinese remainder algorithm. In addition, Hensel’s p-adic lifting has been extended to apply q-adic lifting for q = 2^s where s is an integer, herein referred to as Binary lifting. This has allowed many of the expensive modular computations required in the lifting steps to be carried out often implicitly and practically for “free” as a result of the efficiencies inherent in this regard by the binary nature of today’s computer hardware.