Parallel Monte Carlo algorithms for information retrieval

In any data mining applications, automated text and text and image retrieval of information is needed. This becomes essential with the growth of the Internet and digital libraries. Our approach is based on the latent semantic indexing (LSI) and the corresponding term-by-document matrix suggested by Berry and his co-authors. Instead of using deterministic methods to find the required number of first "k" singular triplets, we propose a stochastic approach. First, we use Monte Carlo method to sample and to build much smaller size term-by-document matrix (e.g. we build k x k matrix) from where we then find the first "k" triplets using standard deterministic methods. Second, we investigate how we can reduce the problem to finding the "k"-largest eigenvalues using parallel Monte Carlo methods. We apply these methods to the initial matrix and also to the reduced one. The algorithms are running on a cluster of workstations under MPI and results of the experiments arising in textual retrieval of Web documents as well as comparison of the stochastic methods proposed are presented. (C) 2003 IMACS. Published by Elsevier Science B.V. All rights reserved.

A sparse parallel hybrid Monte Carlo algorithm for matrix computations

In this paper we introduce a new algorithm, based on the successful work of Fathi and Alexandrov, on hybrid Monte Carlo algorithms for matrix inversion and solving systems of linear algebraic equations. This algorithm consists of two parts, approximate inversion by Monte Carlo and iterative refinement using a deterministic method. Here we present a parallel hybrid Monte Carlo algorithm, which uses Monte Carlo to generate an approximate inverse and that improves the accuracy of the inverse with an iterative refinement. The new algorithm is applied efficiently to sparse non-singular matrices. When we are solving a system of linear algebraic equations, Bx = b, the inverse matrix is used to compute the solution vector x = B(-1)b. We present results that show the efficiency of the parallel hybrid Monte Carlo algorithm in the case of sparse matrices.

Computational complexity of weighted splitting schemes on parallel computers

In models of complicated physical-chemical processes operator splitting is very often applied in order to achieve sufficient accuracy as well as efficiency of the numerical solution. The recently rediscovered weighted splitting schemes have the great advantage of being parallelizable on operator level, which allows us to reduce the computational time if parallel computers are used. In this paper, the computational times needed for the weighted splitting methods are studied in comparison with the sequential (S) splitting and the Marchuk-Strang (MSt) splitting and are illustrated by numerical experiments performed by use of simplified versions of the Danish Eulerian model (DEM).

Empirical mode decomposition: a novel technique for the study of tremor time series

Tremor is a clinical feature characterized by oscillations of a part of the body. The detection and study of tremor is an important step in investigations seeking to explain underlying control strategies of the central nervous system under natural (or physiological) and pathological conditions. It is well established that tremorous activity is composed of deterministic and stochastic components. For this reason, the use of digital signal processing techniques (DSP) which take into account the nonlinearity and nonstationarity of such signals may bring new information into the signal analysis which is often obscured by traditional linear techniques (e.g. Fourier analysis). In this context, this paper introduces the application of the empirical mode decomposition (EMD) and Hilbert spectrum (HS), which are relatively new DSP techniques for the analysis of nonlinear and nonstationary time-series, for the study of tremor. Our results, obtained from the analysis of experimental signals collected from 31 patients with different neurological conditions, showed that the EMD could automatically decompose acquired signals into basic components, called intrinsic mode functions (IMFs), representing tremorous and voluntary activity. The identification of a physical meaning for IMFs in the context of tremor analysis suggests an alternative and new way of detecting tremorous activity. These results may be relevant for those applications requiring automatic detection of tremor. Furthermore, the energy of IMFs was visualized as a function of time and frequency by means of the HS. This analysis showed that the variation of energy of tremorous and voluntary activity could be distinguished and characterized on the HS. Such results may be relevant for those applications aiming to identify neurological disorders. In general, both the HS and EMD demonstrated to be very useful to perform objective analysis of any kind of tremor and can therefore be potentially used to perform functional assessment.

Control of a compliant two-axis robotic arm

It is common to make the links between actuators and robotic limbs as stiff as possible, in complete contrast to natural systems, where compliance is present. In the past, to create some compliance in a drive, springs have been added to the link between the actuator and load. Many of these springs have been in series with the drive, but recently a more 'biological' approach has been taken where two springs have been used in parallel to counteract each other. This paper describes the application of parallel extension springs in a robot arm in order to give it compliance. Advantages and disadvantages of this application are discussed, along with various control strategies.

Parallel implementation and one year experiments with the Danish Eulerian Model

Large scale air pollution models are powerful tools, designed to meet the increasing demand in different environmental studies. The atmosphere is the most dynamic component of the environment, where the pollutants can be moved quickly on far distnce. Therefore the air pollution modeling must be done in a large computational domain. Moreover, all relevant physical, chemical and photochemical processes must be taken into account. In such complex models operator splitting is very often applied in order to achieve sufficient accuracy as well as efficiency of the numerical solution. The Danish Eulerian Model (DEM) is one of the most advanced such models. Its space domain (4800 × 4800 km) covers Europe, most of the Mediterian and neighboring parts of Asia and the Atlantic Ocean. Efficient parallelization is crucial for the performance and practical capabilities of this huge computational model. Different splitting schemes, based on the main processes mentioned above, have been implemented and tested with respect to accuracy and performance in the new version of DEM. Some numerical results of these experiments are presented in this paper.

A comparative study of Java and C performance in two large-scale parallel applications

In the 1990s the Message Passing Interface Forum defined MPI bindings for Fortran, C, and C++. With the success of MPI these relatively conservative languages have continued to dominate in the parallel computing community. There are compelling arguments in favour of more modern languages like Java. These include portability, better runtime error checking, modularity, and multi-threading. But these arguments have not converted many HPC programmers, perhaps due to the scarcity of full-scale scientific Java codes, and the lack of evidence for performance competitive with C or Fortran. This paper tries to redress this situation by porting two scientific applications to Java. Both of these applications are parallelized using our thread-safe Java messaging system—MPJ Express. The first application is the Gadget-2 code, which is a massively parallel structure formation code for cosmological simulations. The second application uses the finite-domain time-difference method for simulations in the area of computational electromagnetics. We evaluate and compare the performance of the Java and C versions of these two scientific applications, and demonstrate that the Java codes can achieve performance comparable with legacy applications written in conventional HPC languages. Copyright © 2009 John Wiley & Sons, Ltd.

A parallel convolutional coder including embedded puncturing with application to consumer devices

As consumers demand more functionality) from their electronic devices and manufacturers supply the demand then electrical power and clock requirements tend to increase, however reassessing system architecture can fortunately lead to suitable counter reductions. To maintain low clock rates and therefore reduce electrical power, this paper presents a parallel convolutional coder for the transmit side in many wireless consumer devices. The coder accepts a parallel data input and directly computes punctured convolutional codes without the need for a separate puncturing operation while the coded bits are available at the output of the coder in a parallel fashion. Also as the computation is in parallel then the coder can be clocked at 7 times slower than the conventional shift-register based convolutional coder (using DVB 7/8 rate). The presented coder is directly relevant to the design of modern low-power consumer devices

Applying autonomic computing concepts to parallel computing using intelligent agents

The work reported in this paper is motivated by the fact that there is a need to apply autonomic computing concepts to parallel computing systems. Advancing on prior work based on intelligent cores [36], a swarm-array computing approach, this paper focuses on ‘Intelligent agents’ another swarm-array computing approach in which the task to be executed on a parallel computing core is considered as a swarm of autonomous agents. A task is carried to a computing core by carrier agents and is seamlessly transferred between cores in the event of a predicted failure, thereby achieving self-ware objectives of autonomic computing. The feasibility of the proposed swarm-array computing approach is validated on a multi-agent simulator.

Uniformization of affine dependence programs for parallel embedded system design

This paper is concerned with the uniformization of a system of afine recurrence equations. This transformation is used in the design (or compilation) of highly parallel embedded systems (VLSI systolic arrays, signal processing filters, etc.). In this paper, we present and implement an automatic system to achieve uniformization of systems of afine recurrence equations. We unify the results from many earlier papers, develop some theoretical extensions, and then propose effective uniformization algorithms. Our results can be used in any high level synthesis tool based on polyhedral representation of nested loop computations.

Electronic transitions and bonding properties in a series of five-coordinate “16-electron” complexes [Mn(CO)3(L2)]− (L2=chelating redox-active π-donor ligand)

In this article we present for the first time accurate density functional theory (DFT) and time-dependent (TD) DFT data for a series of electronically unsaturated five-coordinate complexes [Mn(CO)(3)(L-2)](-), where L-2 stands for a chelating strong pi-donor ligand represented by catecholate, dithiolate, amidothiolate, reduced alpha-diimine (1,4-dialkyl-1,4-diazabutadiene (R-DAB), 2,2'-bipyridine) and reduced 2,2'-biphosphinine types. The single-crystal X-ray structure of the unusual compound [Na(BPY)][Mn(CO)(3)(BPY)]center dot Et2O and the electronic absorption spectrum of the anion [Mn(CO)(3)(BPY)](-) are new in the literature. The nature of the bidentate ligand determines the bonding in the complexes, which varies between two limiting forms: from completely pi-delocalized diamagnetic {(CO)(3)Mn-L-2}(-) for L-2 = alpha-diimine or biphosphinine, to largely valence-trapped {(CO)(3)Mn-1-L-2(2-)}(-) for L-2(2-) = catecholate, where the formal oxidation states of Mn and L-2 can be assigned. The variable degree of the pi-delocalization in the Mn(L-2) chelate ring is indicated by experimental resonance Raman spectra of [Mn(CO)(3)(L-2)](-) (L-2=3,5-di-tBu-catecholate and iPr-DAB), where accurate assignments of the diagnostically important Raman bands have been aided by vibrational analysis. The L-2 = catecholate type of complexes is known to react with Lewis bases (CO substitution, formation of six-coordinate adducts) while the strongly pi-delocalized complexes are inert. The five-coordinate complexes adopt usually a distorted square pyramidal geometry in the solid state, even though transitions to a trigonal bipyramid are also not rare. The experimental structural data and the corresponding DFT-computed values of bond lengths and angles are in a very good agreement. TD-DFT calculations of electronic absorption spectra of the studied Mn complexes and the strongly pi-delocalized reference compound [Fe(CO)(3)(Me-DAB)] have reproduced qualitatively well the experimental spectra. Analyses of the computed electronic transitions in the visible spectroscopic region show that the lowest-energy absorption band always contains a dominant (in some cases almost exclusive) contribution from a pi(HOMO) -> pi*(LUMO) transition within the MnL2 metallacycle. The character of this optical excitation depends strongly on the composition of the frontier orbitals, varying from a partial L-2 -> Mn charge transfer (LMCT) through a fully delocalized pi(MnL2) -> pi*(MnL2) situation to a mixed (CO)Mn -> L-2 charge transfer (LLCT/MLCT). The latter character is most apparent in the case of the reference complex [Fe(CO)(3)(Me-DAB)]. The higher-lying, usually strongly mixed electronic transitions in the visible absorption region originate in the three lower-lying occupied orbitals, HOMO - 1 to HOMO - 3, with significant metal-d contributions. Assignment of these optical excitations to electronic transitions of a specific type is difficult. A partial LLCT/MLCT character is encountered most frequently. The electronic absorption spectra become more complex when the chelating ligand L-2, such as 2,2'-bipyridine, features two or more closely spaced low-lying empty pi* orbitals.

Electronic properties of 4,4 ',5,5 '-tetramethyl-2,2 '-biphosphinine (tmbp) in the redox series fac-[Mn(Br)(CO)(3)(tmbp)], [Mn(CO)(3)(tmbp)](2), and [Mn(CO)(3)(tmbp)](-): crystallographic, spectroelectrochemical, and DFT computational study

Stepwise electrochemical reduction of the complex fac-[Mn(Br)(CO)(3)(tmbp)] (tmbp = 4,4',5,5'-tetramethyl-2,2'-biphosphinine) produces the dimer [Mn(CO)(3)(tmbp)](2) and the five-coordinate anion [Mn(CO)(3)(tmbp)](-). All three members of the redox series have been characterized by single-crystal X-ray diffraction. The crystallographic data provide valuable insight into the localization of the added electrons on the (carbonyl)manganese and tmbp centers. In particular, the formulation of the two-electron-reduced anion as [Mn-0(CO)(3)(tmbp(-))](-) also agrees with the analysis of its IR nu(CO) wavenumbers and with the results of density functional theoretical (DFT) MO calculations on this compound. The strongly delocalized pi-bonding in the anion stabilizes its five-coordinate geometry and results in the appearance of several mixed Mn-to-tmbp charge-transfer/IL(tmbp) transitions in the near-UV-vis spectral region. A thorough voltammetric and UV-vis/IR spectroelectrochemical study of the reduction path provided evidence for a direct formation of [Mn(CO)(3)(tmbp)](-) via a two-electron ECE mechanism involving the [Mn(CO)(3)(tmbp)](.) radical transient. At ambient temperature [Mn(CO)(3)(tmbp)](-) reacts rapidly with nonreduced fac-[Mn(Br)(CO)(3)(tmbp)] to produce [Mn(CO)(3)(tmbp)](2). Comparison with the analogous 2,2'-bipyridine complexes has revealed striking similarity in the bonding properties and reactivity, despite the stronger pi-acceptor character of the tmbp ligand.

Testing Turing's five minutes, parallel-paired imitation game

Purpose – The purpose of this paper is to consider Turing's two tests for machine intelligence: the parallel-paired, three-participants game presented in his 1950 paper, and the “jury-service” one-to-one measure described two years later in a radio broadcast. Both versions were instantiated in practical Turing tests during the 18th Loebner Prize for artificial intelligence hosted at the University of Reading, UK, in October 2008. This involved jury-service tests in the preliminary phase and parallel-paired in the final phase. Design/methodology/approach – Almost 100 test results from the final have been evaluated and this paper reports some intriguing nuances which arose as a result of the unique contest. Findings – In the 2008 competition, Turing's 30 per cent pass rate is not achieved by any machine in the parallel-paired tests but Turing's modified prediction: “at least in a hundred years time” is remembered. Originality/value – The paper presents actual responses from “modern Elizas” to human interrogators during contest dialogues that show considerable improvement in artificial conversational entities (ACE). Unlike their ancestor – Weizenbaum's natural language understanding system – ACE are now able to recall, share information and disclose personal interests.