A Levinson-like fast algorithm for solving block-slanted Toeplitz systems of equations arising in wavelet-based solution of integral equations

The Krein integral equation of one-dimensional inverse scattering, which has a symmetric Toeplitz kernel, is transformed using wavelets into a “block-slanted Toeplitz” system of equations. The kernel of the integral equation does not satisfy the Calderon-Zygmund conditions and as a result, application of the wavelet transform to the integral equation does not yield a sparse system matrix. There is therefore a need for a fast algorithm which directly exploits the (symmetric block-slanted-Toeplitz) structure of the system matrix and does not rely on sparsity. The first such O(N²) algorithm is presented