Implementation and performance of the fast Hartley transform

The authors investigated the implementation aspects of the fast Hartley transform (FHT) in both software and hardware. They describe the modifications required to convert existing fast Fourier transform (FFT) programs to execute FHTs, showing the ease with which these modifications can be implemented. They compare execution time and memory storage requirements of both transforms and present power spectrum calculation and convolution as illustrative examples to compare the performances of the two transform techniques. They also give a comparative survey of the performances of various microprocessors and digital signal processors in FFT and FHT computation     

Efficient algorithms for computing the new Mersenne number transform

The new Mersenne number transform (NMNT) has proved to be an important number theoretic transform (NTT) used for error-free calculation of convolutions and correlations. Its main feature is that for a suitable Mersenne prime number (p), the allowed power-of-two transform lengths can be very large. In this paper, efficient radix-2² decimation-in-time and in-frequency algorithms for fast calculation of the NMNT are developed by deriving the appropriate mathematical relations in finite field and applying principles of the twiddle factor unscrambling technique. The proposed algorithms achieve both the regularity of radix-2 algorithm and the efficiency of radix-4 algorithm and can be applied to any powers of two transform lengths with simple bit reversing for ordering the output sequence. Consequently, the proposed algorithms possess the desirable properties such as simplicity and in-place computation. The validity of the proposed algorithms has been verified through examples involving large integer multiplication and digital filtering applications, using both the NMNT and the developed algorithms.     

A comparison of fast inverse discrete cosine transform algorithms

The discrete cosine transform (DCT) is often applied to image compression to decorrelate picture data before quantization. This decorrelation results in many of the quantized transform coefficients equaling zero, hence the compression gain. At the decoder, very few nonzero quantized transform coefficients are received, so the input to the inverse DCT is sparse, greatly reducing the required computation. This paper describes different styles of implementations of fast inverse DCTs designed especially for sparse data and compares them on workstation processors.This research has been sponsored by ARPA     

Signal recognition: Fourier transform vs. Hartley transform

The new generic feature representation approach was utilized for Gaussian recognition. Approach consists of using simultaneously two new recognition features: real and imaginary Fourier components with taking into account the covariance between features.

Advanced time–frequency technique, short time Fourier transform was considered.

The recognition effectiveness between the new approach and Hartley based approach was compared. It was shown for Gaussian recognition that Hartley approach is not an optimal and is not even a particular case of the proposed approach. The use of the proposed approach provides an essential effectiveness gain in comparison with Hartley approach.     

Accuracy analysis of some fast Fourier transform algorithms for estimation of correlation functions

Translated from Kibernetika, No. 2, pp. 105–109, March–April, 1990.     

基于快速傅里叶变换的人体活动识别改进算法研究

主要探讨了人体活动识别KNN算法的改进方法,该方法通过快速傅里叶变换算法和相关性分析,把采集到的信号时域特性变成频域特性,从而实现了对人体活动模式的识别。     

Efficient algorithms of local discrete wavelet transform with Haar-like bases

In this paper, two new fast algorithms for calculating a local discrete wavelet transform for a one-dimensional signal based on the example of Haar’s wavelet basis are presented and their computational complexities are evaluated. The algorithms are compared with each other and with well-known algorithms of fast wavelet transform. Employment recommendations are given for each algorithm presented. Among other things the preference domains of these algorithms are shown, i.e., the parameters of wavelet transform calculating problem are specified so that these algorithms are computationally efficient. Conclusions regarding the advantages of the recursive algorithm over the alternative one and over the well-known algorithm of the fast wavelet transform are reached using the analysis of algorithmic complexities as the base and with regard to additional possibilities of the recursive algorithm. The extension of the algorithms considered to a two-dimensional case is presented. Vasilii N. Kopenkov. Was born in 1978. He was graduated in Samara State Aerospace University in 2001. At present time he works as an assistant on chair of geoinformatics in SSAU and as a junior research assistant in Institute of Image Processing Systems RAS. Head interests: image processing, earth remote sensing data and pattern recognition, geoinformatic systems. Author of 17 publications, including 7 articles. Member of the Russian Association Pattern Recognition and Image Analysis.     

An algebraic method for synthesizing fast algorithms of discrete cosine transform of arbitrary size

An algebraic method for synthesizing fast algorithms of the discrete cosine transform (DCT) of arbitrary size is proposed. The method is based on the polynomial algebra $\mathbb{F}{{[x]} \mathord{\left/ {\vphantom {{[x]} {p(x)}}} \right. \kern-0em} {p(x)}}$ associated with the DCT. The fast DCT algorithm comes as a result of the step-by-step decomposition of this algebra. In turn, the decomposition requires step-by-step factorization of the polynomial p(x). This problem is solved using Galois??s theory, which allows finding all the subfields of the splitting field of the polynomial p(x) where p(x) can be factorized.     

Performance bound of Walsh-Hadamard transform for feature selection and compression and some related fast algorithms

A fast algorithm of finding the diagonal elements of the covariance matrix of the two-dimensional Walsh-Hadamard (WH) transform of data is described. Its usefulness and other interesting properties of the WH transform are discussed. The performance of the WH transform is compared with the Karhunen-Loeve transform for a first-order stationary Markov process.     

Efficient algorithms for clique problems

The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:

•

We give an algorithm for k-clique that runs in O(nk/(εlogn)^k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.

•

Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u₁,…,uk/2} and V={v₁,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.

     

A VLSI constant geometry architecture for the fast Hartley andFourier transforms

An application-specific architecture for the parallel calculation of the decimation in time and radix 2 fast Hartley (FHT) and Fourier (FFT) transforms is presented. A real sequence with N=2ⁿ data items is considered as input. The system calculates the FHT and the FFT in n and n+1 stages. respectively. The modular and regular parallel architecture is based on a constant geometry algorithm using butterflies of four data items and the perfect unshuffle permutation. With this permutation, the mapping of the algorithm in VLSI technology is simplified and the communications among processors are minimized. Organization of the processor memory based on first-in, first-out (FIFO) queues facilitates a systolic data flow and permits the implementation in a direct way of the complex data movements and address sequences of the transforms. This is accomplished by means of simple multiplexing operations, using hardwired control. The total calculation time is (Nlog₂N)/4Q cycles for the FHT and N(1+log₂N)/4Q cycles for the FFT, where Q is the number of processors ( Q= 2^q, Q⩽N/4)     

Efficient algorithms for common transversals

Suppose we are given a set S of n (possibly intersecting) simple objects in the plane such that, for every pair of objects in S, the intersection of the boundaries of these two objects has O(1) connected components. We consider the problem of determining whether there exists a straight line that goes through every object in S. We give an O(n log n γ (n)) time algorithm for this problem, where γ(n) is a very slowly growing function of n. In many cases, our algorithm runs in O(n log n) time. Previously, only special cases of this problem were considered: the case when every object is a straight-line segment (Edelsbrunner et al., 1982), the case when the objects are equal-radius circles (Bajaj and Li, 1983), and the case when objects all maintain the same orientation (Edelsbrunner, 1985). All these cases follow from our general approach, which places no constraints on the size and/or configuration of the objects in S.     

Efficient algorithms for array redistribution

Dynamic redistribution of arrays is required very often in programs on distributed presents efficient algorithms for redistribution between different cyclic(k) distributions, as defined in High Performance Fortran. We first propose special optimized algorithms for a cyclic(x) to cyclic(y) redistribution when x is a multiple of y, or y is a multiple of x. We then propose two algorithms, called the GCD method and the LCM method, for the general cyclic(x) to cyclic(y) redistribution when there is no particular relation between x and y. We have implemented these algorithms on the Intel Touchstone Delta, and find that they perform well for different array sizes and number of processors     

三相电气参量快速和高精度的测量算法

提出了一种快速富里叶变换FFT算法来测量电力系统基波频率和其它谐波频率的实时值,进而计算出三相电压和电流的有效值与相位的实际值。由于电力系统参数随时都在变化,非正弦信号的系统基波频率不可能是一个确定的值,采用未确定的系统基波频率来采样和测量非正弦信号变化的三相电压和电流将引起很大的误差。因此,提出先准确测量非正弦信号的系统基波频率,然后,采用准确的系统基波频率来采样三相电压和电流,进而再计算三相电压和电流的有效值与相位的实际值、有功功率与电能、无功功率与电能等。这种算法不仅大大缩短计算时间,而且提高了测量的精度,测量精度可以达到0.1%或更高。实例计算的仿真结果及实际应用系统的运行数据都证明:这种算法的可靠性、准确性和快速性。     

Efficient scheduling algorithms for real-time multiprocessorsystems

Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an empty partial schedule, each step of the search extends the current partial schedule by including one of the tasks yet to be scheduled. The heuristic functions used in the algorithm actively direct the search for a feasible schedule, i.e. they help choose the task that extends the current partial schedule. Two scheduling algorithms are evaluated by simulation. To extend the current partial schedule, one of the algorithms considers, at each step of the search, all the tasks that are yet to be scheduled as candidates. The second focuses its attention on a small subset of tasks with the shortest deadlines. The second algorithm is shown to be very effective when the maximum allowable scheduling overhead is fixed. This algorithm is hence appropriate for dynamic scheduling in real-time systems     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and unicycular graphs. Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.Part of this work was done while the first author was at the University of Illinois, Urbana-Champaign, the second author was at Carnegie-Mellon University, and the third author was at the Hebrew University and the Courant Institute of Mathematical Sciences, New York University. A preliminary version of this work was presented at the 1986 International Conference on Parallel Processing.     

Efficient EREW PRAM algorithms for parentheses-matching

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log² n) employing O(n/(log n)) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/(log n)) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, the last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms     

Efficient algorithms for large-scale temporal aggregation

The ability to model time-varying natures is essential to many database applications such as data warehousing and mining. However, the temporal aspects provide many unique characteristics and challenges for query processing and optimization. Among the challenges is computing temporal aggregates, which is complicated by having to compute temporal grouping. We introduce a variety of temporal aggregation algorithms that overcome major drawbacks of previous work. First, for small-scale aggregations, both the worst-case and average-case processing time have been improved significantly. Second, for large-scale aggregations, the proposed algorithms can deal with a database that is substantially larger than the size of available memory. Third, the parallel algorithm designed on a shared-nothing architecture achieves scalable performance by delivering nearly linear scale-up and speed-up, even at the presence of data skew. The contributions made in this paper are particularly important because the rate of increase in database size and response time requirements has out-paced advancements in processor and mass storage technology.