An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.

Focal plane analysis of the Knox-Thompson algorithm in speckle interferometry

For the specific case of binary stars, this paper presents signal-to-noise ratio (SNR) calculations for the detection of the parity (the side of the brighter component) of the binary using the double correlation method. This double correlation method is a focal plane version of the well-known Knox-Thompson method used in speckle interferometry. It is shown that SNR for parity detection using double correlation depends linearly on binary separation. This new result was entirely missed by previous analytical calculations dealing with a point source. It is concluded that, for magnitudes relevant to the present day speckle interferometry and for binary separations close to the diffraction limit, speckle masking has better SNR for parity detection.

A near-optimal initial seed value selection in K-means means algorithm using a genetic algorithm

The K-means algorithm for clustering is very much dependent on the initial seed values. We use a genetic algorithm to find a near-optimal partitioning of the given data set by selecting proper initial seed values in the K-means algorithm. Results obtained are very encouraging and in most of the cases, on data sets having well separated clusters, the proposed scheme reached a global minimum.

Nature of Cl center dot center dot center dot Cl Intermolecular Interactions via Experimental and Theoretical Charge Density Analysis:Correlation of Polar Flattening Effects with Geometry

The experimental charge density distribution in three compounds, 2-chloro-3-quinolinyl methanol, 2-chloro-3-hydroxypyridine, and 2-chloro-3-chloromethyl-8-methylquinoline, has been obtained using high-resolution X-ray diffraction data collected at 100 K based on the aspherical multipole modeling of electron density. These compounds represent type I (cis), type I (trans), and type II geometries, respectively, as defined for short Cl center dot center dot center dot Cl interactions. The experimental results are compared with the theoretical charge densities using theoretical structure factors obtained from a periodic quantum calculation at the B3LYP/6-31G** level. The topological features derived from the Bader's theory of atoms in molecules (AIM) approach unequivocally suggest that both cis and trans type I geometries show decreased repulsion, whereas type II geometry is attractive based on the nature of polar flattening of the electron density around the Cl atom.

A Parallel Progressive Refinement Image Rendering Algorithm on a Scalable Multithreaded VLSI Processor Array

In this paper we develop a multithreaded VLSI processor linear array architecture to render complex environments based on the radiosity approach. The processing elements are identical and multithreaded. They work in Single Program Multiple Data (SPMD) mode. A new algorithm to do the radiosity computations based on the progressive refinement approach[2] is proposed. Simulation results indicate that the architecture is latency tolerant and scalable. It is shown that a linear array of 128 uni-threaded processing elements sustains a throughput close to 0.4 million patches/sec.

Characterizing and recognizing weak visibility polygons

A polygon is said to be a weak visibility polygon if every point of the polygon is visible from some point of an internal segment. In this paper we derive properties of shortest paths in weak visibility polygons and present a characterization of weak visibility polygons in terms of shortest paths between vertices. These properties lead to the following efficient algorithms: (i) an O(E) time algorithm for determining whether a simple polygon P is a weak visibility polygon and for computing a visibility chord if it exist, where E is the size of the visibility graph of P and (ii) an O(n2) time algorithm for computing the maximum hidden vertex set in an n-sided polygon weakly visible from a convex edge.

Geometry and quadratic nonlinearity of charge transfer complexes in solution using depolarized hyper-Rayleigh scattering

We report large quadratic nonlinearity in a series of 1:1 molecular complexes between methyl substituted benzene donors and quinone acceptors in solution. The first hyperpolarizability, beta(HRS), which is very small for the individual components, becomes large by intermolecular charge transfer (CT) interaction between the donor and the acceptor in the complex. In addition, we have investigated the geometry of these CT complexes in solution using polarization resolved hyper-Rayleigh scattering (HRS). Using linearly (electric field vector along X direction) and circularly polarized incident light, respectively, we have measured two macroscopic depolarization ratios D = I-2 omega,I-X,I-X/I-2 omega,I-Z,I-X and D' = I-2 omega,I-X,I-C/I-2 omega,I-Z,I-C in the laboratory fixed XYZ frame by detecting the second harmonic scattered light in a polarization resolved fashion. The experimentally obtained first hyperpolarizability, beta(HRS), and the value of macroscopic depolarization ratios, D and D', are then matched with the theoretically deduced values from single and double configuration interaction calculations performed using the Zerner's intermediate neglect of differential overlap self-consistent reaction field technique. In solution, since several geometries are possible, we have carried out calculations by rotating the acceptor moiety around three different axes keeping the donor molecule fixed at an optimized geometry. These rotations give us the theoretical beta(HRS), D and D' values as a function of the geometry of the complex. The calculated beta(HRS), D, and D' values that closely match with the experimental values, give the dominant equilibrium geometry in solution. All the CT complexes between methyl benzenes and chloranil or 1,2-dichloro-4,5-dicyano-p-benzoquinone investigated here are found to have a slipped parallel stacking of the donors and the acceptors. Furthermore, the geometries are staggered and in some pairs, a twist angle as high as 30 degrees is observed. Thus, we have demonstrated in this paper that the polarization resolved HRS technique along with theoretical calculations can unravel the geometry of CT complexes in solution. (C) 2011 American Institute of Physics. doi:10.1063/1.3514922]

Geometry and quadratic nonlinearity of charge transfer complexes in solution: A theoretical study

In this paper, we have computed the quadratic nonlinear optical (NLO) properties of a class of weak charge transfer (CT) complexes. These weak complexes are formed when the methyl substituted benzenes (donors) are added to strong acceptors like chloranil (CHL) or di-chloro-di-cyano benzoquinone (DDQ) in chloroform or in dichloromethane. The formation of such complexes is manifested by the presence of a broad absorption maximum in the visible range of the spectrum where neither the donor nor the acceptor absorbs. The appearance of this visible band is due to CT interactions, which result in strong NLO responses. We have employed the semiempirical intermediate neglect of differential overlap (INDO/S) Hamiltonian to calculate the energy levels of these CT complexes using single and double configuration interaction (SDCI). The solvent effects are taken into account by using the self-consistent reaction field (SCRF) scheme. The geometry of the complex is obtained by exploring different relative molecular geometries by rotating the acceptor with respect to the fixed donor about three different axes. The theoretical geometry that best fits the experimental energy gaps, beta(HRS) and macroscopic depolarization ratios is taken to be the most probable geometry of the complex. Our studies show that the most probable geometry of these complexes in solution is the parallel displaced structure with a significant twist in some cases. (C) 2011 American Institute of Physics. doi:10.1063/1.3526748]

Lattice embedding and equilibrium geometry of metal-halogen chains in the two-band extended Hubbard model

Two-band extended Hubbard model studies show that the shift in optical gap of the metal-halogen (MX) chain upon embedding in a crystalline environment depends upon alternation in the site-diagonal electron-lattice interaction parameter (epsilon(M)) and the strength of electron-electron interactions at the metal site (U(M)). The equilibrium geometry studies on isolated chains show that the MX chains tend to distort for alternating epsilon(M) and small U(M) values.

Geometry of proline-containing alpha-helices in proteins

Crystal structure analysis of proline-containing alpha-helices in proteins has been carried out. High resolution crystal structures were selected from the Protein Data Bank. Apart from the standard internal parameters, some parameters which are specifically related to the bend in the helix due to proline have been developed and analyzed. Finally the position and nature of these helices and their interactions with the rest of the protein have been analyzed.

Concise row-pruning algorithm to invert a matrix

Presented here, in a vector formulation, is an O(mn2) direct concise algorithm that prunes/identifies the linearly dependent (ld) rows of an arbitrary m X n matrix A and computes its reflexive type minimum norm inverse A(mr)-, which will be the true inverse A-1 if A is nonsingular and the Moore-Penrose inverse A+ if A is full row-rank. The algorithm, without any additional computation, produces the projection operator P = (I - A(mr)- A) that provides a means to compute any of the solutions of the consistent linear equation Ax = b since the general solution may be expressed as x = A(mr)+b + Pz, where z is an arbitrary vector. The rank r of A will also be produced in the process. Some of the salient features of this algorithm are that (i) the algorithm is concise, (ii) the minimum norm least squares solution for consistent/inconsistent equations is readily computable when A is full row-rank (else, a minimum norm solution for consistent equations is obtainable), (iii) the algorithm identifies ld rows, if any, and reduces concerned computation and improves accuracy of the result, (iv) error-bounds for the inverse as well as the solution x for Ax = b are readily computable, (v) error-free computation of the inverse, solution vector, rank, and projection operator and its inherent parallel implementation are straightforward, (vi) it is suitable for vector (pipeline) machines, and (vii) the inverse produced by the algorithm can be used to solve under-/overdetermined linear systems.

An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes

We develop in this article the first actor-critic reinforcement learning algorithm with function approximation for a problem of control under multiple inequality constraints. We consider the infinite horizon discounted cost framework in which both the objective and the constraint functions are suitable expected policy-dependent discounted sums of certain sample path functions. We apply the Lagrange multiplier method to handle the inequality constraints. Our algorithm makes use of multi-timescale stochastic approximation and incorporates a temporal difference (TD) critic and an actor that makes a gradient search in the space of policy parameters using efficient simultaneous perturbation stochastic approximation (SPSA) gradient estimates. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal policy. (C) 2010 Elsevier B.V. All rights reserved.

Study Of Acoustic Source Localization Algorithm For Planar Arrays

The source localization algorithms in the earlier works, mostly used non-planar arrays. If we consider scenarios like human-computer communication, or human-television communication where the microphones need to be placed on the computer monitor or television front panel, i.e we need to use the planar arrays. The algorithm proposed in 1], is a Linear Closed Form source localization algorithm (LCF algorithm) which is based on Time Difference of Arrivals (TDOAs) that are obtained from the data collected using the microphones. It assumes non-planar arrays. The LCF algorithm is applied to planar arrays in the current work. The relationship between the error in the source location estimate and the perturbation in the TDOAs is derived using first order perturbation analysis and validated using simulations. If the TDOAs are erroneous, both the coefficient matrix and the data matrix used for obtaining source location will be perturbed. So, the Total least squares solution for source localization is proposed in the current work. The sensitivity analysis of the source localization algorithm for planar arrays and non-planar arrays is done by introducing perturbation in the TDOAs and the microphone locations. It is shown that the error in the source location estimate is less when we use planar array instead of the particular non-planar array considered for same perturbation in the TDOAs or microphone location. The location of the reference microphone is proved to be important for getting an accurate source location estimate if we are using the LCF algorithm.

Multi-Agent Rendezvous Algorithm with Rectilinear Decision Domain

The aim of this paper is to develop a computationally efficient decentralized rendezvous algorithm for a group of autonomous agents. The algorithm generalizes the notion of sensor domain and decision domain of agents to enable implementation of simple computational algorithms. Specifically, the algorithm proposed in this paper uses a rectilinear decision domain (RDD) as against the circular decision domain assumed in earlier work. Because of this, the computational complexity of the algorithm reduces considerably and, when compared to the standard Ando's algorithm available in the literature, the RDD algorithm shows very significant improvement in convergence time performance. Analytical results to prove convergence and supporting simulation results are presented in the paper.

Layered Tabu Search Algorithm for Large-MIMO Detection and a Lower Bound on ML Performance

In this paper, we are concerned with low-complexity detection in large multiple-input multiple-output (MIMO) systems with tens of transmit/receive antennas. Our new contributions in this paper are two-fold. First, we propose a low-complexity algorithm for large-MIMO detection based on a layered low-complexity local neighborhood search. Second, we obtain a lower bound on the maximum-likelihood (ML) bit error performance using the local neighborhood search. The advantages of the proposed ML lower bound are i) it is easily obtained for MIMO systems with large number of antennas because of the inherent low complexity of the search algorithm, ii) it is tight at moderate-to-high SNRs, and iii) it can be tightened at low SNRs by increasing the number of symbols in the neighborhood definition. Interestingly, the proposed detection algorithm based on the layered local search achieves bit error performances which are quite close to this lower bound for large number of antennas and higher-order QAM. For e. g., in a 32 x 32 V-BLAST MIMO system, the proposed detection algorithm performs close to within 1.7 dB of the proposed ML lower bound at 10(-3) BER for 16-QAM (128 bps/Hz), and close to within 4.5 dB of the bound for 64-QAM (192 bps/Hz).