The complex step approximation to the Fréchet derivative of a matrix function

We show that the Fréchet derivative of a matrix function f at A in the direction E, where A and E are real matrices, can be approximated by Im f(A + ihE)/h for some suitably small h. This approximation, requiring a single function evaluation at a complex argument, generalizes the complex step approximation known in the scalar case. The approximation is proved to be of second order in h for analytic functions f and also for the matrix sign function. It is shown that it does not suffer the inherent cancellation that limits the accuracy of finite difference approximations in floating point arithmetic. However, cancellation does nevertheless vitiate the approximation when the underlying method for evaluating f employs complex arithmetic. The ease of implementation of the approximation, and its superiority over finite differences, make it attractive when specialized methods for evaluating the Fréchet derivative are not available, and in particular for condition number estimation when used in conjunction with a block 1-norm estimation algorithm.     

Spectral clustering and its use in bioinformatics

We formulate a discrete optimization problem that leads to a simple and informative derivation of a widely used class of spectral clustering algorithms. Regarding the algorithms as attempting to bi-partition a weighted graph with N vertices, our derivation indicates that they are inherently tuned to tolerate all partitions into two non-empty sets, independently of the cardinality of the two sets. This approach also helps to explain the difference in behaviour observed between methods based on the unnormalized and normalized graph Laplacian. We also give a direct explanation of why Laplacian eigenvectors beyond the Fiedler vector may contain fine-detail information of relevance to clustering. We show numerical results on synthetic data to support the analysis. Further, we provide examples where normalized and unnormalized spectral clustering is applied to microarray data—here the graph summarizes similarity of gene activity across different tissue samples, and accurate clustering of samples is a key task in bioinformatics.     

Strong convergence rates for backward Euler on a class of nonlinear jump-diffusion problems

We generalise the current theory of optimal strong convergence rates for implicit Euler-based methods by allowing for Poisson-driven jumps in a stochastic differential equation (SDE). More precisely, we show that under one-sided Lipschitz and polynomial growth conditions on the drift coefficient and global Lipschitz conditions on the diffusion and jump coefficients, three variants of backward Euler converge with strong order of one half. The analysis exploits a relation between the backward and explicit Euler methods.     

Computing the field of values and pseudospectra using the Lanczos method with continuation

The field of values and pseudospectra are useful tools for understanding the behaviour of various matrix processes. To compute these subsets of the complex plane it is necessary to estimate one or two eigenvalues of a large number of parametrized Hermitian matrices; these computations are prohibitively expensive for large, possibly sparse, matrices, if done by use of the QR algorithm. We describe an approach based on the Lanczos method with selective reorthogonalization and Chebyshev acceleration that, when combined with continuation and a shift and invert technique, enables efficient and reliable computation of the field of values and pseudospectra for large matrices. The idea of using the Lanczos method with continuation to compute pseudospectra is not new, but in experiments reported here our algorithm is faster and more accurate than existing algorithms of this type.This work was supported by Engineering and Physical Sciences Research Council grants GR/H/52139 and GR/H/94528.     

Parallel defect control

How can small-scale parallelism best be exploited in the solution of nonstiff initial value problems? It is generally accepted that only modest gains inefficiency are possible, and it is often the case that “fast” parallel algorithms have quite crude error control and stepsize selection components. In this paper we consider the possibility of using parallelism to improvereliability andfunctionality rather than efficiency. We present an algorithm that can be used with any explicit Runge-Kutta formula. The basic idea is to take several smaller substeps in parallel with the main step. The substeps provide an interpolation facility that is essentially free, and the error control strategy can then be based on a defect (residual) sample. If the number of processors exceeds (p ? 1)/2, wherep is the order of the Runge-Kutta formula, then the interpolant and the error control scheme satisfy very strong reliability conditions. Further, for a given orderp, the asymptotically optimal values for the substep lengths are independent of the problem and formula and hence can be computed a priori. Theoretical comparisons between the parallel algorithm and optimal sequential algorithms at various orders are given. We also report on numerical tests of the reliability and efficiency of the new algorithm, and give some parallel timing statistics from a 4-processor machine.     

P-chirogenic phosphines. MOP/diPAMP hybrids, their oxide crystal structures, reduction studies and alternative syntheses

The novel P-chirogenic anisylphenylMOP derivatives (R,R) and (R,S)-2-(anisylphenylphosphino)-2′-methoxy-1,1′-binaphthyl (10a and b) have been synthesized and their corresponding oxides characterised by X-ray crystallography. The results of a parallel screening regimen with various reducing agents highlight the sensitivity of the tertiary phosphine oxides to epimerisation and, interestingly, reveal that the PO, O-CH₃ and P-C₆H₅ bonds can all be cleaved selectively depending on the reducing agents employed. An alternative synthesis was provided by direct coupling of the secondary phosphine with (R)-methoxytriflate 4, which led to the isolation of the optically pure P-chirogenic phosphines via their borane adducts. A brief study of the coordination chemistry of 10a with different rhodium precursors, relevant to the catalytic asymmetric addition of boronic acids to aldehydes is also reported.     

On the Boundedness of Asymptotic Stability Regions for the Stochastic Theta Method

The stochastic theta method gives a computational procedure for simulating ordinary stochastic differential equations. The method involves a free parameter, . Here, we characterise the precise value of beyond which the region of linear asymptotic stability of the method becomes unbounded. The cutoff point is seen to differ from that in the deterministic case. Computations that suggest further results are also given.     

Algorithms for the matrix <Emphasis Type="Italic">p</Emphasis>th root

New theoretical results are presented about the principal matrix pth root. In particular, we show that the pth root is related to the matrix sign function and to the Wiener–Hopf factorization, and that it can be expressed as an integral over the unit circle. These results are used in the design and analysis of several new algorithms for the numerical computation of the pth root. We also analyze the convergence and numerical stability properties of Newtons method for the inverse pth root. Preliminary computational experiments are presented to compare the methods. AMS subject classification 15A24, 65H10, 65F30Numerical Analysis Report 454, Manchester Centre for Computational Mathematics, July 2004.Dario A. Bini: This work was supported by MIUR, grant number 2002014121.Nicholas J. Higham: This work was supported by Engineering and Physical Sciences Research Council grant GR/R22612 and by a Royal Society – Wolfson Research Merit Award.