H.264 video coding standard has a significant performance better than the other standards are the adoption of variable block sizes, multiple reference frames, and the consideration of rate distortion optimization within the codec. However, these features incur a considerable complexity in the encoder for motion estimation. As for the multiple reference frames motion estimation, the increased computation is in proportion to the number of searched reference frames. In this paper, a fast multiple frame reference frames selection method is proposed for H.264 video coding. The proposed algorithm can efficiently determine the best reference frame from the allowed five reference frames. As determine the number of reference frames to search the motion using the correlation of the different block between the block of current frame and that of previous frame, this scheme can efficiently reduce the computational cost while keeping the similar quality and bit-rate. Simulation results show that the speed of the proposed method is faster than that of the original scheme adapted in JVT reference software JM95 while keeping the similar video quality and bit-rate.

The computational grid provides a promising platform for the deployment of various high-performance computing applications. Problem in implementing computational grid environments is how to effectively use various resources in the system, such as CPU cycle, memory, communication network, and data storage. There are many effective heuristic algorithms for scheduling in the computational grid, however most scheduling strategies have no theoretical guarantee at all. In this paper, a cost-based online scheduling algorithm is presented for job assignment in the grid environment with theoretical guarantee. Firstly, a scheduling framework is described, where the grid environment is characterized, and the online job model is defined. Secondly, the cost-based online scheduling algorithm is presented where costs of resources are exponential functions of their loads, and the performance of this algorithm is theoretically analyzed against the performance of the optimal offline algorithm. Finally, we implement the algorithm in the grid simulation environment, and compare the performance of the presented algorithm with the other three algorithms, and experimental results indicate that the cost-based online scheduling algorithm can outperform the other three online algorithms.

Genetic algorithms are a general problem-solving technique that has been widely used in computational biology. In this paper, we present a framework to map hierarchical parallel genetic algorithms for protein folding problems onto computational grids. By using this framework, the two level communication parts of hierarchical parallel genetic algorithms are separated. Thus both parts of the algorithm can evolve independently. This permits users to experiment with alternative communication models on different levels conveniently. The underlying programming techniques are based on generic programming, a programming technique suited for the generic representation of abstract concepts. This allows the framework to be built in a generic way at application level and thus provides good extensibility and flexibility. Experiments show that it can lead to significant runtime savings on PC clusters and computational grids.

An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n5), that the sum of the path lengths is O(n3), and that the length of the maximum path is O(n2). Computer experiment showed that the average execution time was O(n3.9) and, the average sum of the path lengths was O(n3.0).

An efficient clustering strategy for estimation of distribution algorithms (EDAs) is presented. It is used for properly fitting probabilistic models that play an important role in guiding search direction. To this end, a fitness-aided ordering scheme is devised for deciding the input sequence of samples (i.e., individuals) for clustering. It can effectively categorise the individuals by using the (available) information about fitness landscape. Moreover, a virtual leader is introduced for providing a reliable reference for measuring the distance from samples to its own cluster. The proposed algorithm incorporates them within the framework of random the leader algorithm (RLA). Experimental results demonstrate that the proposed approach is more effective than the existing ones with regard to probabilistic model fitting.

This paper presents new algorithms for the Tate pairing on a prime field. Recently, many pairing-based cryptographic schemes have been proposed. However, computing pairings incurs a high computational cost and represents the bottleneck to using pairings in actual protocols. This paper shows that the proposed algorithms reduce the cost of multiplication and inversion on an extension field, and reduce the number of calculations of the extended finite field. This paper also discusses the optimal algorithm to be used for each pairing parameter and shows that the total computational cost is reduced by 50% if k = 6 and 57% if k = 8.

The optical network is a promising approach for realizing a scalable backbone network. In backbone networks, survivability is very important because great volumes of traffic incur damage from faulty equipment. To address this issue, various recovery schemes have been proposed for optical backbone networks. Among those schemes, shared mesh restoration utilizes link bandwidth efficiently because the backup lightpaths share link bandwidth if they protect against different failures and are never utilized simultaneously. However, a route computation method for the backup lightpaths that promotes such bandwidth sharing is necessary to achieve efficient bandwidth utilization. This paper proposes a distributed route computation method for the backup lightpaths in shared mesh restoration. In this method, the link weight is estimated to be smaller if a backup lightpath newly established can share the link bandwidth with the backup lightpaths already accommodated in that link. The link weight can be calculated using the Markov Decision Theory. The bandwidth sharing between the backup lightpaths can be promoted by selecting the shortest route based on such modified link weights. The proposed method effectively realizes efficient utilization of the link bandwidth and achieves low loss rate of reliable lightpath establishment requests under the same traffic load. The proposed method restricts the amount of link state information advertised by the routing protocol and achieves a sufficiently small amount of route calculation.

In this paper, we propose an agent architecture for a combination of speculative computation and abduction. Speculative computation is a tentative computation when complete information for performing computation is not obtained. We use a default value to complement such incomplete information. Unlike usual default reasoning, the real value for the information can be obtained during the computation and the computation can be revised on the fly. In the previous work, we applied this technique to handling distributed problem solving under incomplete communication environments in the context of multi-agent systems and proposed correct procedures in abductive logic programming in terms of perfect model semantics. In the previous work, however, we regarded assumptions as defaults and used these assumptions for speculative computation. Thus, we could not perform hypothetical reasoning, that is, the original usage of abduction. In this paper, we extend our framework so that speculative computation and abduction can be both performed. As a result, our procedure becomes an extension of the abductive procedure developed by Kakas and Mancarella augmented by dynamic belief revision mechanism about outside world.

In this paper, we evaluate the computational complexity and the performance of the RAKE receivers for the Direct Sequence--Ultra Wideband (DS-UWB) with considering the accuracy of channel estimation in a multipath channel. As RAKE receivers for DS-UWB, we consider the maximal-ratio combining (MRC)-RAKE, the minimum mean square error (MMSE)-RAKE, and the MRC-RAKE-Equalizer that is the MRC-RAKE followed by a liner equalizer. Generally, if the channel estimation is perfect, as the number of fingers or taps increases, the performance of each receiver is improved, however the computational complexity of each receiver increases. In practice, the channel estimation is not perfect. The channel estimation error makes their performances degraded. Therefore, the performances of the RAKE receivers depend on the accuracy of channel estimation. Consequently, we evaluate the computational complexities and the Bit Error Rates (BERs) of MRC-RAKE, MMSE-RAKE, and MRC-RAKE-Equalizer with considering the accuracy of channel estimation for DS-UWB. We show that the accuracy of channel estimation affects the BER of each receiver significantly. We also show that when the accuracy of channel estimation is high, MRC-RAKE-Equalizer can achieve the better BER than MMSE-RAKE with less computational complexity, while MMSE-RAKE can achieve the better BER than MRC-RAKE-Equalizer when the accuracy of channel estimation is low.

In this letter, we propose a simplified step-by-step decoding algorithm for t-error-correcting binary Bose-Chaudhuri- Hocquenghem (BCH) codes based on logical analysis. Compared to the conventional step-by-step decoding algorithm, the computation complexity of this decoder is much less, since it significantly reduces the matrix calculation and the operations of multiplication.

A new method for logical structure analysis of document images is proposed in this paper as the basis for a document reader which can extract logical information from various printed documents. The proposed system consists of five basic modules: text line classification, object recognition, object segmentation, object grouping, and object modification. Emergent computation, which is a key concept of artificial life, is adopted for the cooperative interaction among modules in the system in order to achieve effective and flexible behavior of the whole system. It has three principal advantages over other methods: adaptive system configuration for various and complex logical structures, robust document analysis tolerant of erroneous feature detection, and feedback of high-level logical information to the low-level physical process for accurate analysis. Experimental results obtained for 150 documents show that the method is adaptable, robust, and effective for various document structures.

This paper proposes resource management in Layer 1 Virtual Private Networks (VPNs). We have been proposing Layer 1 VPNs that provide layer 1 services to multiple customers over the single optical network with per VPN control and management capabilities. We have proposed two resource management models for Layer 1 VPNs, which constitute different class of services. One is the shared model, where resources are shared among VPNs. The other is the dedicated model, where resources are explicitly pre-assigned to each VPN. In this paper, after introducing an overview of Layer 1 VPNs, we evaluate several path computation algorithms for these two models focusing on the multi layer network scenario. In the shared model, there are several existing studies for non-VPN cases, but considerations for VPN cases are not investigated. This paper evaluates algorithms originally proposed for non-VPN cases for use in VPN cases. Simulation results show that the path computation algorithm that works as saving layer 1 resources achieves better resource sharing effect. In the dedicated model, the problem is identical to non-VPN cases. There is one conventional algorithm, but amount of available resources is not well considered. We propose a novel path computation algorithm. Simulation results show effectiveness of our proposed algorithm against the conventional algorithm. Furthermore, resource usage efficiency of two resource management models is compared. We analyze and propose applicability of resource management models.

The demand for intra- and interdomain routing for multilayered networks such as those using generalized multiprotocol label switching (GMPLS) is strong. One of the features that is peculiar to GMPLS networks is that because several different domains, such as those of IP, ATM, and optical fiber, are combined with each other hierarchically, various routing policies, which are sometimes independent from underlying domains and sometimes taking the underlying domains' policies into consideration, are required. For example GMPLS's lower layer LSPs like lambda LSP are expected to be established independently before the upper-layer LSPs, like IP and MPLS LSPs, are established in the underlying domains. Another requirement for the GMPLS interdomain routing is lightening the burden for selecting the interdomain route, because there are a lot of demands to interconnect many GMPLS domains. In order to satisfy these demands, we propose a path computation server (PCS) that is special for the intra/interdomain routing of GMPLS networks. As a counterpart of the proposed interdomain routing, it is now becoming popular to apply OSPF to the GMPLS interdomain routing. Therefore, we compared the proposed interdomain routing with OSPF, and show the applicability of the routing to GMPLS networks.

A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.

We have proposed in [5] a practical blind channel identification algorithm for the white observation noise. In this paper, we examine the effectiveness of the algorithm given in [5] for the colored observation noise. The proposed algorithm utilizes Gram-Schmidt orthogonalization procedure and estimates (1) the channel order, (2) the noise variance and then (3) the channel impulse response with less computational complexity compared to the conventional algorithms using eigenvalue decomposition. It can be shown through numerical examples that the algorithm proposed in [5] is quite effective in the colored noise case.

This paper describes an estimation of the computational and memory complexities of Greengard-Rokhlin's Fast Multipole Algorithm (GRFMA). GRFMA takes a quad tree structure and six calculation processes. We consider a perfect a-ary tree structure and the number of floating-point operations for each calculation process. The estimation for both complexities shows that the perfect quad tree is the best and the perfect binary tree is the worst. When we apply GRFMA to the computation of realistic problems, volume scattering are the best case and surface scattering are the worst case. In the worst case, the computational and memory complexities of GRFMA are O(Llog2 L) and O(Llog L), respectively. The computational complexity of GRFMA is higher than that of the multilevel fast multipole algorithm.

This paper presents a framework for automatic video region-of-interest determination based on visual attention model. We view this work as a preliminary step towards the solution of high-level semantic video analysis. Facing such a challenging issue, in this work, a set of attempts on using video attention features and knowledge of computational media aesthetics are made. The three types of visual attention features we used are intensity, color, and motion. Referring to aesthetic principles, these features are combined according to camera motion types on the basis of a new proposed video analysis unit, frame-segment. We conduct subjective experiments on several kinds of video data and demonstrate the effectiveness of the proposed framework.

Effective trading with given pattern-based multi-predictors of stock price needs an intelligent asset allocation strategy. In this paper, we study a method of dynamic asset allocation, called the meta policy, which decides how much the proportion of asset should be allocated to each recommendation for trade. The meta policy makes a decision considering both the recommending information of multi-predictors and the current ratio of stock funds over the total asset. We adopt evolutionary computation to optimize the meta policy. The experimental results on the Korean stock market show that the trading system with the proposed meta policy outperforms other systems with fixed asset allocation methods.

A method is proposed to compute moments of distributed coupled RLC interconnects. Both uniform line models and non-uniform line models will be developed. Considering both self inductances and mutual inductances in multi-conductors, recursive moment computations formulae of lumped coupled RLC interconnects are extended to those of distributed coupled RLC interconnects. By using the moment computation technique in conjunction with the projection-based order reduction method, the inductive crosstalk noise waveform can be accurately and efficiently estimated. Fundamental developments of the proposed approach will be described. Simulation results demonstrate the improved accuracy of the proposed method over the traditional lumped methods.

There have been significant advances in computational electromagnetics (CEM) in the last decade for a variety of antennas and propagation problems. Improvements in single frequency techniques including the finite element method (FEM), the fast mulitipole moment (FMM) method, and the method of moments (MoM) have led to significant simulation capabilities on basic computing platforms. Similar advances have occurred with time domain methods including finite difference time domain (FDTD) methods, time domain integral equation (TDIE) methods, and time domain finite element (TD-FEM) methods. Very complex radiating and scattering structures in the presence of complex materials have been modeled with many of these approaches. Many commercial products have been made available through the efforts of many individuals. The CEM simulators have enabled virtual EM test ranges that have led to dramatic improvements in our understanding of antennas and propagation in complex environments and to the realization of many of their important applications.