Alternatives for parallel Krylov subspace basis computation

Numerical methods related to Krylov subspaces are widely used in large sparse numerical linear algebra. Vectors in these subspaces are manipulated via their representation onto orthonormal bases. Nowadays, on serial computers, the method of Arnoldi is considered as a reliable technique for constructing such bases. However, although easily parallelizable, this technique is not as scalable as expected for communications. In this work we examine alternative methods aimed at overcoming this drawback. Since they retrieve upon completion the same information as Arnoldi's algorithm does, they enable us to design a wide family of stable and scalable Krylov approximation methods for various parallel environments. We present timing results obtained from their implementation on two distributed-memory multiprocessor supercomputers: the Intel Paragon and the IBM Scalable POWERparallel SP2. (C) 1997 by John Wiley & Sons, Ltd.

Calculation of product state distributions from resonance decay via Lanczos subspace filter diagonalization: Application to HO2

Resonance phenomena associated with the unimolecular dissociation of HO2 have been investigated quantum-mechanically by the Lanczos homogeneous filter diagonalization (LHFD) method. The calculated resonance energies, rates (widths), and product state distributions are compared to results from an autocorrelation function-based filter diagonalization (ACFFD) method. For calculating resonance wave functions via ACFFD, an analytical expression for the expansion coefficients of the modified Chebyshev polynomials is introduced. Both dissociation rates and product state distributions of O-2 show strong fluctuations, indicating the dissociation of HO2 is essentially irregular. (C) 2001 American Institute of Physics.

Lanczos subspace filter diagonalization: Homogeneous recursive filtering and a low-storage method for the calculation of matrix elements

We develop a new iterative filter diagonalization (FD) scheme based on Lanczos subspaces and demonstrate its application to the calculation of bound-state and resonance eigenvalues. The new scheme combines the Lanczos three-term vector recursion for the generation of a tridiagonal representation of the Hamiltonian with a three-term scalar recursion to generate filtered states within the Lanczos representation. Eigenstates in the energy windows of interest can then be obtained by solving a small generalized eigenvalue problem in the subspace spanned by the filtered states. The scalar filtering recursion is based on the homogeneous eigenvalue equation of the tridiagonal representation of the Hamiltonian, and is simpler and more efficient than our previous quasi-minimum-residual filter diagonalization (QMRFD) scheme (H. G. Yu and S. C. Smith, Chem. Phys. Lett., 1998, 283, 69), which was based on solving for the action of the Green operator via an inhomogeneous equation. A low-storage method for the construction of Hamiltonian and overlap matrix elements in the filtered-basis representation is devised, in which contributions to the matrix elements are computed simultaneously as the recursion proceeds, allowing coefficients of the filtered states to be discarded once their contribution has been evaluated. Application to the HO2 system shows that the new scheme is highly efficient and can generate eigenvalues with the same numerical accuracy as the basic Lanczos algorithm.

Subspace wavepacket evolution with Newton polynomials

Time-dependent wavepacket evolution techniques demand the action of the propagator, exp(-iHt/(h)over-bar), on a suitable initial wavepacket. When a complex absorbing potential is added to the Hamiltonian for combating unwanted reflection effects, polynomial expansions of the propagator are selected on their ability to cope with non-Hermiticity. An efficient subspace implementation of the Newton polynomial expansion scheme that requires fewer dense matrix-vector multiplications than its grid-based counterpart has been devised. Performance improvements are illustrated with some benchmark one and two-dimensional examples. (C) 2001 Elsevier Science B.V. All rights reserved.

A real symmetric Lanczos subspace implementation of quantum scattering using boundary inhomogeneities

We present an efficient and robust method for calculating state-to-state reaction probabilities utilising the Lanczos algorithm for a real symmetric Hamiltonian. The method recasts the time-independent Artificial Boundary Inhomogeneity technique recently introduced by Jang and Light (J. Chem. Phys. 102 (1995) 3262) into a tridiagonal (Lanczos) representation. The calculation proceeds at the cost of a single Lanczos propagation for each boundary inhomogeneity function and yields all state-to-state probabilities (elastic, inelastic and reactive) over an arbitrary energy range. The method is applied to the collinear H + H-2 reaction and the results demonstrate it is accurate and efficient in comparison with previous calculations. (C) 2002 Elsevier Science B.V. All rights reserved.

Efficient time-independent wave packet scattering calculations within a Lanczos subspace: H+O-2 (J=0) state-to-state reaction probabilities

An efficient Lanczos subspace method has been devised for calculating state-to-state reaction probabilities. The method recasts the time-independent wave packet Lippmann-Schwinger equation [Kouri , Chem. Phys. Lett. 203, 166 (1993)] inside a tridiagonal (Lanczos) representation in which action of the causal Green's operator is affected easily with a QR algorithm. The method is designed to yield all state-to-state reaction probabilities from a given reactant-channel wave packet using a single Lanczos subspace; the spectral properties of the tridiagonal Hamiltonian allow calculations to be undertaken at arbitrary energies within the spectral range of the initial wave packet. The method is applied to a H+O-2 system (J=0), and the results indicate the approach is accurate and stable. (C) 2002 American Institute of Physics.

Lanczos subspace time-independent wave packet calculations of S(D-1)+H-2 reactive scattering

In this paper. we present the results of quantum dynamical simulations of the S (D-1) + H-2 insertion reaction on a newly developed potential energy surface (J. Chem. Phys. 2001, 114, 320). State-to-state reaction probabilities. product state distributions, and initial-state resolved cumulative reaction probabilities from a given incoming reactant channel are obtained from a time-independent wave packet analysis, performed within a single Lanczos subspace. Integral reaction cross sections are then estimated by J-shifting method and compared with the results from molecular beam experiment and QCT calculations.

Using continuous measurement to protect a universal set of quantum gates within a perturbed decoherence-free subspace

We consider a universal set of quantum gates encoded within a perturbed decoherence-free subspace of four physical qubits. Using second-order perturbation theory and a measuring device modelled by an infinite set of harmonic oscillators, simply coupled to the system, we show that continuous observation of the coupling agent induces inhibition of the decoherence due to spurious perturbations. We thus advance the idea of protecting or even creating a decoherence-free subspace for processing quantum information.

Fault-tolerant quantum computation with cluster states

The one-way quantum computing model introduced by Raussendorf and Briegel [Phys. Rev. Lett. 86, 5188 (2001)] shows that it is possible to quantum compute using only a fixed entangled resource known as a cluster state, and adaptive single-qubit measurements. This model is the basis for several practical proposals for quantum computation, including a promising proposal for optical quantum computation based on cluster states [M. A. Nielsen, Phys. Rev. Lett. (to be published), quant-ph/0402005]. A significant open question is whether such proposals are scalable in the presence of physically realistic noise. In this paper we prove two threshold theorems which show that scalable fault-tolerant quantum computation may be achieved in implementations based on cluster states, provided the noise in the implementations is below some constant threshold value. Our first threshold theorem applies to a class of implementations in which entangling gates are applied deterministically, but with a small amount of noise. We expect this threshold to be applicable in a wide variety of physical systems. Our second threshold theorem is specifically adapted to proposals such as the optical cluster-state proposal, in which nondeterministic entangling gates are used. A critical technical component of our proofs is two powerful theorems which relate the properties of noisy unitary operations restricted to act on a subspace of state space to extensions of those operations acting on the entire state space. We expect these theorems to have a variety of applications in other areas of quantum-information science.

Multicomponent reversible reactions inside a porous catalyst pellet

This work deals with a solution method to handle multicomponents reversible reactions occurring inside a porous catalyst pellet. The complexity of this problem arises from the fact that the effective diffusivities and Biot number, which characterizes the external mass transfer, are different for each chemical species. In mathematical terms, this means that each chemical species has its own subspace and, therefore, when the technique of finite integral transform is applied to solve this multicomponent problem, each chemical species is associated with its own integral transform kernel. The analytical solutions obtained for this problem are compact and simple for any further manipulation. Application of this result to the catalytic reforming of C7 hydrocarbon system is shown in this paper.

Expokit: A software package for computing matrix exponentials

Expokit provides a set of routines aimed at computing matrix exponentials. More precisely, it computes either a small matrix exponential in full, the action of a large sparse matrix exponential on an operand vector, or the solution of a system of linear ODEs with constant inhomogeneity. The backbone of the sparse routines consists of matrix-free Krylov subspace projection methods (Arnoldi and Lanczos processes), and that is why the toolkit is capable of coping with sparse matrices of large dimension. The software handles real and complex matrices and provides specific routines for symmetric and Hermitian matrices. The computation of matrix exponentials is a numerical issue of critical importance in the area of Markov chains and furthermore, the computed solution is subject to probabilistic constraints. In addition to addressing general matrix exponentials, a distinct attention is assigned to the computation of transient states of Markov chains.

A numerical study of large sparse matrix exponentials arising in Markov chains

Krylov subspace techniques have been shown to yield robust methods for the numerical computation of large sparse matrix exponentials and especially the transient solutions of Markov Chains. The attractiveness of these methods results from the fact that they allow us to compute the action of a matrix exponential operator on an operand vector without having to compute, explicitly, the matrix exponential in isolation. In this paper we compare a Krylov-based method with some of the current approaches used for computing transient solutions of Markov chains. After a brief synthesis of the features of the methods used, wide-ranging numerical comparisons are performed on a power challenge array supercomputer on three different models. (C) 1999 Elsevier Science B.V. All rights reserved.AMS Classification: 65F99; 65L05; 65U05.

Stability of linear difference and differential inclusions

Any given n X n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N x N matrix B of spectral radius p(B) arbitrarily close to p(A). A difference inclusion x(k+1) is an element of Ax(k), where A is a compact set of matrices, is asymptotically stable if and only if A can be extended to a set B of nonnegative matrices B with \ \B \ \ (1) < 1 or \ \B \ \ (infinity) < 1. Similar results are derived for differential inclusions.

A systematic approach to error isolation in computerized wastewater simulation models

Activated sludge models are used extensively in the study of wastewater treatment processes. While various commercial implementations of these models are available, there are many people who need to code models themselves using the simulation packages available to them, Quality assurance of such models is difficult. While benchmarking problems have been developed and are available, the comparison of simulation data with that of commercial models leads only to the detection, not the isolation of errors. To identify the errors in the code is time-consuming. In this paper, we address the problem by developing a systematic and largely automated approach to the isolation of coding errors. There are three steps: firstly, possible errors are classified according to their place in the model structure and a feature matrix is established for each class of errors. Secondly, an observer is designed to generate residuals, such that each class of errors imposes a subspace, spanned by its feature matrix, on the residuals. Finally. localising the residuals in a subspace isolates coding errors. The algorithm proved capable of rapidly and reliably isolating a variety of single and simultaneous errors in a case study using the ASM 1 activated sludge model. In this paper a newly coded model was verified against a known implementation. The method is also applicable to simultaneous verification of any two independent implementations, hence is useful in commercial model development.

A comparison of low-storage strategies for spectral analysis in dissipative systems: filter diagonalisation in the Lanczos representation and harmonic inversion of the Chebychev-order-domain autocorrelation function

We compare the performance of two different low-storage filter diagonalisation (LSFD) strategies in the calculation of complex resonance energies of the HO2, radical. The first is carried out within a complex-symmetric Lanczos subspace representation [H. Zhang, S.C. Smith, Phys. Chem. Chem. Phys. 3 (2001) 2281]. The second involves harmonic inversion of a real autocorrelation function obtained via a damped Chebychev recursion [V.A. Mandelshtam, H.S. Taylor, J. Chem. Phys. 107 (1997) 6756]. We find that while the Chebychev approach has the advantage of utilizing real algebra in the time-consuming process of generating the vector recursion, the Lanczos, method (using complex vectors) requires fewer iterations, especially for low-energy part of the spectrum. The overall efficiency in calculating resonances for these two methods is comparable for this challenging system. (C) 2001 Elsevier Science B.V. All rights reserved.