Talk Abstracts

Session A: Talk #1	Working on SUNTANS: The design of a high performance, high resolution coastal ocean model
Presenter:	Margot Gerritsen Dept. of Petroleum Engineering, Stanford University
E-mail:	margot.gerritsen@stanford.edu
Abstract:	Colleagues and I at Stanford have recently started the development of SUNTANS (Stanford Unstructured Nonhydrostatic Terrain-following Adaptive Navier-Stokes Simulator), sponsored by NSF and ONR. Our goal is to design a high resolution parallel simulation code capable of generating accurate predictions of motions and transport in coastal oceans under conditions when a nonhydrostatic and terrain-following representation is essential. We plan to carry out two specific applications as part of the development: Internal waves in Monterey Bay and nonlinear internal tides in Mamala Bay, Hawaii. I will motivate the need for SUNTANS and present the major challenges in developing this code.

Session A: Talk #2	Recent Improvements in Parallel Algebraic Multigrid for Solving Maxwell's Equations
Presenter:	Jonathan Hu Computational Mathematics and Algorithms, Sandia National Laboratories
E-mail:	jhu@ca.sandia.gov
Abstract:	We describe our experiences with using parallel algebraic multigrid (AMG) for the solution of Maxwell's equations discretized via edge elements. A key difficulty is properly mapping the (curl,curl) operator's null space on to coarser grids via a prolongation operator that is constructed using only algebraic information (i.e. matrix coefficients and a minimal amount of element information). The AMG coarse grid correction scheme that we start with is based on the work of Stefan Reitzinger and Joachim Schöberl, and the smoother is a form of distributed relaxation. We describe modifications to the coarse grid correction and the smoother that result in improved convergence behavior. The resulting parallel multilevel preconditioner is implemented within ML, a Sandia multilevel package that already contains similar techniques like smoothed aggregation. The resulting capability has been integrated within the Sandia supported Nevada code framework and applied to a 3D Arbitrary Lagrangian-Eulerian magnetohydrodynamics capability (ALEGRA/MHD). Repeated solution of the eddy current approximation to Maxwell's equations in a highly heterogeneous material properties environment is required in this application. Numerical experiments are presented for various 3D model problems and an application of current interest: 3D simulations of Z-pinch implosions. The experiments illustrate the efficiency of the approach on various parallel machines in terms of both convergence and parallel speed-up.
Coauthors:	Pavel B. Bochev, Christopher J. Garasi, Ray S. Tuminaro, Allen C. Robinson, Sandia National Laboratories


Session B: Talk #1	Accurate and Efficient Matrix Computations with Totally Positive Generalized Vandermonde Matrices Using Schur Functions
Presenter:	Plamen Koev Dept. of Mathematics, UC-Berkeley
E-mail:	oplamen@math.berkeley.edu
Abstract:	Totally positive Vandermonde and Cauchy linear systems can be solved very accurately, regardless of condition number, using Björck-Pereyra-type methods. We explain this phenomenon by the following facts. First the Björck-Pereyra methods, written in matrix form, are nothing else but an accurate and efficient bidiagonal decomposition of the inverse of the matrix, as is obtained by Neville Elimination with no pivoting. Second, each nontrivial entry of this bidiagonal decomposition is a product of two quotients of (initial) minors. We conclude that Björck-Pereyra-type methods exist for every totally positive matrix whose (initial) minors are computable accurately and efficiently. We apply this theory to Totally Positive generalized Vandermonde matrices: $\begin{displaymath} G = \left[\begin{array}{cccc} x_1^{a_1} & x_1^{a_2} & \ldo... ...x_n^{a_1} & x_n^{a_2} & \ldots & x_n^{a_n} \end{array}\right], \end{displaymath}$ where $0\le a_1<a_2<\ldots<a_n$ are integers and $0<x_1<x_2<\ldots<x_n$ . The key to the accurate and efficient computation of minors of those matrices is the accurate and efficient computation of the Schur function $s_\lambda(x_1,\ldots,x_n)$ , because of the relationship $\begin{displaymath} \det G=\det V \cdot s_\lambda(x_1,\ldots,x_n), \end{displaymath}$ where $V=\left[x_i^{j-1} \right]_{i,j=1}^n$ is the ordinary Vandermonde matrix. We exploit the combinatorial properties of the Schur function to derive a recursive algorithm for its computation, resulting in Björck-Pereyra-type algorithms for this class of matrices. Time permitting, we will also present a new algorithm for computing the SVD to high relative accuracy of polynomial Vandermonde matrices involving orthogonal polynomials regardless of condition number.
Coauthors:	James Demmel, Dept. of Mathematics, UC-Berkeley

Session B: Talk #2	Computational Challenges in Cryo-Electron Microscopy Image Reconstruction
Presenter:	Chao Yang Scientifc Computing Group, Lawrence Berkeley National Laboratory
E-mail:	cyang@lbl.gov
Abstract:	Three-dimensional (3-D) density maps of biological molecules can be recovered by merging a large number of two-dimensional (2-D) projection images taken by a low-dose electron microscope. To avoid radiation damage, 2-D projection images are produced by taking a single shot of many identical but randomly oriented molecules embedded in a thin layer of vitreous ice (a technique known as cryo-electron microscopy). As a result, the relative orientations of the 2-D images are unknown. They must be determined as part of the solution to the 3-D image reconstruction problem. An iterative computational scheme for recovering the relative orientation parameters of the projection data and the 3-D density map has been developed by treating the reconstruction problem as a nonlinear optimization problem. In this talk, we will examine the computational complexity of the current computational scheme and discuss potential ways to improve the efficiency and quality of the reconstruction algorithm.

Session B: Talk #3	Unstructured Adaptive (UA) NAS Parallel Benchmark
Presenter:	Hiuyu Feng Nasa Ames Research Center
E-mail:	fhy@nas.nasa.gov
Abstract:	Unstructured Adaptive (UA), a new problem to be incorporated in the NAS Parallel Benchmarks, is designed to measure the performance of modern computer systems when solving scientific problems featuring irregular, dynamic memory accesses. The method involves the solution of a stylized 3-D heat transfer problem on an unstructured, adaptive grid. A Spectral Element Method (SEM) with an adaptive, nonconforming mesh is selected to discretize the transport equation. A space filling curve is used to handle the load balancing and domain-processor partitioning. The relatively high order of the SEM lowers the fraction of wall clock time spent on inter-processor communication, which eases the load balancing task and allows us to concentrate on the memory accesses.


Session C: Talk #1	Fast Phase Space Computation of Multiple Arrivals
Presenter:	Sergey Fomel UC-Berkeley
E-mail:	fomel@math.lbl.gov
Abstract:	We present a fast, general computational technique for computing the phase-space solution of static Hamilton-Jacobi equations. Starting with the Liouville formulation of the characteristic equations, we derive "Escape equations" which are static, time-independent Eulerian PDEs. They represent all arrivals to the given boundary from all possible starting configurations. The solution is numerically constructed through a one-pass formulation, building on ideas from semi-Lagrangian methods, Fast Marching Methods, and Ordered Upwind Methods. To compute all possible trajectories corresponding to all possible boundary conditions, the technique is of computational order N log N, where N is the total number of points in the computational phase-space domain; any particular set of boundary conditions is then extracted through rapid post-processing. As an application, we apply the technique to the problem of computing first, multiple, and most energetic arrivals to the Eikonal equation.
Coauthors:	James A. Sethian, UC-Berkeley

Session C: Talk #2	Adjoint sensitivity analysis for ODE and DAE systems
Presenter:	Radu Serban Lawrence Livermore National Laboratory
E-mail:	radu@llnl.gov
Abstract:	We discuss an adjoint sensitivity method for parameter-dependent ODE and DAE systems. The adjoint system is derived, along with conditions for its consistent initialization, for DAEs of index up to two (Hessenberg). For stable linear DAEs, stability of the adjoint system (for semi-explicit DAEs) or of an augmented adjoint system (for fully-implicit DAEs) is shown. Finally, we introduce an adjoint sensitivity extension of the ODE integrator CVODE. This work was performed under the auspices of the U.S. Department of Energy by the University of California, Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.


Session D: Talk #1	Challenges in Numerically Simulating Seismic Behavior of Constructed Facilities
Presenter:	Boris Jeremic Dept. of Civil Engineering, UC-Davis
E-mail:	Jeremic@ucdavis.edu
Abstract:	Research in earthquake engineering is focused on creating new methods and technology to improve performance of the built environment in earthquakes. We motivate this talk with an example of current simulations of seismic behavior of a Soil-Structure Interaction (SSI) system. More specifically, the analysis is concerned with the safety of the new bridge structure on I-880 just west of downtown Oakland. For this analysis, a number of computational and visualization issues had to be tackled. The work will be presented in light of both Neumann (physical) and Turing (computer) computability. In particular we will present computational methods related to: - Simulations of boundary conditions for the SSI system (earthquake input motions), - Distributed parallel simulations of the SSI system, - Data visualization of large tensorial data sets resulting from the SSI system simulations. In addition, an emerging Earthquake Engineering Grid Computational Platform will be discussed.

Session D: Talk #2	Safety First: Scientific Computation and the da Vinci(tm) Surgical System for Tele-Manipulation Surgery
Presenter:	William C. Nowlin Director, Software Systems Intuitive Surgical, Inc
E-mail:	bill.nowlin@intusurg.com
Abstract:	In this presentation, we introduce a tele-operated system for endoscopic surgery, the da Vinci(tm) Surgical System, and describe some of the challenges that must be overcome to make a system like this safe and effective to use in everyday surgery. The central concept of the tele-surgical system performance is, to a technologist, fairly straightforward: make the surgeon unaware that he (or she) is grasping an interface to a computer, in turn operating surgical manipulators on the surgeon's behalf, and instead convince the surgeon that what he sees and feels are his hands manipulating the tissue. The details of the application, however, reveal several stumbling blocks (for example, too high friction and inertias, too low bandwidth and stiffness). In the end, however, these can be overcome with careful design and relatively little heroics from the mathematicians. However, some of the more significant challenges arise only after the technology concept is proven and an "everyday use" product is the goal. In fact, a better problem statement might be: Find the vital few things that help convince the surgeon that the immersive illusion you are creating is "real enough" to be worth the effort to use every day. After a brief description of the technology, design and application of the system, the presenter would like to reflect on a couple of these challenges and describe Intuitive's algorithmic approaches for dealing with them.