Parallel Hybrid Monte Carlo Algorithms for Matrix Computations

In this paper we consider hybrid (fast stochastic approximation and deterministic refinement) algorithms for Matrix Inversion (MI) and Solving Systems of Linear Equations (SLAE). Monte Carlo methods are used for the stochastic approximation, since it is known that they are very efficient in finding a quick rough approximation of the element or a row of the inverse matrix or finding a component of the solution vector. We show how the stochastic approximation of the MI can be combined with a deterministic refinement procedure to obtain MI with the required precision and further solve the SLAE using MI. We employ a splitting A = D – C of a given non-singular matrix A, where D is a diagonal dominant matrix and matrix C is a diagonal matrix. In our algorithm for solving SLAE and MI different choices of D can be considered in order to control the norm of matrix T = D –1C, of the resulting SLAE and to minimize the number of the Markov Chains required to reach given precision. Further we run the algorithms on a mini-Grid and investigate their efficiency depending on the granularity. Corresponding experimental results are presented.

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.

Complexity of Monte Carlo algorithms for a class of integral equations

In this work we study the computational complexity of a class of grid Monte Carlo algorithms for integral equations. The idea of the algorithms consists in an approximation of the integral equation by a system of algebraic equations. Then the Markov chain iterative Monte Carlo is used to solve the system. The assumption here is that the corresponding Neumann series for the iterative matrix does not necessarily converge or converges slowly. We use a special technique to accelerate the convergence. An estimate of the computational complexity of Monte Carlo algorithm using the considered approach is obtained. The estimate of the complexity is compared with the corresponding quantity for the complexity of the grid-free Monte Carlo algorithm. The conditions under which the class of grid Monte Carlo algorithms is more efficient are given.

Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems

In this paper we analyse applicability and robustness of Markov chain Monte Carlo algorithms for eigenvalue problems. We restrict our consideration to real symmetric matrices. Almost Optimal Monte Carlo (MAO) algorithms for solving eigenvalue problems are formulated. Results for the structure of both - systematic and probability error are presented. It is shown that the values of both errors can be controlled independently by different algorithmic parameters. The results present how the systematic error depends on the matrix spectrum. The analysis of the probability error is presented. It shows that the close (in some sense) the matrix under consideration is to the stochastic matrix the smaller is this error. Sufficient conditions for constructing robust and interpolation Monte Carlo algorithms are obtained. For stochastic matrices an interpolation Monte Carlo algorithm is constructed. A number of numerical tests for large symmetric dense matrices are performed in order to study experimentally the dependence of the systematic error from the structure of matrix spectrum. We also study how the probability error depends on the balancing of the matrix. (c) 2007 Elsevier Inc. All rights reserved.

Experimental design and model construction algorithms for radial basis function networks

New construction algorithms for radial basis function (RBF) network modelling are introduced based on the A-optimality and D-optimality experimental design criteria respectively. We utilize new cost functions, based on experimental design criteria, for model selection that simultaneously optimizes model approximation, parameter variance (A-optimality) or model robustness (D-optimality). The proposed approaches are based on the forward orthogonal least-squares (OLS) algorithm, such that the new A-optimality- and D-optimality-based cost functions are constructed on the basis of an orthogonalization process that gains computational advantages and hence maintains the inherent computational efficiency associated with the conventional forward OLS approach. The proposed approach enhances the very popular forward OLS-algorithm-based RBF model construction method since the resultant RBF models are constructed in a manner that the system dynamics approximation capability, model adequacy and robustness are optimized simultaneously. The numerical examples provided show significant improvement based on the D-optimality design criterion, demonstrating that there is significant room for improvement in modelling via the popular RBF neural network.

Practical interface experiments with implant technology

In this paper results are shown to indicate the efficacy of a direct connection between the human nervous system and a computer network. Experimental results obtained thus far from a study lasting for over 3 months are presented, with particular emphasis placed on the direct interaction between the human nervous system and a piece of wearable technology. An overview of the present state of neural implants is given, as well as a range of application areas considered thus far. A view is also taken as to what may be possible with implant technology as a general purpose human-computer interface for the future.

Theoretical studies of the interface between water and Langmuir films of aliphatic alcohols

The interface between water and Langmuir films of long chain aliphatic molecules is investigated using accurate intermolecular potentials. The stabilities of various ice structures which could form at the interface are examined. Antiferroelectric ice is found to be the most stable, but this stability depends crucially on the first layer of water. Ferroelectric structures are found to collapse upon relaxation. Our model was not able to differentiate between the different nucleation properties of C31H63OH and C30H61OH. A better description of the alcohol–water interaction is probably required to account for this difference.

Amyloid formation: interface influence

The causes of pathological conditions such as Alzheimer’s and Parkinson’s diseases are becoming better understood. Proteins that misfold from their native structure to form aggregates of β-sheet fibrils — termed amyloid — are known1,2 to be implicated in these ‘amyloid diseases’. Understanding the early steps of fibril formation is critical, and the conditions, mechanism and kinetics of protein and peptide aggregation are being widely investigated through a variety of in vitro studies. Kinetic aspects of the dispersion of the protein or peptide in solution are thought to influence the fibrillization process by mass-transfer effects. In addition, mixing also leads to shear forces, which can influence fibril growth by perturbing the equilibrium between the isolated and aggregated proteins, causing existing fibrils to fragment and create new nuclei3. Writing in the Journal of the American Chemical Society, David Talaga and co-workers have now highlighted4 an additional factor that can influence the fibrillization of amyloid-forming proteins — the presence of hydrophobic interfaces.

Interaction of nitrogen dioxide (NO2) with a monolayer of oleic acid at the air–water interface – A simple proxy for atmospheric aerosol

The reactions between atmospheric oxidants and organic amphiphiles at the air water interface of an aerosol droplet may affect the size and critical supersaturation required for cloud droplet formation. We demonstrate that no reaction occurs between gaseous nitrogen dioxide (1000 ppm in air) and a monolayer of an insoluble amphiphile, oleic acid (cis-9-octadecenoic acid), at the air water interface which removes material from the air water interface. We present evidence that the NO2 isomerises the cis-9-octadecenoic (oleic) acid to trans-9-octadecenoic (elaidic) acid. The study presented here is important for future and previous studies of (1) the reaction between the nitrate radical, NO3, and thin organic films as NO2 is usually present in high concentrations in these experimental systems and (2) the effect of NO2 air pollution on the unsaturated fatty acids and lipids found at the air liquid surface of human lung lining fluid.

Handling single node failures using agents in computer clusters

The work reported in this paper is motivated towards handling single node failures for parallel summation algorithms in computer clusters. An agent based approach is proposed in which a task to be executed is decomposed to sub-tasks and mapped onto agents that traverse computing nodes. The agents intercommunicate across computing nodes to share information during the event of a predicted node failure. Two single node failure scenarios are considered. The Message Passing Interface is employed for implementing the proposed approach. Quantitative results obtained from experiments reveal that the agent based approach can handle failures more efficiently than traditional failure handling approaches.

New algorithms for synthesized design of optical filters

Chebyshev optical-filter algorithms for low-cost microcomputers have been improved. An offset ripple is now used for better transmission/matching in low-pass stacks. A prototype for narrowband filters is now more general and nearer practicability.