Split versions of the Levinson-like and Schur-like fast algorithms for solving block-slanted-Toeplitz systems of equations

In a previous paper in this issue, the Fredholm equations of one-dimensional (1-D) inverse scattering and LLS estimation were transformed via the orthonormal wavelet transform into a series of symmetric "block-slanted-Toeplitz" (BST) systems of equations. Levinson-like and Schur-like fast algorithms were presented for solving the BST systems. Here, we present split versions of the Levinson-like and Schur-like fast algorithms. The significance of these split algorithms is as follows. Although the Levinson-like and Schur-like fast algorithms reduce the complexity of solving the BST systems from O(n(3)) to O(n(2)), there still exists an inherent redundancy in these algorithms in the case where the BST system matrices have centrosymmetric blocks. This situation arises when a symmetric wavelet basis function (like the Littlewood-Paley) is used in the problem transformation. This redundancy is exploited here to derive the split Levinson-like and split Schur-like fast algorithms. These split algorithms reduce the number of multiplications required at each iteration by a factor of two, as compared with the Levinson-like and Schur-like algorithms.