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

In Joshi and Yagle (1998) 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³) to O(n²), 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     

An algorithm for solving discrete-time Wiener-Hopf equations based upon Euclid's algorithm

An algorithm for solving a discrete-time Wiener-Hopf equation is presented based upon Euclid's algorithm. The discrete-time Wiener-Hopf equation is a system of linear inhomogeneous equations with a given Toeplitz matrix M, a given vector b, and an unknown vectorlambdasuch thatMlambda = b. The algorithm is able to find a solution of the discrete-time Wiener-Hopf equation for any type of Toeplitz matrices except for the all-zero matrix, while the Levinson algorithm and the Trench algorithm are not available when at least one of the principal submatrices of the Toeplitz matrixMis singular. The algorithm gives a solution, if one exists, even when the Toeplitz matrixMis singular, while the Brent-Gustavson-Yun algorithm only states that the Toeplitz matrixMis singular. The algorithm requiresO(t^{2})arithmetic operations fortunknowns, in the sense that the number of multiplications or divisions is directly proportional tot^{2}, like the Levinson and Trench algorithms. Furthermore, a faster algorithm is also presented based upon the half greatest common divisor algorithm, and hence it requiresO(t log^{2} t)arithmetic operations, like the Brent-Gustavson-Yun algorithm.     

Fredholm resolvents, Wiener-Hopf equations, and Riccati differential equations

We shall show that the solution of Fredholm equations with symmetric kernels of a certain type can be reduced to the solution of a related Wiener-Hopf integral equation. A least-squares filtering problem is associated with this equation. When the kernel has a separable form, this related problem suggests that the solution can be obtained via a matrix Riccati differential equation, which may be a more convenient form for digital computer evaluation. The Fredholm determinant is also expressed in terms of the solution to the Riccati equation; this formula can also be used for the numerical determination of eigenvalues. The relations to similar work by Anderson and Moore and by Schumitzky are also discussed.     

Plane wave diffraction by a slit in a perfectly conducting plane and a parallel complementary strip

The diffraction of plane electromagnetic waves by the configuration formed by a slit in a perfectly conducting plane and a parallel complementary strip is investigated. The related boundary-value problem is formulated into a modified matrix Wiener-Hopf equation. The factorization of the kernel matrix is accomplished through Abrahams’ method and the modified matrix Wiener-Hopf equation is first reduced to a pair of coupled Fredholm integral equations of the second kind and then solved by iterations. Several numerical results illustrating the effects of various parameters such as the spacing between the slit and the strip and their width on the diffraction phenomena are presented.     

Solution of large dense complex matrix equations utilizing wavelet-like transforms

The objective of this paper is to explore the validity of various mathematical properties of the wavelet-like transforms for the solution from thin wire structures utilizing the conventional integral equation technique based on the method of moments. It is illustrated through numerical experimentation that the conventional mathematical bounds existing for the classical wavelet transform do not apply to the wavelet-like transforms. Also the classical wavelet transform is really not applicable for the solution of the matrix equations. These statements will be illustrated through examples.     

Fast solution of electromagnetic integral equations using adaptivewavelet packet transform

The adaptive wavelet packet transform is applied to sparsify the moment matrices for the fast solution of electromagnetic integral equations. In the algorithm, a cost function is employed to adaptively select the optimal wavelet packet expansion/testing functions to achieve the maximum sparsity possible in the resulting transformed system. The search for the best wavelet packet basis and the moment matrix transformation are implemented by repeated two-channel filtering of the original moment matrix with a pair of quadrature filters. It is found that the sparsified matrix has above-threshold elements that grow only as O(N^1.4) for typical scatterers. Consequently the operations to solve the transformed moment equation using the conjugate gradient method scales as O(N^1.4). The additional computational cost for carrying out the adaptive wavelet packet transform is evaluated and discussed     

Algorithm for wavelet transform of Toeplitz matrices

An algorithm is presented for calculating the 2D wavelet transform of a Toeplitz matrix. The algorithm exploits the special form of the Toeplitz matrix in order to reduce the number of operations required. More specifically. It is shown that the number of 1D wavelet transformations that are necessary to carry out a sub-band decomposition can be reduced to eight     

A comparison of integral equations with unique solution in theresonance region for scattering by conducting bodies

A comparison of integral equations, for problems involving scattering by arbitrary-shape conducting bodies, having a unique solution in the resonance region is presented. The augmented electric and magnetic field integral equations and the combined field integral equation, in their exact and approximate versions, are considered. The integral equations and the basis and test functions used in the method of moments to solve them are reviewed. Their implementation in a computer code is analyzed, mainly the relation between the matrix properties and the CPU time and memory. Numerical results (condition number and backscattering cross section) are presented for the cube. It is shown that the combined field integral equation, and the approximate (symmetric) combined field integral equation, are the most efficient equations to use in the neighborhood of resonant frequencies, because the overdetermined augmented integral equations require an extra matrix multiplication     

Exact and first-order error analysis of the Schur and split Schuralgorithms: theory and practice

A new analytical methodology is introduced here for fixed-point error analysis of various Toeplitz solving algorithms. The method is applied to the very useful Schur algorithm and the lately introduced split Schur (1918, 1986) algorithm. Both exact and first order error analysis are provided in this paper. The theoretical results obtained are consistent with experimentation. Besides the intrinsic symmetry of the error propagation recursive formulae, the technique presented here is capable of explaining many practical situations. For signals having a small eigenvalue spread the Schur algorithm behaves better than the split Schur in the fixed-point environment. The intermediate coefficients of the split Schur algorithm leading to the PARCOR's cannot serve as alternatives to the reflection coefficients in error sensitive applications. It is demonstrated that the error-weight vectors of the Schur propagation mechanism follow Levinson-like (second order) recursions, while the same vectors of the split Schur propagation mechanism follow split Levinson-like (third-order) recursions     

Application of wavelet transforms for solving integral equationsthat arise in rough-surface scattering

We consider the problem of scattering a plane wave from a periodic rough surface. The scattered field is evaluated once the field on the boundary is calculated. The latter is the solution of an integral equation. In fact, different integral equation formulations are available in both coordinate and spectral space. We solve these equations using standard numerical techniques, and compare the results to corresponding solutions of the equations using wavelet transform methods for "sparsification" of the impedance matrix. Using an energy check, the methods are shown to be highly accurate. We limit the discussion to the Dirichlet problem (scalar), or the TE-polarized case for a one-dimensional surface. The boundary unknown is thus the normal derivative of the total (scalar) field or, equivalently, the surface current. We illustrate two conclusions. First, sparsification (using "thresholded" wavelet transforms) can significantly reduce accuracy. Second, the wavelet transform did not speed up the overall solution. For our examples, the solution time was considerably increased when thresholded wavelet transforms were used     

Semi-orthogonal versus orthogonal wavelet basis sets for solvingintegral equations

The two categories of wavelets, orthogonal and semi-orthogonal, are compared and it is shown that the semi-orthogonal wavelet is best suited for integral equation applications. The Battle-Lemarie orthogonal wavelet and the spline generated semi-orthogonal wavelet are each used to solve for the current distribution on an infinite strip illuminated by a transverse magnetic (TM) plane wave and a straight thin wire illuminated by a normally incident plane wave. The grounds for comparison are accuracy in characterizing the current, matrix sparsity, computation time, and singularity extraction capability. The limitations and advantages of solving integral equations with each of the two wavelet categories are discussed     

Levinson-type extensions for non-Toeplitz systems

It is shown Levinson's basic principle for the solution of normal equations which are of Toeplitz form may be extended to the case where these equations do not possess this specific symmetry. The method is illustrated by application to various examples which are chosen so that the coefficient matrix possesses various symmetries. Specifically, the solution of the normal equations when the associated matrix is the doubly symmetric non-Toeplitz covariance matrix is considered. Next, the solution of extended Yule-Walker equations where the coefficient matrix is Toeplitz, but nonsymmetric is obtained. Finally, the approach is illustrated by considering the determination of the prediction error operator when the normal equations are of symmetric Toeplitz form     

On the application of numerical methods to Hallen's equation

The so-called Hallen integral equation for the current on a finite linear antenna center-driven by a delta-function generator takes two forms depending on the choice of kernel. The two kernels are usually referred to as the exact and the approximate or reduced kernel. With the approximate kernel, the integral equation has no solution. Nevertheless, the same numerical method is often applied to both forms of the integral equation. In this paper, the behavior of the numerical solutions thus obtained is investigated, and the similarities and differences between the two numerical solutions are discussed. The numerical method is Galerkin's method with pulse functions. We first apply this method to the two corresponding forms of the integral equation for the current on a linear antenna of infinite length. In this case, the method yields an infinite Toeplitz system of algebraic equations in which the width of the pulse basis functions enters as a parameter. The infinite system is solved exactly for nonzero pulse width; the exact solution is then developed asymptotically for the case where the pulse width is small. When the asymptotic expressions for the case of the infinite antenna are used as a guide for the behavior of the solutions of the finite antenna, the latter problem is greatly facilitated. For the approximate kernel, the main results of this paper carry over to a certain numerical method applied to the corresponding equation of the Pocklington type     

用MoM—PCG—FFT分析金属栅有限阵列的散射问题

本文用矩量法、预条件共轭梯度法和快速傅里叶变换（MoM-PCG-FFT)的混合技术来分析金属栅有限阵列的电磁散射问题。首先以等效电流作为未知函数建立积分方程组或积分－微分方程组,再用矩量法（脉冲／点匹配）获得一个线性代数方程组,其系数矩阵是一个对称二重复Toeplitz矩阵,基于这一特点,应用预条件共轭梯度法和快速傅里叶变换的结合算法（PCGFFT）来求解这个线性代数方程组,其中预条件器选用T.Chan循环预条件共轭梯度法和快速傅里叶变换的结合算法（PCGFFT）来求解这个线性代数方程组,其中预条件器选用T．Chan循环预条件器的二重分块形式。文中给出的数值算例表明该混合技术是有效的,适用于较大的金属栅有限阵列的分析。     

New algorithm for solving block matrix equations with applicationsin 2-D AR spectral estimation

The author presents an iterative algorithm to solve Toeplitz and non-Toeplitz block matrix equations. The development is based upon some well-known matrix iterative techniques. The algorithm is developed for the ideal case where the individual blocks in the autocorrelation matrix are Toeplitz, and it is then extended to a more general least squares data formulation case. It is shown that the algorithm requires fewer computations than the direct matrix inversion methods and is very simple to implement. The algorithm is applied to compute the spectral estimates of 2-D data of very small size based on the least squares data formulation with a quarter plane support     

A Modified Residue-Calculus Technique for Solving a Class of Boundary Value Problems Part I: Waveguide Discontinuities

The modified residue-calculus technique, which is a generalization of the conventional function theoretic procedure for solving certain infinite sets of equations, permits solution of waveguide discontinuity problems which include dielectric, diaphragm, and step modifications of a basic discontinuity problem exactly solvable by the Wiener-Hopf techniqne. Solutions in scattering matrix form, including both propagating and nonpropagating modes, are found by a rapidly convergent and very accurate numerical procedure which eliminates many of the computational difficulties associated with integral equation or matrix equation solutions of the same problems.     

An asymmetric discrete-time approach for the design and analysis ofperiodic waveguide gratings

A discrete-time approach is introduced for the analysis of periodic waveguide gratings with gain (or loss) extending concepts developed for transfer matrix and Gel'fand-Levitan-Marchenko (GLM) inverse scattering techniques. The periodic waveguide grating with gain (or loss) is modeled as a lossy layered dielectric that allows for a digital signal processing (DSP) formulation of the forward and inverse scattering problem. It is shown that the DSP forward scattering formulation as an asymmetric two-component wave system is equivalent to the impedance matching matrix method. A numerical example is presented to emphasize this result. The DSP formulation is an exact discrete design, not just an approximation to a continuous design, and includes all multiple reflections, transmission scattering losses, and absorption effects. A comparison of the continuous GLM, discrete GLM, and discrete Krein inverse problem formulations for a medium with gain (or loss) is presented. The discrete lossy formulations generalize previous lossless results and are found from two different types of reflection data. Since slab gratings are discrete (not continuous) structures, the integral equations used to describe the continuous inverse problem are shown to become matrix equations. Thus, our result enables fast algorithms to be used to solve the inverse problem. A fast algorithm is presented allowing for the complete reconstruction of the grating parameters from its two-sided response in a recursive (slab by slab) fashion     

The Toeplitz matrix: Its occurrence in antenna problems and a rapid inversion algorithm

A special form of the Toeplitz matrix which frequently occurs in the numerical solution of antenna analysis and synthesis problems is discussed. Specific examples are presented illustrating its occurrence in the solution of the integral equation for a thin cylindrical antenna and in the theory of arrays. A matrix inversion algorithm is presented which, by exploiting the unique symmetry properties of the Toeplitz matrix, specifies the inverse matrix elements in terms of recurrence relationships. In this way computational time is proportional to the square of the matrix order rather than the cube as is the case with a general algorithm.     

Weighted least mean square design of 2-D FIR digital filters: thegeneral case

This paper solves the weighted least mean square (WLMS) design of two-dimensional (2-D) finite impulse response (FIR) filters with general half plane symmetric frequency responses and nonnegative weighting functions. The optimal solution is characterized by a pair of coupled integral equations, and the existence and uniqueness of the WLMS solution for 2-D FIR filter design are established. Two efficient numerical algorithms using a 2-D fast Fourier transform (FFT) are proposed to solve the WLMS solution. One is based on the contraction mapping and fix point theorem characterizing the coupled integral equation; the other uses conjugate gradient techniques, which guarantees finite convergence. The associated computational complexity is analyzed and compared with existing algorithms. Examples are used to illustrate the effectiveness of the proposed design algorithms. The selection of weighting functions to improve the minimax performance of the filter is also discussed