The use of Huygens' equivalence principle for solving the volumeintegral equation of scattering

An algorithm is introduced to solve the volume integral equation of scattering. A volume scatterer is first divided into N subscatterers. Then the subscatterers are divided into four groups, and the groups are in turn divided into four subgroups and so on. By using the idea found in many fast algorithms, a smaller problem can hence be nested within a larger problem. Moreover, by way of Huygen's equivalence principle, the scattering properties of a group of subscatterers in a volume can be replaced by a group of subscatterers distributed on a surface enclosing the volume. This idea is used as the basis of an algorithm which solves the scattering problem in several stages, where at each stage the interaction matrix algorithm is first used to find the scattering solution of each subgroup of subscatterers. Subscatterers are then replaced by equivalent surface subscatterers which are used in the next stage. This results in a reduction in the number of subscatterers at every stage. This algorithm can be shown to have a CPU time asymptotically proportional to N^1.5 for N subscatterers     

Rectangular Pisarenko method applied to source localization

Most high-resolution (HR) direction-of-arrival (DOA) estimation schemes require the extraction of a low-dimensional subspace: a task that takes O(N³) flops for an order S matrix. Different techniques have been recently proposed to reduce this computational load. For those working on blocks of data, the number of flops required is generally O(N²P), where P, which is the dimension of the subspace (the number of sources), is often quite small as compared with N, which is the number of sensors. The method we propose is a HR technique that requires O(NP²)+O(P³) flops, i.e., that is linear in the number of sensors. The price to be paid for this drastic computational saving is a reduction in performance. Although the Cramer-Rao lower bound (CRLB) on the variance of the direction estimates is of the order T^-1 N^-3 (with T the number of snapshots), this variance is of order T^-1 N^-2 for the proposed procedure. The idea behind the method is to apply a Pisarenko method to a rectangular matrix extracted from the Toeplerized estimated covariance matrix, and it is this Toeplerization that allows preservation of the O(T^-1 N^-2) level of performance     

Birkhoff-von Neumann input-buffered crossbar switches forguaranteed-rate services

Based on a decomposition result by Birkhoff (1946) and von Neumann (1953) for a doubly sub-stochastic matrix, in this letter we propose a scheduling algorithm that is capable of providing guaranteed-rate services for input-buffered crossbar switches. Our guarantees are uniformly good for all nonuniform traffic. The computational complexity to identify the scheduling algorithm is O(N^4.5) for an N×N switch. Once the algorithm is identified, its on-line computational complexity is O(log N) and its on-line memory complexity is O(N³ log N)     

Two fast architectures for the direct 2-D discrete wavelettransform

We propose two architectures for the direct two-dimensional (2-D) discrete wavelet transform (DWT). The first one is based on a modified recursive pyramid algorithm (MRPA) and performs a “"nonstandard” decomposition (i.e., Mallat's (1989) tree) of an N×N image in approximately 2N²/3 clock cycles (ccs). This result consistently speeds up other known architectures that commonly need approximately N² ccs. Furthermore, the proposed architecture is simpler than others in terms of hardware complexity. Subsequently, we show how “symmetric”/“anti-symmetric” properties of linear-phase wavelet filter bases can be exploited in order to further reduce the VLSI area. This is used to design a second architecture that provides one processing unit for each level of decomposition (pipelined approach) and performs a decomposition in approximately N²/2 ccs. In many practical cases, even this architecture is simpler than general MRPA-based devices (having only one processing unit)     

Efficient weighted least-squares algorithm for the design of FIRfilters

The weighted least-squares (WLS) technique has been widely used for the design of digital FIR filters. In the conventional WLS, the filter coefficients are obtained by performing a matrix inverse operation, which needs computation of O(N³). The authors present a new WLS algorithm that introduces an extra frequency response including implicitly the weight function. In the new algorithm, the filter coefficients can be solved just by a matrix vector multiplication. It reduces the computational complexity from O(N³ ) to O(N²)     

Low-complexity centralized joint power and admission control in cognitive radio networks

This letter introduces a centralized joint power and admission control algorithm for cognitive radio networks. Its novelty lies in the proposed admission metric. Unlike those in existing algorithms, our metric predetermines the admission order of N secondary users which intend to access the network. This allows us to search a group of admitted secondary users with the bisection method. The proposed algorithm is shown by simulation to achieve a comparable performance to existing algorithms, and the computational complexity is reduced from O(N³) to O(N² log₂ N).     

On a class of predefined wavelet packet bases for efficientrepresentation of electromagnetic integral equations

A general wavelet packet tree is proposed to design predefined wavelet packet (PWP) bases for the efficient representation of electrodynamic integral equations. The wavelet packet decomposition tree is constructed by zooming in along the spectral oscillatory frequency of the free-space Green's function. Numerical results show that for typical two dimensional (2-D) scatterers the number of above-threshold elements in the PWP-based moment matrix is on the order of O(N^1.3) and tends to grow at a rate of O(N·log N) for large-scale problems. Therefore, the complexity of solving the moment equations can be reduced accordingly. Furthermore, it is shown that the elements of the moment matrix based on the PWP bases can be computed directly at approximately the same complexity as the fast wavelet transform approach. Consequently, with on-the-fly thresholding of the matrix elements, the O(N²) memory bottleneck in the formation of the PWP-based moment matrix can be circumvented     

A recursive Green's function method for boundary integral analysisof inhomogeneous domains

The recursive Green's function method (RGFM) for computation of fields scattered by two-dimensional (2-D) inhomogeneous dielectric bodies is presented. The algorithm efficiently constructs the Green's function for the inhomogeneous region by recursively combining known Green's functions from smaller subdomains. The fields on the scatterer surface are then computed using a boundary integral formulation. Proper implementation of the RGFM results in computational and storage complexities which scale as N^1.5 and N, respectively, where N is the total number of discrete cells in a domain. Comparisons of results obtained using the RGFM with those computed from moment method and exact solutions show the efficiency and accuracy of the technique     

A generalized recursive algorithm for wave-scattering solutions intwo dimensions

A generalized recursive algorithm valid for both the E _z and H_z wave scattering of densely packed scatterers in two dimensions is derived. This is unlike previously derived recursive algorithms which have been found to be valid only for E_z polarized waves. In this generalized recursive algorithm, a scatterer is first divided into N subscatterers. The n-subscatterer solution is then used to solve the (n+n')-subscatterer solution. The computational complexity of such an algorithm is found to be of O (N²) in two dimensions while providing a solution valid for all angles of incidence. This is better than the method of moments with Gaussian elimination, which has an O(N³) complexity     

Fast Solution of Scattering From Conducting Structures by Local MLFMA Based on Improved Electric Field Integral Equation

In this paper, a local multilevel fast multipole algorithm (LMLFMA) based on an improved electric field integral equation (IEFIE) is developed to achieve fast and efficient solution of electromagnetic scattering from 3-D conducting structures. The IEFIE is used to reduce iteration number, and LMLFMA is applied to further accelerate the computation of matrix-vector multiplications in iteration, in which only the local interactions between subscatterers are taken into account. Numerical results show that the present method attains faster iterative convergence than traditional EFIE and less computational cost than MLFMA. The speedup can achieve at least 4–5 times while keeping an rms error of less than 2 dB.      

Fast and stable least-squares approach for the design of linearphase FIR filters

We present a new numerical algorithm for solving the normal equations associated with the least-squares design of linear phase FIR filters. The usual solution methods have a computational complexity of O(N³). Moreover, solving the normal equations with Gaussian elimination commonly yields numerical errors, especially when the filter is long. Here, we convert a least-squares method into the problem of constructing a system of orthonormal functions. The proposed design algorithm needs only O(N²) computations, and numerical errors can be reduced. Some examples are given to show the performance of the algorithm     

A nonseparable VLSI architecture for two-dimensional discreteperiodized wavelet transform

A modified two-dimensional (2-D) discrete periodized wavelet transform (DPWT) based on the homeomorphic high-pass filter and the 2-D operator correlation algorithm is developed in this paper. The advantages of this modified 2-D DPWT are that it can reduce the multiplication counts and the complexity of boundary data processing in comparison to other conventional 2-D DPWT for perfect reconstruction. In addition, a parallel-pipeline architecture of the nonseparable computation algorithm is also proposed to implement this modified 2-D DPWT. This architecture has properties of noninterleaving input data, short bus width request, and short latency. The analysis of the finite precision performance shows that nearly half of the bit length can be saved by using this nonseparable computation algorithm. The operation of the boundary data processing is also described in detail. In the three-stage decomposition of an N×N image, the latency is found to be N²+2N+18     

Hierarchical 2-D DD and HD noise simulations of Si and SiGe devicesII. Results

For pt. I see ibid., vol. 49, pp. 1250-1257 (2002). Terminal current noise is investigated with Langevin-type drift-diffusion (DD) and hydrodynamic (HD) noise models for one-dimensional (1-D) N⁺ NN⁺ and P⁺ PP⁺ structures and a realistic two-dimensional (2-D) SiGe NPN HBT. The new noise models, which are suitable for technology computer aided design (TCAD), are validated by comparison with Monte Carlo (MC) device simulations for the 1-D structures including noise due to particle scattering and generation of secondary particles by impact ionization (II). It is shown that the accuracy of the usual approach based on the DD model in conjunction with the Einstein relation degrades under nonequilibrium conditions. 2-D MC noise simulations are found to be feasible only if the current correlation functions decay on a subpicosecond scale, what is not always the case     

Scheduling algorithm for real-time imprecise computations tominimise maximum weighted errors using the linear programmingmethod

An optimal scheduling algorithm for imprecise systems is presented. The proposed algorithm aims at minimising the maximum weighted errors. A novel property of the algorithm is that the errors are evenly distributed among scheduled tasks. The complexity of the proposed algorithm is O(N³) in the worst case, where N is the number of tasks     

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     

A new architecture and a new metric for lightwave networks

The notion of a logically routed network was developed to overcome the bottlenecks encountered during the design of a large purely optical network. In the last few years, researchers have proposed the use of torus. Perfect shuffle, hypercube, de Bruijn graph, Kautz graph, and Cayley graph as an overlay structure on top of a purely optical network. All these networks have regular structures. Although regular structures have many virtues, it is often difficult in a realistic setting to meet these stringent structural requirements. In this paper, we propose generalized multimesh (GM), a semiregular structure, as an alternate to the proposed architectures. In terms of simplicity of interconnection and routing, this architecture is comparable to the torus network. However, the new architecture exhibits significantly superior topological properties to the torus. For example, whereas a two-dimensional (2-D) torus with N nodes has a diameter of Θ(N^0.5), a generalized multimesh network with the same number of nodes and links has a diameter of Θ(N^0.25). In this paper, we also introduce a new metric, flow number, that can be used to evaluate topologies for optical networks. For optical networks, a topology with a smaller flow number is preferable, as it is an indicator of the number of wavelengths necessary for full connectivity. We show that the flow numbers of a 2-D torus, a multimesh, and a de Bruijn network, are Θ(N^1.5), Θ(N^1.25), and Θ(N log N), respectively, where N is the number of nodes in the network. The advantage of the generalized multimesh over the de Bruijn network lies in the bet that, unlike the de Bruijn network, this network can be constructed for any number of nodes and is incrementally expandable     

Low complexity affine MMSE detector for iterative detection-decoding MIMO OFDM systems

Iterative turbo processing between detection and decoding shows near-capacity performance on a multiple-antenna system. Combining iterative processing with optimum front-end detection is particularly challenging because the front-end maximum a posteriori (MAP) algorithm has a computational complexity that is exponential. Sub-optimum detector such as the soft interference cancellation linear minimum mean square error (SIC-LMMSE) detector with near front-end MAP performance has been proposed in the literature. The asymptotic computational complexity of SIC-LMMSE is O(n_t ²n_r + n_tn_r ³ + n_tM_c2^Mc) per detection-decoding cycle where n_t is number of transmit antenna, nr is number of receive antenna, and Mc is modulation size. A lower complexity detector is the hard interference cancellation LMMSE (HIC-LMMSE) detector. HIC-LMMSE has asymptotic complexity of O(n_t ²n_r + n_tM_c2^Mc) but suffers extra performance degradation. In this paper, two front-end detection algorithms are introduced that not only achieve asymptotic computational complexity of O(n_t ²n_r + n_tn_r ² [Gamma (beta) + 1] + n_tM_c2^Mc) where Gamma(beta) is a function with discrete output {-1, 2, 3, ...,n_t} and O(n_tM_c2^Mc) respectively. Simulation results demonstrate that the proposed low complexity detection algorithms offer exactly same performance as their full complexity counterpart in an iterative receiver while being computational more efficient.     

Double $phi$-Step $theta$-Scanning Technique for Spherical Near-Field Antenna Measurements

Probe-corrected spherical near-field antenna measurements with an arbitrary probe set certain requirements on an applicable scanning technique. The computational complexity of the general high-order probe correction technique for an arbitrary probe, that is based on the Phi scanning, is O(N⁴), where N is proportional to the radius of the antenna under test (AUT) minimum sphere in wavelengths. With the present knowledge, the computational complexity of the probe correction for arbitrary probes in the case of the thetas scanning is O(N^-6), which is typically not acceptable. This paper documents a specific double Phi-step thetas scanning technique for spherical near-field antenna measurements. This technique not only constitutes an alternative spherical scanning technique, but it also enables formulating an associated probe correction technique for arbitrary probes with the computational complexity of 0(N4) while the possibility for the exploitation of the advantages of the thetas scanning are maintained.     

Efficient and fast iterative reweighted least-squares nonrecursivefilters

An efficient and fast technique for designing L_p approximation filters using the iterative reweighted least-squares (IRLS) algorithm is proposed. This technique introduces an extra frequency response which implicitly includes the weighting function such that the filter coefficients can be obtained with O(N²) complexity     

A low-complexity zero-forcing CFO compensation scheme for OFDMA uplink systems

Similar to the conventional orthogonal frequencydivision multiplexing (OFDM) system, an OFDM multiple access (OFDMA) system will have a carrier frequency offset (CFO) problem. Since CFOs of all users are different, CFO compensation in the OFDMA uplink system is much more involved. A simple, yet efficient, method is the zero-forcing (ZF) compensation method. However, it involves an inverse of an N × N CFO-induced ICI matrix, where N is the number of subcarriers. Thus, the complexity can become very high when N is large, a case commonly seen in OFDMA systems. In this work, we propose a low-complexity ZF method to overcome the problem. The main idea is to use Newton's method to solve matrix inversion iteratively. We explore the structure of the CFOinduced ICI matrix and develop a method that can implement Newton's method with fast Fourier transforms (FFTs). As a result, the required computational complexity is significantly reduced from O(N³) to O(2N log₂N). Simulations show that, with only three iterations, the proposed method can have similar performance to the direct ZF method.