clarke@csri.toronto.edu (Jim Clarke) (04/06/89)
NUMERICAL ANALYSIS SEMINAR - Wednesday, April 12, 10 a.m. in Room GB 248
(GB = Galbraith Building, 35 St. George Street)
Faisal Saied
Yale University
"Spectral and Finite Difference Techniques for
the Numerical Solution of Schrodinger's Equation
and Their Parallel Implementation"
We investigate numerical techniques for the solution of the time dependent
Schrodinger equation in one and two space dimensions. We consider well-
known methods, such as the split-step Fourier method and Crank-Nicolson,
and some methods that have been proposed recently, such as an explicit 5-
point scheme, and we propose some new methods. We introduce a framework
for constructing finite difference schemes based on Pade approximations for
both the time and space discretization and apply this framework to
construct high order finite difference schemes for Schrodinger's equation
in conjunction with the split-step approach and also as three level
schemes. The split-step Douglas (SSD) method is an example of the class of
methods thus obtained. We define the notion os i-stability for the Pade
table for the expontial function (which is appropriate for the Schrodinger
operator) and prove some results on the locations of the i-stable entries.
For two space dimensions, some of the new techniques proposed include a
split-step Crank-Nicolson scheme, where the implicit equations at each time
step can be solved by a fast Poisson solver. The two-dimensional methods
have ADI (alternating direction implicit) analogues which reduce the
complexity of the computations. The accuracy and stability of these
methods is studied, and their efficiencies are compared. The results of
some numerical comparisons of the methods are presented.
We have implemented some of the techniques for solving Schrodinger's
equation on a hypercube. Since several methods considered involve the
solution of a single or multiple systems of tridiagonal equations, we have
implemented a variety of approaches for solving a single tridiagonal system
that is spread across the hypercube. If the order of the system is large
compared to the number of processors, one must perform substructuring and
solve a distributed reduced system. For multiple tridiagonal systems we
found that performing a transpose on the entire data is preferable to
performing substructuring for each system and then applying balanced cyclic
reduction or a transpose to the reduced systems. However, predictions based
on a model of computation show that balanced cyclic reduction is
asymptotically the best method. These results are then used to implement an
alternating direction scheme for the problem with two space dimensions,
where a combination of an incomplete transpose and ``two-way'' Gaussian
elimination is found to be the most effective method on the Intel iPSC.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke