A computationally efficient technique for data-clustering

A computationally efficient agglomerative clustering algorithm based on multilevel theory is presented. Here, the data set is divided randomly into a number of partitions. The samples of each such partition are clustered separately using hierarchical agglomerative clustering algorithm to form sub-clusters. These are merged at higher levels to get the final classification. This algorithm leads to the same classification as that of hierarchical agglomerative clustering algorithm when the clusters are well separated. The advantages of this algorithm are short run time and small storage requirement. It is observed that the savings, in storage space and computation time, increase nonlinearly with the sample size.

A hybrid clustering procedure for concentric and chain-like clusters

K-means algorithm is a well known nonhierarchical method for clustering data. The most important limitations of this algorithm are that: (1) it gives final clusters on the basis of the cluster centroids or the seed points chosen initially, and (2) it is appropriate for data sets having fairly isotropic clusters. But this algorithm has the advantage of low computation and storage requirements. On the other hand, hierarchical agglomerative clustering algorithm, which can cluster nonisotropic (chain-like and concentric) clusters, requires high storage and computation requirements. This paper suggests a new method for selecting the initial seed points, so that theK-means algorithm gives the same results for any input data order. This paper also describes a hybrid clustering algorithm, based on the concepts of multilevel theory, which is nonhierarchical at the first level and hierarchical from second level onwards, to cluster data sets having (i) chain-like clusters and (ii) concentric clusters. It is observed that this hybrid clustering algorithm gives the same results as the hierarchical clustering algorithm, with less computation and storage requirements.

Ternary function and circuit design using ternary multiplexers

The recent trend towards minimizing the interconnections in large scale integration (LSI) circuits has led to intensive investigation in the development of ternary circuits and the improvement of their design. The ternary multiplexer is a convenient and useful logic module which can be used as a basic building block in the design of a ternary system. This paper discusses a systematic procedure for the simplification and realization of ternary functions using ternary multiplexers as building blocks. Both single level and multilevel multiplexing techniques are considered. The importance of the design procedure is highlighted by considering two specific applications, namely, the development of ternary adder/subtractor and TCD to ternary converter.

Parallelization of an unstructured data based cell centre finite volume code, HIFUN-3D

This work describes the parallelization of High Resolution flow solver on unstructured meshes, HIFUN-3D, an unstructured data based finite volume solver for 3-D Euler equations. For mesh partitioning, we use METIS, a software based on multilevel graph partitioning. The unstructured graph used for partitioning is associated with weights both on its vertices and edges. The data residing on every processor is split into four layers. Such a novel procedure of handling data helps in maintaining the effectiveness of the serial code. The communication of data across the processors is achieved by explicit message passing using the standard blocking mode feature of Message Passing Interface (MPI). The parallel code is tested on PACE++128 available in CFD Center

Grid interfacing of a photovoltaic system using a chain cell converter

With the rapid development of photovoltaic system installations and increased number of grid connected power systems, it has become imperative to develop an efficient grid interfacing instrumentation suitable for photovoltaic systems ensuring maximum power transfer. The losses in the power converter play an important role in the overall efficiency of a PV system. Chain cell converter is considered to be efficient as compared to PWM converters due to lower switching losses, modularized circuit layout, reduced voltage rating of the converter switches, reduced EMI. The structure of separate dc sources in chain cell converter is well suited for photovoltaic systems as there will b several separate PV modules in the PV array which can act as an individual dc source. In this work, a single phase multilevel chain cell converter is used to interface the photovoltaic array to a single phase grid at a frequency of 50Hz. Control algorithms are developed for efficient interfacing of the PV system with grid and isolating the PV system from grid under faulty conditions. Digital signal processor TMS320F 2812 is used to implement the control algorithms developed and for the generation of other control signals.

Secure Concurrency Control in Firm Real-Time Database Systems

Many real-time database applications arise in electronic financial services, safety-critical installations and military systems where enforcing security is crucial to the success of the enterprise. For real-time database systems supporting applications with firm deadlines, we investigate here the performance implications, in terms of killed transactions, of guaranteeing multilevel secrecy. In particular, we focus on the concurrency control (CC) aspects of this issue. Our main contributions are the following: First, we identify which among the previously proposed real-time CC protocols are capable of providing covert-channel-free security. Second, using a detailed simulation model, we profile the real-time performance of a representative set of these secure CC protocols for a variety of security-classified workloads and system configurations. Our experiments show that a prioritized optimistic CC protocol, OPT-WAIT, provides the best overall performance. Third, we propose and evaluate a novel "dual-CC" approach that allows the real-time database system to simultaneously use different CC mechanisms for guaranteeing security and for improving real-time performance. By appropriately choosing these different mechanisms, concurrency control protocols that provide even better performance than OPT-WAIT are designed. Finally, we propose and evaluate GUARD, an adaptive admission-control policy designed to provide fairness with respect to the distribution of killed transactions across security levels. Our experiments show that GUARD efficiently provides close to ideal fairness for real-time applications that can tolerate covert channel bandwidths of upto one bit per second.

Load balancing algorithms for an extended hypercube

Reduction of the execution time of a job through equitable distribution of work load among the processors in a distributed system is the goal of load balancing. Performance of static and dynamic load balancing algorithms for the extended hypercube, is discussed. Threshold algorithms are very well-known algorithms for dynamic load balancing in distributed systems. An extension of the threshold algorithm, called the multilevel threshold algorithm, has been proposed. The hierarchical interconnection network of the extended hypercube is suitable for implementing the proposed algorithm. The new algorithm has been implemented on a transputer-based system and the performance of the algorithm for an extended hypercube is compared with those for mesh and binary hypercube networks

A Sub-Nyquist Sampling Method For Computing The Level-crossing-times Of An Analog Signal: Theory And Applications

We address the problem of computing the level-crossings of an analog signal from samples measured on a uniform grid. Such a problem is important, for example, in multilevel analog-to-digital (A/D) converters. The first operation in such sampling modalities is a comparator, which gives rise to a bilevel waveform. Since bilevel signals are not bandlimited, measuring the level-crossing times exactly becomes impractical within the conventional framework of Shannon sampling. In this paper, we propose a novel sub-Nyquist sampling technique for making measurements on a uniform grid and thereby for exactly computing the level-crossing times from those samples. The computational complexity of the technique is low and comprises simple arithmetic operations. We also present a finite-rate-of-innovation sampling perspective of the proposed approach and also show how exponential splines fit in naturally into the proposed sampling framework. We also discuss some concrete practical applications of the sampling technique.

Automatic decomposition of unstructured meshes employing genetic algorithms for parallel FEM computations

Parallel execution of computational mechanics codes requires efficient mesh-partitioning techniques. These mesh-partitioning techniques divide the mesh into specified number of submeshes of approximately the same size and at the same time, minimise the interface nodes of the submeshes. This paper describes a new mesh partitioning technique, employing Genetic Algorithms. The proposed algorithm operates on the deduced graph (dual or nodal graph) of the given finite element mesh rather than directly on the mesh itself. The algorithm works by first constructing a coarse graph approximation using an automatic graph coarsening method. The coarse graph is partitioned and the results are interpolated onto the original graph to initialise an optimisation of the graph partition problem. In practice, hierarchy of (usually more than two) graphs are used to obtain the final graph partition. The proposed partitioning algorithm is applied to graphs derived from unstructured finite element meshes describing practical engineering problems and also several example graphs related to finite element meshes given in the literature. The test results indicate that the proposed GA based graph partitioning algorithm generates high quality partitions and are superior to spectral and multilevel graph partitioning algorithms.

A Seven-Level Inverter Topology for Induction Motor Drive Using Two-Level Inverters and Floating Capacitor Fed H-Bridges

A multilevel inverter topology for seven-level space vector generation is proposed in this paper. In this topology, the seven-level structure is realized using two conventional two-level inverters and six capacitor-fed H-bridge cells. It needs only two isolated dc-voltage sources of voltage rating V(dc)/2 where V(dc) is the dc voltage magnitude required by the conventional neutral point clamped (NPC) seven-level topology. The proposed topology is capable of maintaining the H-bridge capacitor voltages at the required level of V(dc)/6 under all operating conditions, covering the entire linear modulation and overmodulation regions, by making use of the switching state redundancies. In the event of any switch failure in H-bridges, this inverter can operate in three-level mode, a feature that enhances the reliability of the drive system. The two-level inverters, which operate at a higher voltage level of V(dc)/2, switch less compared to the H-bridges, which operate at a lower voltage level of V(dc)/6, resulting in switching loss reduction. The experimental verification of the proposed topology is carried out for the entire modulation range, under steady state as well as transient conditions.

Subnatural linewidth in a strongly-driven degenerate two-level system

We observe linewidths below the natural linewidth for a probe laser on a degenerate two-level F -> F' transition, when the same transition is driven by a strong control laser. We take advantage of the fact that each level of the transition is made of multiple magnetic sublevels, and use the phenomenon of electromagnetically induced transparency (EIT) or absorption ( EIA) in multilevel systems. Optical pumping by the control laser redistributes the population so that only a few sublevels contribute to the probe absorption, an explanation which is verified by a density-matrix analysis of the relevant sublevels. We observe more than a factor of 3 reduction in linewidth in the D(2) line of Rb in room-temperature vapor. Such subnatural features vastly increase the scope of applications of EIT, such as high-resolution spectroscopy and tighter locking of lasers to atomic transitions, since it is not always possible to find a suitable third level. (C) 2011 Elsevier B.V. All rights reserved.

Optimal Parameterized Policies for Resource Allocation in Communication Networks

The problem of finding optimal parameterized feedback policies for dynamic bandwidth allocation in communication networks is studied. We consider a queueing model with two queues to which traffic from different competing flows arrive. The queue length at the buffers is observed every T instants of time, on the basis of which a decision on the amount of bandwidth to be allocated to each buffer for the next T instants is made. We consider two different classes of multilevel closed-loop feedback policies for the system and use a two-timescale simultaneous perturbation stochastic approximation (SPSA) algorithm to find optimal policies within each prescribed class. We study the performance of the proposed algorithm on a numerical setting and show performance comparisons of the two optimal multilevel closedloop policies with optimal open loop policies. We observe that closed loop policies of Class B that tune parameters for both the queues and do not have the constraint that the entire bandwidth be used at each instant exhibit the best results overall as they offer greater flexibility in parameter tuning. Index Terms — Resource allocation, dynamic bandwidth allocation in communication networks, two-timescale SPSA algorithm, optimal parameterized policies. I.

Five-level inverter voltage-space phasor generation for an open-end winding induction motor drive

A topology for voltage-space phasor generation equivalent to a five-level inverter for an open-end winding induction motor is presented. The open-end winding induction motor is fed from both ends by two three-level inverters. The three-level inverters are realised by cascading two two-level inverters. This inverter scheme does not experience neutral-point fluctuations. Of the two three-level inverters only one will be switching at any instant in the lower speed ranges. In the multilevel carrier-based SPWM used for the proposed drive, a progressive discrete DC bias depending on the speed range is given to the reference wave to reduce the inverter switchings. The drive is implemented and tested with a 1 HP open-end winding induction motor and experimental results are presented.

A Space-Vector-Based Hysteresis Current Controller for a General n-Level Inverter-Fed Drive With Nearly Constant Switching Frequency Control

A current-error space-vector-based hysteresis current controller for a general n-level voltage-source inverter (VSI)-fed three-phase induction motor (IM) drive is proposed here, with control of the switching frequency variation for the full linear modulation range. The proposed current controller monitors the space-vector-based current error of an n-level VSI-fed IM to keep the current error within a parabolic boundary, using the information of the current triangular sector in which the tip of the reference vector lies. Information of the reference voltage vector is estimated using the measured current-error space vectors, along the alpha- and beta-axes. Appropriate dimension and orientation of this parabolic boundary ensure a switching frequency spectrum similar to that of a constant-switching-frequency voltage-controlled space vector pulsewidth modulation (PWM) (SVPWM)-based IM drive. Like SVPWM for multilevel inverters, the proposed controller selects inverter switching vectors, forming a triangular sector in which the tip of the reference vector stays, for the hysteresis PWM control. The sector in the n-level inverter space vector diagram, in which the tip of the fundamental stator voltage stays, is precisely detected, using the sampled reference space vector estimated from the instantaneous current-error space vectors. The proposed controller retains all the advantages of a conventional hysteresis controller such as fast current control, with smooth transition to the overmodulation region. The proposed controller is implemented on a five-level VSI-fed 7.5-kW IM drive.

Seventeen-Level Inverter Formed by Cascading Flying Capacitor and Floating Capacitor H-Bridges

A multilevel inverter for generating 17 voltage levels using a three-level flying capacitor inverter and cascaded H-bridge modules with floating capacitors has been proposed. Various aspects of the proposed inverter like capacitor voltage balancing have been presented in the present paper. Experimental results are presented to study the performance of the proposed converter. The stability of the capacitor balancing algorithm has been verified both during transients and steady-state operation. All the capacitors in this circuit can be balanced instantaneously by using one of the pole voltage combinations. Another advantage of this topology is its ability to generate all the voltages from a single dc-link power supply which enables back-to-back operation of converter. Also, the proposed inverter can be operated at all load power factors and modulation indices. Additional advantage is, if one of the H-bridges fail, the inverter can still be operated at full load with reduced number of levels. This configuration has very low dv/dt and common-mode voltage variation.