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.

Monte Carlo methods for matrix computations on the grid

Many scientific and engineering applications involve inverting large matrices or solving systems of linear algebraic equations. Solving these problems with proven algorithms for direct methods can take very long to compute, as they depend on the size of the matrix. The computational complexity of the stochastic Monte Carlo methods depends only on the number of chains and the length of those chains. The computing power needed by inherently parallel Monte Carlo methods can be satisfied very efficiently by distributed computing technologies such as Grid computing. In this paper we show how a load balanced Monte Carlo method for computing the inverse of a dense matrix can be constructed, show how the method can be implemented on the Grid, and demonstrate how efficiently the method scales on multiple processors. (C) 2007 Elsevier 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.

Error analysis of a Monte Carlo algorithm for computing bilinear forms of matrix powers

In this paper we present error analysis for a Monte Carlo algorithm for evaluating bilinear forms of matrix powers. An almost Optimal Monte Carlo (MAO) algorithm for solving this problem is formulated. Results for the structure of the probability error are presented and the construction of robust and interpolation Monte Carlo algorithms are discussed. Results are presented comparing the performance of the Monte Carlo algorithm with that of a corresponding deterministic algorithm. The two algorithms are tested on a well balanced matrix and then the effects of perturbing this matrix, by small and large amounts, is studied.

The philosophy of W. Ross Ashby and its relationship to 'The Matrix'

Ashby was a keen observer of the world around him, as per his technological and psychiatrical developments. Over the years, he drew numerous philosophical conclusions on the nature of human intelligence and the operation of the brain, on artificial intelligence and the thinking ability of computers and even on science in general. In this paper, the quite profound philosophy espoused by Ashby is considered as a whole, in particular in terms of its relationship with the world as it stands now and even in terms of scientific predictions of where things might lead. A meaningful comparison is made between Ashby's comments and the science fiction concept of 'The Matrix' and serious consideration is given as to how much Ashby's ideas lay open the possibility of the matrix becoming a real world eventuality.

Comparison of the computational cost of a Monte Carlo and deterministic algorithm for computing bilinear forms of matrix powers

In this paper we consider bilinear forms of matrix polynomials and show that these polynomials can be used to construct solutions for the problems of solving systems of linear algebraic equations, matrix inversion and finding extremal eigenvalues. An almost Optimal Monte Carlo (MAO) algorithm for computing bilinear forms of matrix polynomials is presented. Results for the computational costs of a balanced algorithm for computing the bilinear form of a matrix power is presented, i.e., an algorithm for which probability and systematic errors are of the same order, and this is compared with the computational cost for a corresponding deterministic method.

A structural basis for the inhibition of collagen-stimulated platelet function by quercetin and structurally related flavonoids

Background and purpose: Molecular mechanisms underlying the links between dietary intake of flavonoids and reduced cardiovascular disease risk are only partially understood. Key events in the pathogenesis of cardiovascular disease, particularly thrombosis, are inhibited by these polyphenolic compounds via mechanisms such as inhibition of platelet activation and associated signal transduction, attenuation of generation of reactive oxygen species, enhancement of nitric oxide production and binding to thromboxane A2 receptors. In vivo, effects of flavonoids are mediated by their metabolites, but the effects and modes of action of these compounds are not well-characterized. A good understanding of flavonoid structure–activity relationships with regard to platelet function is also lacking. Experimental approach: Inhibitory potencies of structurally distinct flavonoids (quercetin, apigenin and catechin) and plasma metabolites (tamarixetin, quercetin-3′-sulphate and quercetin-3-glucuronide) for collagen-stimulated platelet aggregation and 5-hydroxytryptamine secretion were measured in human platelets. Tyrosine phosphorylation of total protein, Syk and PLCγ2 (immunoprecipitation and Western blot analyses), and Fyn kinase activity were also measured in platelets. Internalization of flavonoids and metabolites in a megakaryocytic cell line (MEG-01 cells) was studied by fluorescence confocal microscopy. Key results: The inhibitory mechanisms of these compounds included blocking Fyn kinase activity and the tyrosine phosphorylation of Syk and PLCγ2 following internalization. Principal functional groups attributed to potent inhibition were a planar, C-4 carbonyl substituted and C-3 hydroxylated C ring in addition to a B ring catechol moiety. Conclusions and implications: The structure–activity relationship for flavonoids on platelet function presented here may be exploited to design selective inhibitors of cell signalling.

Fibrillar superstructure from extended nanotapes formed by a collagen-stimulating peptide

The nanostructure of a peptide amphiphile in commercial use in anti-wrinkle creams is investigated. The peptide contains a matrikine, collagen-stimulating, pentapeptide sequence. Selfassembly into giant nanotapes is observed and the internal structure was found to comprise bilayers parallel to the flat tape surfaces.

A molecular T-matrix approach to calculating low-energy electron diffusion intensities for ordered molecular adsorbates

We present a novel approach to calculating Low-Energy Electron Diffraction (LEED) intensities for ordered molecular adsorbates. First, the intra-molecular multiple scattering is computed to obtain a non-diagonal molecular T-matrix. This is then used to represent the entire molecule as a single scattering object in a conventional LEED calculation, where the Layer Doubling technique is applied to assemble the different layers, including the molecular ones. A detailed comparison with conventional layer-type LEED calculations is provided to ascertain the accuracy of this scheme of calculation. Advantages of this scheme for problems involving ordered arrays of molecules adsorbed on surfaces are discussed.

Perturbation, extraction and refinement of invariant pairs for matrix polynomials

Generalizing the notion of an eigenvector, invariant subspaces are frequently used in the context of linear eigenvalue problems, leading to conceptually elegant and numerically stable formulations in applications that require the computation of several eigenvalues and/or eigenvectors. Similar benefits can be expected for polynomial eigenvalue problems, for which the concept of an invariant subspace needs to be replaced by the concept of an invariant pair. Little has been known so far about numerical aspects of such invariant pairs. The aim of this paper is to fill this gap. The behavior of invariant pairs under perturbations of the matrix polynomial is studied and a first-order perturbation expansion is given. From a computational point of view, we investigate how to best extract invariant pairs from a linearization of the matrix polynomial. Moreover, we describe efficient refinement procedures directly based on the polynomial formulation. Numerical experiments with matrix polynomials from a number of applications demonstrate the effectiveness of our extraction and refinement procedures.