Session D27: Focus Session: Novel Computational Algorithms I

Linear scaling techniques for the solution of the time-dependent Schr\"{o}dinger equation

An efficient, accurate solution of the time-dependent linear/nonlinear Schr{\"{o}}dinger equation (TDSE) is required for a wide variety of problems in physics and chemistry. These include the dynamics of atoms and molecules in intense/ultrashort external fields, time-dependent approaches to atomic collisions, the dynamics of ultracold media such as Bose-Einstein Condensates and plasmas, and the behavior of materials under extreme conditions. Various techniques have been developed for this purpose. We shall describe a new approach in which the Finite Element Discrete Variable Representation (FEDVR) is combined with the Real-Space Product (RSP) algorithm to generate a highly effective procedure (RSP-FEDVR) for solving the TDSE on supercomputers. Emphasis will be placed on the complete formalism and the implementation of parallelization within the Message-Passing-Interface (MPI) scheme on large, distributed-memory supercomputer clusters. Its superior performance will be illustrated by a number of three-/four-dimensional problems, in comparison to the conventional finite-difference (FD) methods.   

Solution of the Time-Dependent Schroedinger Equation using a Real Space Product Finite Element Discrete Variable Representation (RSPFEDVR)

A novel approach to the solution of the time-dependent Schroedinger equation using a RSPFEDVR method is described. The method is applied in both a second and fourth order version. In this talk we describe the essential features of the approach and compare the method as to its accuracy and efficiency in a number of model problems. The method may be transparently and efficiently parallelized using MPI as a consequence of the structure of the RSPFEDVR propagator which leads to a minimal number of communications at each step in the propagtion.   

A Nonlinear Finite Difference Scheme for the Time-Dependent Schrodinger Equation

In general, the time-dependent Schrodinger equation (TDSE) cannot be explicitly solved for an arbitrary boundary and/or initial value problem. One resolution of this difficulty is to construct discrete models of this equation and use them to calculate numerical solutions. We consider the case of the TDSE, in one space dimension, and demonstrate that a nonlinear finite difference scheme can be formulated. We study its various limiting forms and compare their mathematical properties with those of the corresponding ordinary and partial differential equations. A formal solution is presented for the fully discrete TDSE. We discuss the basis of this nonlinear discretization within the framework of the nonstandard finite difference methodology created by Mickens [1] and the work of Bhattacharya [2]. \bigskip \newline [1] R. E. Mickens, Nonstandard Finite Difference Models of Differential Equations (World Scientific, Singapore, 1994). \newline [2] M. C. Bhattacharya, Applied Mathematical Modeling 10 (1986), 68-70.   

Efficient Boundary Integral Method for Quantum Billiards

Calculating highly excited eigenvalues of the Laplace equation and their corresponding eigenfunctions are of great current interest in many areas. We present an efficient algorithm based on a novel Fredholm formulation of the Laplace eigenvalue problem, in the spirit of the scattering quantization method proposed by the authors in the context of the basis function expansion technique.\footnote{H.~E. Tureci, H.~G.~L. Schwefel, Ph. Jacquod, and A.~Douglas Stone. Modes of wave-chaotic dielectric resonators. {\em Progress In Optics}, 47, 2005.} We also point out the connection to the scaling eigenfunctions\footnote{A.~H.~Barnett. Quasi-orthogonality on the boundary for Euclidean Laplace eigenfunctions. {\em submitted, Comm.\ Pure Appl.\ Math.}, 2004} and show how this method can be generalized to dielectric cavities.   

Quantum Computation for Quantum Chemistry

The calculation time for the energy of atoms and molecules scales exponentially with system size on a classical computer, but polynomially using quantum algorithms. We demonstrate that such algorithms can be applied to problems of chemical interest using modest numbers of quantum bits. Calculations of the H$_{2}$O and LiH molecular ground-state energies have been carried out on a quantum computer simulator using a recursive phase estimation algorithm. The recursive algorithm reduces the number of quantum bits required for the read-out register from approximately twenty to four. Mappings of the molecular wave function to the quantum bits are described. An adiabatic method for the preparation of a good approximate ground-state wave function is described and demonstrated for stretched H$_{2}$. The number of quantum bits required scales linearly with the number of basis functions used and the number of gates required grows polynomially with the number of quantum bits.   

The ``Inverse Band Structure ( IBS) Approach'' for designer nanostructures and designer impurities in semiconductors.

While in standard computational physics and chemistry one first defines the molecular or crystalline structure and then computes the ensuing electronic structure and properties, we adopt a reverse approach in which we search for the atomic configuration having a prescribed target property. Using either Simulated Annealing or Genetic Algorithms as search strategies we determine the configuration of groups of Nitrogen atoms having either the deepest or the shallowest level in the GaP gap, or the highest/lowest oscillator-strength for optical absorption. Similar approaches are used to determine the extremal band gaps of alloys and the configuration of Mn atoms in GaAs having the highest Curie temperature. This approach allows one to scan a large number of configurations of e.g, alloys in search of the optimal one with a desired property.If the property is readily calculable, the IBS search is done on-the-fly. If its difficult to calculate ( e.g, Tc of ferromagnets), we first do a cluster expansion,then IBS search. Work supported by DOE-SC-BES-DMS under NREL contract AC3699GO10377.   

A Real-Space Genetic Algorithm for Crystal Structure Determination

There has been much interest in using genetic algorithms for determining the ground-state structure of clusters [1] and nanowires [2], and more recently silicon surfaces [3]. We present a real-space encoded genetic algorithm which is suitable not only for surface structure calculations, but also for bulk crystal structure determination. This algorithm makes use of a novel crossover technique in the generation of offspring. The method is also suitable as a polymorph search, and is flexible enough that population members can have different supercells. We will present results from a variety of empirical and {\it ab initio} systems, where all calculations have been performed using the CASTEP [4] code. \\ \ \\ {[}1{]} {D. M. Deaven and K. M. Ho,{\it Phys. Rev. Lett.},{\bf 75} (1995) {288-291}}\\ {[}2{]} {B. Wang {\it et al}, {\it Phys. Rev. Lett.}, {\bf 86} (2001) 2046-2049}\\ {[}3{]} {F. C. Chuang {\it et al}, {\it Surf. Sci.}, {\bf 573} (2004) L375-L381}\\ {[}4{]} {M. D. Segall {\it et al}, {\it J. Phys.: Cond. Matt.}, {\bf 14} (2002) 2717-2743} \\   

Traveling the configurational space of binary alloys

Binary $A_{1-x}B_{x}$ alloys can exist in any of the $2^{N}$ possible configurations on a periodic lattice of $N$ sites. In many areas of the alloy theory one needs to search all lattice configuration. Such a problem arises, for example, when the $T=0$ ground state configurations are sought, or in problems of materials design, where it is desirable to scan all the configurations to find the configuration $\sigma^{*}$ that has specific property. This task is complicated by (i) the huge computational demand for large $N$ and (ii) by the possibility that the $P(\sigma)$ is sensitive to the cell shape. In this talk we present a new computational approach for defining and searching the configurational space, that is based on (i) the exhaustive {\em enumeration} of the ``Inequivalent Cell Shapes'', and, for a given cell shape on (ii) the {\em sampling} of the related ``Same-Shape-Structures'' via a Genetic Algorithm. We apply this procedure to few ground state problems in semiconductor and metal alloys: For (AC)$_{x}$(BC)$_{1-x}$ tetrahedral semiconductor alloys we predict the lattice configurations of minimum bond-bending and bond-stretching strain both in free-floating bulk and under the epitaxial strain. We show that the chalcopyrite structure remains a ground state even under epitaxy. For Au-Pd alloy modelled with the mixed basis cluster expansion Hamiltonian, we determine the ground state structures and compare the convex hull to the one found previously by the direct enumeration approach.   

Simulating Charged Systems with the Geometric Cluster Algorithm

The recently introduced generalized geometric cluster algorithm (GCA) for colloidal suspensions [J. Liu and E. Luijten, Phys.\ Rev.\ Lett.\textbf{92}, 035504 (2004)] is extended to systems with electrostatic interactions. The Ewald summation is used to determine the pair potentials. However, the resulting pair potentials cannot be used directly in the GCA because the long range nature of the electrostatic potential causes all particles to be included in a cluster. In our new method, the cluster size is therefore controlled by using only the real-space part of the potential during cluster construction, then accepting or rejecting the cluster move based on the part of the internal energy that is computed in Fourier space. Although the resulting algorithm is, in contrast with the original approach, no longer rejection-free, it is possible to perform collective nonlocal moves while maintaining a significant acceptance ratio. The method is particularly beneficial for systems containing components with large size asymmetries, such as suspensions of charged colloids in the presence of salt.   

Multi-physics/scale simulations using particles

Particle simulations of continuum and discrete phenomena can be formulated by following the motion of interacting particles that carry the physical properties of the systems that is being approximated (continuum) or modeled (discrete) by the particles. We identify the common computational characteristics of particle methods and emphasize their key properties that enable the formulation of a novel, systematic framework for multiscale simulations, that can be applicable to the simulation of diverse physical problems. We present novel multiresolution particle methods for continuum (fluid/solid) simulations, using adaptive mesh refinement and wavelets, by relaxing the grid-free character of particle methods and discuss the coupling of scales in continuum-atomistic flow simulations.   

Algorithmic Refinements for Multicanonical System Measurements

We have adapted, to our knowledge for the first time, multicanonical sampling and its Wang-Landau extension to the analysis of the statistics of communication systems, and by extension, arbitrary stochastic physical systems.[D. Yevick, ``A First Course in Computational Physics and Object Oriented Programming with C++``, Cambridge University Press, Ch. 22 and references] Subsequently, we applied the technique experimentally with and without a novel biasing procedure for the intermediate pdf distributions that significantly enhances the statistics in selected regions of system variables. [T. Lu, D. Yevick et. al.\textbf{,} IEEE Photon. Technol. Lett, \textbf{17}, 1420 (2005) and to be published]. Here we additionally discuss procedures that (1) bias the statistical samples by raising the estimated pdf to a power (2) combine intermediate results in a manner identical to that employed in importance sampling (3) incorporate non-uniform Markov chain displacements and (4) interpolate the histogram and pdf values during iterations. These significantly impact experiments with a restricted number of samples.[D. Yevick et. al., submitted to J. Opt. Soc. Am. A]