High-order compact exponential finite difference methods for convection–diffusion type problems

A class of high-order compact (HOC) exponential finite difference (FD) methods is proposed for solving one- and two-dimensional steady-state convection–diffusion problems. The newly proposed HOC exponential FD schemes have nonoscillation property and yield high accuracy approximation solution as well as are suitable for convection-dominated problems. The O(h⁴) compact exponential FD schemes developed for the one-dimensional (1D) problems produce diagonally dominant tri-diagonal system of equations which can be solved by applying the tridiagonal Thomas algorithm. For the two-dimensional (2D) problems, O(h⁴ + k⁴) compact exponential FD schemes are formulated on the nine-point 2D stencil and the line iterative approach with alternating direction implicit (ADI) procedure enables us to deal with diagonally dominant tridiagonal matrix equations which can be solved by application of the one-dimensional tridiagonal Thomas algorithm with a considerable saving in computing time. To validate the present HOC exponential FD methods, three linear and nonlinear problems, mostly with boundary or internal layers where sharp gradients may appear due to high Peclet or Reynolds numbers, are numerically solved. Comparisons are made between analytical solutions and numerical results for the currently proposed HOC exponential FD methods and some previously published HOC methods. The present HOC exponential FD methods produce excellent results for all test problems. It is shown that, besides including the excellent performances in computational accuracy, efficiency and stability, the present method has the advantage of better scale resolution. The method developed in this article is easy to implement and has been applied to obtain the numerical solutions of the lid driven cavity flow problem governed by the 2D incompressible Navier–Stokes equations using the stream function-vorticity formulation.     

Intermolecular Zero-Quantum Coherences of Multi-component Spin Systems in Solution NMR

Intermolecular zero-quantum coherences (iZQC) induced by the dipolar demagnetizing field can give bothP- andN-type cross peaks. This paper shows that the relative intensities of the two types of iZQC peaks follow a simple relation, tan²(θ/2), from both the quantum (spin density matrix) and classical (modified Bloch equation) calculations. The experimental data and numerical simulations agree well with the prediction. In addition, higher-order iZQCs are experimentally examined for the first time and are explained by the quantum picture in which dipolar couplings convert four-spin operators into observable magnetization.     

Finite-element lattice Hamiltonian matrix elements: Anharmonic oscillators

The finite-element approach to lattice field theory is both highly accurate (relative errors 1/N ², whereN is the number of lattice points) and exactly unitary (in the sense that canonical commutation relations are exactly preserved at the lattice sites). In this Letter, we construct matrix elements for the time evolution operator for the anharmonic oscillator, for which the continuum Hamiltonian isH=p ²/2+q ^2k /2k. Construction of such matrix elements does not require solving the implicit equations of motion. Low-order approximations turn out to be quite accurate. For example, the matrix element of the time evolution operator in the harmonic oscillator groundstate gives a result for thek=2 anharmonic oscillator groundstate energy accurate to better than 1% while a two-state approximation reduces the error to less than 0.1%. Accurate wavefunctions are also extracted. Analogous results may be obtained in the continuum, but there the computation is more difficult, and not generalizable to field theories in more dimensions.     

Lyapunov Bounds for Lattice Gauge Dynamics

We study the classical Hamiltonian dynamics of the Kogut–Susskind model for lattice gauge theories on a finite box in a d-dimensional integer lattice. The coupling constant for the plaquette interaction is denoted λ². When the gauge group is a real or a complex subgroup of a unitary matrix group U(N), N≥ 1, we show that the maximal Lyapunov exponent is bounded by , uniformly in the size of the lattice, the energy of the system as well as the order, N, of the gauge group. Received: 20 December 1997 / Accepted: 21 July 1998     

An MPI parallel level-set algorithm for propagating front curvature dependent detonation shock fronts in complex geometries

We present a parallel, two-dimensional, grid-based algorithm for solving a level-set function PDE that arises in Detonation Shock Dynamics (DSD). In the DSD limit, the detonation shock propagates at a speed that is a function of the curvature of the shock surface, subject to a set of boundary conditions applied along the boundaries of the detonating explosive. Our method solves for the full level-set function field, φ(x, y, t), that locates the detonation shock with a modified level-set function PDE that continuously renormalises the level-set function to a distance function based off of the locus of the shock surface, φ(x, y, t)=0. The boundary conditions are applied with ghost nodes that are sorted according to their connectivity to the interior explosive nodes. This allows the boundary conditions to be applied via a local, direct evaluation procedure. We give an extension of this boundary condition application method to three dimensions. Our parallel algorithm is based on a domain-decomposition model which uses the Message-Passing Interface (MPI) paradigm. The computational order of the full level-set algorithm, which is O(N ⁴), where N is the number of grid points along a coordinate line, makes an MPI-based algorithm an attractive alternative. This parallel model partitions the overall explosive domain into smaller sub-domains which in turn get mapped onto processors that are topologically arranged into a two-dimensional rectangular grid. A comparison of our numerical solution with an exact solution to the problem of a detonation rate stick shows that our numerical solution converges at better than first-order accuracy as measured by an L1-norm. This represents an improvement over the convergence properties of narrow-band level-set function solvers, whose convergence is limited to a floor set by the width of the narrow band. The efficiency of the narrow-band method is recovered by using our parallel model.     

The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk

The pivot algorithm is a dynamic Monte Carlo algorithm, first invented by Lal, which generates self-avoiding walks (SAWs) in a canonical (fixed-N) ensemble with free endpoints (hereN is the number of steps in the walk). We find that the pivot algorithm is extraordinarily efficient: one effectively independent sample can be produced in a computer time of orderN. This paper is a comprehensive study of the pivot algorithm, including: a heuristic and numerical analysis of the acceptance fraction and autocorrelation time; an exact analysis of the pivot algorithm for ordinary random walk; a discussion of data structures and computational complexity; a rigorous proof of ergodicity; and numerical results on self-avoiding walks in two and three dimensions. Our estimates for critical exponents are=0.7496±0.0007 ind=2 and= 0.592±0.003 ind=3 (95% confidence limits), based on SAWs of lengths 200N10000 and 200N 3000, respectively.     

Fast evaluation of Helmholtz potential on graphics processing units (GPUs)

This paper presents a parallel algorithm implemented on graphics processing units (GPUs) for rapidly evaluating spatial convolutions between the Helmholtz potential and a large-scale source distribution. The algorithm implements a non-uniform grid interpolation method (NGIM), which uses amplitude and phase compensation and spatial interpolation from a sparse grid to compute the field outside a source domain. NGIM reduces the computational time cost of the direct field evaluation at N observers due to N co-located sources from O(N²) to O(N) in the static and low-frequency regimes, to O(N log N) in the high-frequency regime, and between these costs in the mixed-frequency regime. Memory requirements scale as O(N) in all frequency regimes. Several important differences between CPU and GPU implementations of the NGIM are required to result in optimal performance on respective platforms. In particular, in the CPU implementations all operations, where possible, are pre-computed and stored in memory in a preprocessing stage. This reduces the computational time but significantly increases the memory consumption. In the GPU implementations, where handling memory often is a critical bottle neck, several special memory handling techniques are used to accelerate the computations. A significant latency of the GPU global memory access is hidden by implementing coalesced reading, which requires arranging many array elements in contiguous parts of memory. Contrary to the CPU version, most of the steps in the GPU implementations are executed on-fly and only necessary arrays are kept in memory. This results in significantly reduced memory consumption, increased problem size N that can be handled, and reduced computational time on GPUs. The obtained GPU–CPU speed-up ratios are from 150 to 400 depending on the required accuracy and problem size. The presented method and its CPU and GPU implementations can find important applications in various fields of physics and engineering.     

Simulated quantum computation of global minima

Finding the optimal solution to a complex optimisation problem is of great importance in practically all fields of science, technology, technical design and econometrics. We demonstrate that a modified Grover's quantum algorithm can be applied to real problems of finding a global minimum using modest numbers of quantum bits. Calculations of the global minimum of simple test functions and Lennard-Jones clusters have been carried out on a quantum computer simulator using a modified Grover's algorithm. The number of function evaluations N reduced from O(N) in classical simulation to O(N ^1/2) in quantum simulation. We also show how the Grover's quantum algorithm can be combined with the classical Pivot method for global optimisation to treat larger systems.     

A Fast Algorithm for Wave Propagation from a Plane or a Cylindrical Surface

The newly developed Taylor-Interpolation-FFT (TI-FFT) algorithm dramatically increases the computational speeds for millimeter wave propagation from a planar (cylindrical) surface onto a “quasi-planar” (“quasi-cylindrical”) surface. Two different scenarios are considered in this article: the planar TI-FFT is for the computation of the wave propagation from a plane onto a “quasi-planar” surface and the cylindrical TI-FFT is for the computation of wave propagation from a cylindrical surface onto a “quasi-cylindrical” surface. Due to the use of the FFT, the TI-FFT algorithm has a computational complexity of O(N ² log₂  N ²) for an N × N computational grid, instead of N ⁴ for the direct integration method. The TI-FFT algorithm has a low sampling rate according to the Nyquist sampling theorem. The algorithm has accuracy down to −80 dB and it works particularly well for narrow-band fields and “quasi-planar” (“quasi-cylindrical”) surfaces.     

A CUDA-based reverse gridding algorithm for MR reconstruction

MR raw data collected using non-Cartesian method can be transformed on Cartesian grids by traditional gridding algorithm (GA) and reconstructed by Fourier transform. However, its runtime complexity is O(K× N²), where resolution of raw data is N× N and size of convolution window (CW) is K. And it involves a large number of matrix calculation including modulus, addition, multiplication and convolution. Therefore, a Compute Unified Device Architecture (CUDA)-based algorithm is proposed to improve the reconstruction efficiency of PROPELLER (a globally recognized non-Cartesian sampling method). Experiment shows a write–write conflict among multiple CUDA threads. This induces an inconsistent result when synchronously convoluting multiple k-space data onto the same grid. To overcome this problem, a reverse gridding algorithm (RGA) was developed. Different from the method of generating a grid window for each trajectory as in traditional GA, RGA calculates a trajectory window for each grid. This is what “reverse” means. For each k-space point in the CW, contribution is cumulated to this grid. Although this algorithm can be easily extended to reconstruct other non-Cartesian sampled raw data, we only implement it based on PROPELLER. Experiment illustrates that this CUDA-based RGA has successfully solved the write–write conflict and its reconstruction speed is 7.5 times higher than that of traditional GA.     

Improved mean field studies of SU(N) chiral models and comparison with numerical simulations

SU(N) × SU(N) matrix models are investigated using a systematic expansion around the classical mean field result. One-loop corrections for N = 2?5, and ∞ are computed for the two-, three-, and four-dimensional models. The results are in good agreement with numerical simulations of these models.     

On the potentialx 2N and the correspondence principle

Eigenenergies and frequencies are obtained for a particle oscillating in the potential (1/2)k ^N × ^2N , wherek is a constant,x is displacement, andN is a real number. These potentials include the harmonic oscillator (N = 1) and the square well (N = ). Then ^th eigenenergy has the formA _N n ^(N) , where(N) = 2N/(N + 1), andA _N is independent ofn. Application is made to the correspondence principle for the potentialsN > 1 and it is concluded the classical continuum is not obtained in Bohr's limitn . Complete correspondence is attained in Planck's limith 0, so that for these configurations the limitsh 0 andn are not equivalent. A classical analysis of these potentials is included which reveals the relation log _E (/ _N ) = (N – 1)/2N between frequencyv and energyE, where the constant _N is independent ofE.     

Crossover from Quantum to Boltzmann Statistics for Free Particles in a Single Harmonic Trap

With invoking analytical formulae in number theory and numerical calculations, we calculate the number of microstates in microcanonical ensemble for free particles in a single harmonic trap which in whole space defines a thermodynamic system but not a spatially homogeneous one. Once the number of excitation quanta m is larger than the square of the particle number N ² as m⪰O(N ²) when N≫1, the number of microcanonical microstates for an ideal, harmonically trapped Bose or Fermi gas gradually converge to the Boltzmann microcanonical microstates for the classical particles with a proper consideration of the indistinguishability.     

Ground-state energy of a classical artificial molecule

We study the ground-state energy of a classical artificial molecule formed by two-dimensional clusters (artificial atoms) of N/2 charged particles separated by a distance d. For the small molecules of N = 2 and 4, we obtain analytical expressions for this energy. For the larger ones, we calculate the ground-state energy using molecular dynamics simulation for N up to 128. From our numerical results, we are able to find out a function to approximate the ground-state energy of the molecules covering the range from atoms to molecules for any inter-atom distance d and for particle number from N = 8 to 128 within a difference less than one percent from the MD data.     

The travelling salesman problem on randomly diluted lattices: Results for small-size systems

If one places N cities randomly on a lattice of size L, we find that and vary with the city concentration p=N/L ², where is the average optimal travel distance per city in the Euclidean metric and is the same in the Manhattan metric. We have studied such optimum tours for visiting all the cities using a branch and bound algorithm, giving the exact optimized tours for small system sizes () and near-optimal tours for bigger system sizes (). Extrapolating the results for , we find that for p=1, and and with as . Although the problem is trivial for p=1, for it certainly reduces to the standard travelling salesman problem on continuum which is NP-hard. We did not observe any irregular behaviour at any intermediate point. The crossover from the triviality to the NP-hard problem presumably occurs at p=1. Received 15 April 2000     

Join- and-cut algorithm for self-avoiding walks with variable length and free endpoints

We introduce a new Monte Carlo algorithm for generating self-avoiding walks of variable length and free endpoints. The algorithm works in the unorthodox ensemble consisting of all pairs of SAWs such that the total number of stepsN _tot in the two walks is fixed. The elementary moves of the algorithm are fixed-N (e.g., pivot) moves on the individual walks, and a novel join- and-cut move that concatenates the two walks and then cuts them at a random location. We analyze the dynamic critical behavior of the new algorithm, using a combination of rigorous, heuristic, and numerical methods. In two dimensions the autocorrelation time in CPU units grows as N^1.5, and the behavior improves in higher dimensions. This algorithm allows high-precision estimation of the critical exponent.     

Optimal mass transport for higher dimensional adaptive grid generation

In this work, we describe an approach for higher dimensional adaptive grid generation based on solving the L² Monge–Kantorovich problem (MKP) which is a special case of the classical optimal mass transportation problem. Two methods are developed for computing the coordinate transformation used to define the grid adaptation. For the first method, the transformation is determined by solving a parabolic Monge–Ampère equation for a steady state solution. For the second method, the grid movement is determined from the velocity field obtained by solving a fluid dynamics formulation of the L² MKP. Several numerical experiments are presented to demonstrate the performance of the MKP methods and to compare them with some related adaptive grid methods. The experimental results demonstrate that the MKP methods show promise as effective and reliable methods for higher dimensional adaptive grid generation.     

On the indistinguishability of classical particles

If no property of a system of many particles discriminates among the particles, they are said to be indistinguishable. This indistinguishability is equivalent to the requirement that the many-particle distribution function and all of the dynamic functions for the system be symmetric. The indistinguishability defined in terms of the discrete symmetry of many-particle functions cannot change in the continuous classical statistical limit in which the number density n and the reciprocal temperature become small. Thus, microscopic particles like electrons must remain indistinguishable in the classical statistical limit although their behavior can be calculated as if they move following the classical laws of motion. In the classical mechanical limit in which quantum cells of volume (2)³ are reduced to points in the phase space, the partition functionTr{exp(–) for N identical bosons (fermions) approaches (2)^–3N(N!) ... d³r₁ d³p₁ ... d³r_N d³p_N exp(–H). The two factors, (2)^–3N and (N!)^–1, which are often added in anad hoc manner in many books on statistical mechanics, are thus derived from the first principles. The criterion of the classical statistical approximation is that the thermal de Broglie wavelength be much shorter than the interparticle distance irrespective of any translation-invariant interparticle interaction. A new derivation of the Maxwell velocity distribution from Boltzmann's principle is given with the assumption of indistinguishable classical particles.     

Point-contact tunneling spectroscopy between a Nb tip and an ideal topological insulator Sn-doped Bi1.1Sb0.9Te2S

We find that the quantum-classical correspondence in integrable systems is characterized by two time scales. One is the Ehrenfest time below which the system is classical; the other is the quantum revival time beyond which the system is fully quantum. In between, the quantum system can be well approximated by classical ensemble distribution in phase space. These results can be summarized in a diagram which we call Ehrenfest diagram. We derive an analytical expression for Ehrenfest time, which is proportional to h~(-1/2). According to our formula, the Ehrenfest time for the solar-earth system is about 10~(26) times of the age of the solar system. We also find an analytical expression for the quantum revival time, which is proportional to h~(-1). Both time scales involve ω(I), the classical frequency as a function of classical action. Our results are numerically illustrated with two simple integrable models. In addition, we show that similar results exist for Bose gases, where 1/N serves as an effective Planck constant.     

Non-perturbative membrane spin-orbit couplings in

Membrane source-probe dynamics is investigated in the framework of the finite N-sector DLCQ M-theory compactified on a transverse two-torus for an arbitrary size of the longitudinal dimension. The non-perturbative two-fermion terms in the effective action of the matrix theory, the (2 + 1)-dimensional supetsymmetric Yang-Mills theory, that are related to the four derivative F⁴ terms by the supersymmetry transformation are obtained, including the one-loop term and full instanton corrections. On the supergravity side, we compute the classical probe action up to two-fermion terms based on the classical supermembrane formulation in an arbitrary curved background geometry produced by source membranes satisfying the BPS condition; two-fermion terms correspond to the spin-orbit couplings for membranes. We find precise agreement between the two approaches when the background space-time is chosen to be that of the DLCQ M-theory, which is asymptotically locally anti-de Sitter.