An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Partition function for hindered, one-and multi-dimensional rotors

Writing the hindered rotor (hr) partition function as the trace of (rho) over cap = e(-beta(H) over cap hr), we approximate it by the sum of contributions from a set of points in position space. The contribution of the density matrix from each point is approximated by performing a local harmonic expansion around it. The highlight of this method is that it can be easily extended to multidimensional systems. Local harmonic expansion leads to a breakdown of the method a low temperatures. In order to calculate the partition function at low temperatures, we suggest a matrix multiplication procedure. The results obtained using these methods closely agree with the exact partition function at all temperature ranges. Our method bypasses the evaluation of eigenvalues and eigenfunctions and evaluates the density matrix for internal rotation directly. We also suggest a procedure to account for the antisymmetry of the total wavefunction in the same. (C) 2012 Elsevier B.V. All rights reserved.

Fast Likelihood Computation in Speech Recognition using Matrices

Acoustic modeling using mixtures of multivariate Gaussians is the prevalent approach for many speech processing problems. Computing likelihoods against a large set of Gaussians is required as a part of many speech processing systems and it is the computationally dominant phase for Large Vocabulary Continuous Speech Recognition (LVCSR) systems. We express the likelihood computation as a multiplication of matrices representing augmented feature vectors and Gaussian parameters. The computational gain of this approach over traditional methods is by exploiting the structure of these matrices and efficient implementation of their multiplication. In particular, we explore direct low-rank approximation of the Gaussian parameter matrix and indirect derivation of low-rank factors of the Gaussian parameter matrix by optimum approximation of the likelihood matrix. We show that both the methods lead to similar speedups but the latter leads to far lesser impact on the recognition accuracy. Experiments on 1,138 work vocabulary RM1 task and 6,224 word vocabulary TIMIT task using Sphinx 3.7 system show that, for a typical case the matrix multiplication based approach leads to overall speedup of 46 % on RM1 task and 115 % for TIMIT task. Our low-rank approximation methods provide a way for trading off recognition accuracy for a further increase in computational performance extending overall speedups up to 61 % for RM1 and 119 % for TIMIT for an increase of word error rate (WER) from 3.2 to 3.5 % for RM1 and for no increase in WER for TIMIT. We also express pairwise Euclidean distance computation phase in Dynamic Time Warping (DTW) in terms of matrix multiplication leading to saving of approximately of computational operations. In our experiments using efficient implementation of matrix multiplication, this leads to a speedup of 5.6 in computing the pairwise Euclidean distances and overall speedup up to 3.25 for DTW.

Fast acoustic likelihood computation using low-rank matrix approximation

Acoustic modeling using mixtures of multivariate Gaussians is the prevalent approach for many speech processing problems. Computing likelihoods against a large set of Gaussians is required as a part of many speech processing systems and it is the computationally dominant phase for LVCSR systems. We express the likelihood computation as a multiplication of matrices representing augmented feature vectors and Gaussian parameters. The computational gain of this approach over traditional methods is by exploiting the structure of these matrices and efficient implementation of their multiplication.In particular, we explore direct low-rank approximation of the Gaussian parameter matrix and indirect derivation of low-rank factors of the Gaussian parameter matrix by optimum approximation of the likelihood matrix. We show that both the methods lead to similar speedups but the latter leads to far lesser impact on the recognition accuracy. Experiments on a 1138 word vocabulary RM1 task using Sphinx 3.7 system show that, for a typical case the matrix multiplication approach leads to overall speedup of 46%. Both the low-rank approximation methods increase the speedup to around 60%, with the former method increasing the word error rate (WER) from 3.2% to 6.6%, while the latter increases the WER from 3.2% to 3.5%.

Dislocation dynamical approach to force fluctuations in nanoindentation experiments

We develop an approach that combines the power of nonlinear dynamics with the evolution equations for the mobile and immobile dislocation densities and force to explain force fluctuations in nanoindentation experiments. The model includes nucleation, multiplication, and propagation thresholds for mobile dislocations, and other well known dislocation transformation mechanisms. The model predicts all the generic features of nanoindentation such as the Hertzian elastic branch followed by several force drops of decreasing magnitudes, and residual plasticity after unloading. The stress corresponding to the elastic force maximum is close to the yield stress of an ideal solid. The predicted values for all the quantities are close to those reported by experiments. Our model allows us to address the indentation-size effect including the ambiguity in defining the hardness in the force drop dominated regime. At large indentation depths, the hardness remains nearly constant with a marginal decreasing trend.

Co-Exploration of NLA Kernels and Specification of Compute Elements in Distributed Memory CGRAs

Coarse Grained Reconfigurable Architectures (CGRA) are emerging as embedded application processing units in computing platforms for Exascale computing. Such CGRAs are distributed memory multi- core compute elements on a chip that communicate over a Network-on-chip (NoC). Numerical Linear Algebra (NLA) kernels are key to several high performance computing applications. In this paper we propose a systematic methodology to obtain the specification of Compute Elements (CE) for such CGRAs. We analyze block Matrix Multiplication and block LU Decomposition algorithms in the context of a CGRA, and obtain theoretical bounds on communication requirements, and memory sizes for a CE. Support for high performance custom computations common to NLA kernels are met through custom function units (CFUs) in the CEs. We present results to justify the merits of such CFUs.

Strain Gradient Effects on Deformation Strengthening Behavior of Particle Reinforced Metal Matrix Composites

Dislocation models with considering the mismatch of elastic modulus between matrix and reinforcing particles are used to determine the effective strain gradient \ita for particle reinforced metal matrix composites (MMCp) in the present research. Based on Taylor relation and the kinetics of dislocation multiplication, glide and annihilation, a strain gradient dependent constitutive equation is developed. By using this strain gradient-dependent constitutive equation, size-dependent deformation strengthening behavior is characterized. The results demonstrate that the smaller the particle size, the more excellent in the reinforcing effect. Some comparisons with the available experimental results demonstrate that the present approach is satisfactory.

Formation, microstructure and development of the localized shear deformation in low-carbon steels

An investigation has been made into the effect of microstructural parameters on the propensity for forming shear localization produced during high speed torsional testing by split Hopkinson bar with different average rates of 610, 650 and 1500 s(-1) in low carbon steels. These steels received the quenched, quenched and tempered as well as normalized treatments that provide wide microstructural parameters and mechanical properties. The results indicate that the occurrence of the shear localization is susceptible to the strength of the steels. In other words, the tendency of the quenched steel to form a shear band is higher than that of the other two steels. It is also found that there is a critical strain at which the shear localization occurs in the steels. The critical strain value is strongly dependent on the strength of the steels. Before arriving at this point, the material undergoes a slow work-hardening. After this point, the material suffers work-softening, corresponding to a process during which the deformation is gradually localized and eventually becomes spatially correlated to form a macroscopic shear band. Examinations by SEM reveal that the shear localization within the band involves a series of sequential crystallographic and non-crystallographic events including the change in crystal orientation, misorientation, generation and even perhaps damage in microstructures such as the initiation, growth and coalescence of the microcracks. It is expected that the sharp drop in the load-carrying capacity is associated with the growth and coalescence of the microcracks rather than the occurrence of the shear localization, but the shear localization is seen to accelerate the growth and coalescence of the microcracks. The thin foil observations by TEM reveal that the density of dislocations in the band is extremely high and the tangled arrangement and cell structure of dislocations tends to align along the shear direction. The multiplication and interaction of dislocations seems to be responsible for work-hardening of the steels. The avalanche of the dislocation cells corresponds to the sharp drop in shear stress at which the deformed specimen is broken. Double shear bands and kink bands are also observed in the present study. The principal band develops first and its width is narrower than that of the secondary band.

Vertical and seasonal distribution of phytoplankton in the Shen Reservoir Plateau State, Nigeria

The phytoplankton distribution of the Shen Reservoir, Bukuru in the Jos Plateau, Nigeria was monitored at 6 depths. Higher floral abundance occurred within the upper 00-03 meters with highest values at the first 1 meter. Bacillariophyceae and Dinophyceae recorded higher values in March-April with lower values in July and January respectively. Phytoplankton were most abundant in the rainy season. Secchi disc transparency was lowest in the peak of the rainy season (July) due to higher levels of suspended matter resulting from the increased run-off from surrounding farmlands of allochthonous materials as well as higher levels of phytoplankton population arising from the former factor. The low water temperature of December/January 15 degree C plus or minus 2 degree C might have depressed growth among the major groups of plankters but enhanced rapid multiplication of the Chlorophyta, Trachelomonas which showed a bloom at this season

Lake Kainji water hyacinth infestation and the control strategies

The paper documents the aquatic vascular plants situation of Lake Kainji, particularly with the invasion of water hyacinth (Eichhormia crassipes) hitherto alien to the lake system. The frequency of occurrence of some aquatic plants on Lake Kainji have increased whilst a few decreased over the period between 1984 and 1995. More than 53.6% of the lake surface has now been covered by aquatic vascular plants of which water hyacinth alone covered 30.6% (16.4% of the system). Apart from the characteristic rapid multiplication and biomass build-up of the plant, more than 9.1 clumps with a diameter range between 0.8-4cm enter the lake per minute. Thus more than 16.4ha per day or annually 6000ha of water hyacinth are added as drifts. Because of the peculiar hydrological cycle of the lake and the plant aggressiveness and invasiveness, NIFFR (with the support of the GTZ) had developed an approach of control which combines manual, biological, natural, boom construction and chemical measures. These are discussed

Produção in vitro e criopreservação de raízes de Cleome rosea Vahl (Capparaceae)

Cleome rosea é uma espécie nativa, de porte herbáceo, ocorrente em restingas brasileiras. Estudos recentes têm revelado o potencial medicinal da espécie para importantes propriedades farmacológicas, como por exemplo, as atividades anti-inflamatória, antigenotóxica, antiviral e antibacteriana. Porém, nos últimos anos, C. rosea não tem sido encontrada em várias regiões de seu ambiente natural, devido, principalmente, às ações antrópicas. Dessa forma, torna-se relevante o desenvolvimento de métodos de conservação que permitam o estudo e exploração das propriedades medicinais da espécie. O cultivo in vitro de raízes representa uma forma eficiente para produção de biomassa, devido ao rápido crescimento, produção estável de metabólitos, além de representar uma potencial fonte de explantes para a propagação em massa de diferentes espécies. O presente trabalho teve como objetivo a produção in vitro de culturas de raízes de C. rosea, associada à criopreservação, como forma de manutenção em longo prazo das culturas, monitorada através da análise de estabilidade genética. As culturas estabelecidas a partir de explantes radiculares de plantas propagadas in vitro de C. rosea demonstraram excelente capacidade de multiplicação de raízes em meio de cultura suplementado com o fitorregulador ANA, com manutenção dessa capacidade ao longo de sucessivas subculturas. Associado a esses resultados, o estabelecimento de protocolos de criopreservação pelo método de vitrificação resultou em elevados valores de frequência de recuperação do material após congelamento em nitrogênio líquido com as soluções de vitrificação PVS2 e PVS3. Os estudos de monitoramento da estabilidade genética, pela técnica de marcadores moleculares RAPD, revelaram a presença de polimorfismos significativos em uma das três culturas iniciadas a partir de raízes de C. rosea criopreservadas. Esses resultados demonstram as possibilidades de produção de raízes de C. rosea e conservação em longo prazo através da criopreservação, iniciando estudos inéditos para a espécie.

Rhythms of division of some algae in situ and in laboratory culture. [Translation from: Studii Cerc.Biol.(Bot.) 21, 61-65, 1969. ]

The rhythm of division of 9 species belonging to different groups of algae were analysed in situ and in the laboratory. The research which developed in different environmental conditions attempted to establish the capacity for multiplication and assimilation of chlorophyll on the part of the algae under study with a view to placing them in a culture. The results obtained showed that the green multicellular algae (eg. Ulothrix) and the blue algae (eg. Lyngbya, Oscillatoria) are able to produce an appreciable quantity of dry matter, just as the unicellular algae. At the same time it arises that amongst the numerous factors of the environment, temperature plays one of the most important roles in the process of multiplication.

MODIFIED ENGAGEMENT METHOD FOR MATRIX OPERATION

We describe a modified engagement method for matrix operation based on a two-dimensional crossed-ring interconnection network, Our method incorporates fewer steps than that reported by Bocker et al. [Appl. Opt. 22, 804 (1983)], and its performance is found to be the most efficient (minimum steps) in comparison with other systolic and/or engagement methods for matrix operation. Thus, it may be helpful for other optical and electronic implementations of matrix operations. One compact optoelectronic integrity approach for implementing the modified engagement method is briefly described. (C) 1995 Optical Society of America

Compact parallel optical modified-signed-digit arithmetic-logic array processor with electron-trapping device

A compact two-step modified-signed-digit arithmetic-logic array processor is proposed. When the reference digits are programmed, both addition and subtraction can be performed by the same binary logic operations regardless of the sign of the input digits. The optical implementation and experimental demonstration with an electron-trapping device are shown. Each digit is encoded by a single pixel, and no polarization is included. Any combinational logic can be easily performed without optoelectronic and electro-optic conversions of the intermediate results. The system is compact, general purpose, simple to align, and has a high signal-to-noise ratio. (C) 1999 Optical Society of America.

Two-step digit-set-restricted modified signed-digit addition-subtraction algorithm and its optoelectronic implementation

A novel, to our knowledge, two-step digit-set-restricted modified signed-digit (MSD) addition-subtraction algorithm is proposed. With the introduction of the reference digits, the operand words are mapped into an intermediate carry word with all digits restricted to the set {(1) over bar, 0} and an intermediate sum word with all digits restricted to the set {0, 1}, which can be summed to form the final result without carry generation. The operation can be performed in parallel by use of binary logic. An optical system that utilizes an electron-trapping device is suggested for accomplishing the required binary logic operations. By programming of the illumination of data arrays, any complex logic operations of multiple variables can be realized without additional temporal latency of the intermediate results. This technique has a high space-bandwidth product and signal-to-noise ratio. The main structure can be stacked to construct a compact optoelectronic MSD adder-subtracter. (C) 1999 Optical Society of America.