Fifth Bay Area Scientific Computing Day

Lawrence Berkeley National Laboratory
Berkeley, California
March 13, 2004

ABSTRACTS OF THE TALKS

[click on the title to see the full presentation]

Lie-Quan Lee, Linxin Ge, Marc Kowalski, and Kwok Ko
Stanford Linear Accelerator Center

A case study of solving very large sparse linear systems in end-to-end accelerator structure simulations is presented. A parallel multilevel preconditioner based on hierarchical finite element basis functions is implemented to accelerate the convergence of the Conjugate Gradient linear solver. A linear system with matrix size 93,147,736 and with 3,964,961,944 non-zeros from three-dimensional electromagnetic finite element discretization has been solved in less than 8 minutes with 1024 CPUs on the NERSC IBM SP. The resource utilization as well as the application performance is discussed.

Fast Methods for Computing Certain Elements of the Inverse of a Sparse Matrix

Eric Darve
Stanford University

Calculating the diagonal entries of the inverse of a sparse matrix or a few specific entries is a problem that often occurs in quantum mechanics and other fields. For example, for quantum transport inside nano devices, the charge distribution inside the device is computed from the diagonal entries of the Green's function. In least-square data-fitting problems, the diagonal entries of the inverse of the normal matrix A^T A have particular significance since they yield estimates of the variances of the fitted parameters. Entries in the inverse can also be used to compute sensitivity information.

We will present methods based on recurrence formulas, cyclic reduction, total reduction and nested dissection. Those methods are efficient under certain assumptions such as properties of the underlying partial differential equations (e.g. Laplace versus Schrodinger). In the case of the Laplace equation in 2D and 3D, an algorithm in O(N) operations can be derived based on total reduction. For other types of partial differential equations (Schrodinger for example), nested dissection can be combined with Takahashi's relationships to obtain an algorithm in O(N^{3/2}) operations in 2D. This algorithm is also applicable to 3D problems but becomes more costly.

This work is on collaboration with G. Golub (Stanford University) and M.P. Anantram (NASA Ames).

Vessel Segmentation and Blood Flow Simulation Using Level-Sets and Embedded Boundary Methods

Thomas Deschamps
Lawrence Berkeley National Laboratory

Aneurysms and stenoses are examples of pathologies which involve complex flows in vascular passages such as cerebral arteries. Computational Fluid Dynamics (CFD) simulations of such flows can provide clinicians with information needed to evaluate how pathologies form, how they evolve, and ultimately how they are effectively treated. In order to do this, accurate methods are required to build the anatomical models, and CFD codes must be available that can run on anatomical models.

However, methods of surface extraction are limited in their ability to recover the geometry of complex objects like tubular branching structures in real time. Moreover, it is necessary to convert the surface extracted by image processing techniques into a computational domain appropriate for the CFD solver, involving the construction of a mesh on the surface and in the 3D domain surrounding it. Valuable information can be lost during this construction due to limitations of the CFD solvers with respect to the properties of the surface mesh. It is often the case, for example, that the surface needs to be smoothed in order to build a finite-element mesh necessary to some CFD codes. Failing that, irregular surfaces must be approximated by a large number of small mesh elements, pushing the limits of computer memory. The result in this and other cases is a compromise in the level of accuracy of the surface extraction method.

Some recent techniques of image processing enable an approximation of the surface of any vascular tree in the patient body to be built using CT or MR images of the patient enhanced with contrast product. In addition, recent techniques in CFD make easy use of these approximations from image processing in the generation of computational grids. The purpose of this work, therefore, is to couple a novel model extraction method with a high-resolution CFD code, with no loss of information from the latest image processing technique to the flow solver, and to accurately compute measures of fluid velocity, pressure and wall shear stress in realistic arterial geometries.

Computing Nonlinear Thermodynamics in Shape Memory Alloy Wires

Daniel R. Reynolds
Lawrence Livermore National Laboratory

In this talk I present a mesoscale mathematical model for the behavior of shape memory alloy wires. These so-called 'smart materials' are characterized by a unique ability to macroscopically transform their shape as a result of changes in temperature. The model consists of continuum-level conservation equations for the thermal and elastic properties, based on a new construction of the Helmholtz free energy potential. This system is paired with a computational solution technique that integrates a viscosity-based continuation method with an implicit Newton-Krylov solver, allowing for an efficient and robust solution to the non-convex modeling system. Computational experiments document that this combination of modeling and solution techniques appropriately predicts the thermally -and stress- induced martensitic transformations, hysteretic behavior, as well as the nonlinear thermal properties associated with shape memory alloys.

Gonzalo R. Feijó
Sandia National Laboratories

When imaging a transparent inhomogeneous medium with wavelengths on the order of the feature size, diffraction effects need to be taken into account for the proper reconstruction of the object or objects embedded in the medium. This imaging problem is usually referred to as "diffraction tomography." Widely used algorithms in X-ray tomography, such as backprojection, do not give satisfactory results in this case since they are based on ray models which cannot properly account for diffraction effects. Backpropagation-based algorithms attempt to solve this problem in either of two ways: (1) assuming that scatterers are weak, which implies that the Born or Rytov approximations can be applied to the wave field resulting in a closed form expression for the reconstructed profile; or (2) by solving the nonlinear inverse scattering problem using an iterative algorithm, which is computationally costly.

I will describe a new method in diffraction tomography that is based on the idea of an "optimal topology." The method relies on the definition of a function, called the topological derivative, with support in the imaged domain. This function quantifies the sensitivity (or derivative) of the scattered field upon the introduction of an infinitesimal scatterer at every point of the image. The expression for the topological derivative can be calculated analytically. As a result, the proposed scheme is not iterative. Furthermore, no assumptions like the Born or Rytov approximations are made. I will show through several numerical experiments that the image produced by this function is capable of reconstructing both the position and shape of scatterers with excellent agreement.


Simulating Radio-Frequency MEMS

David Bindel
University of California at Berkeley

Resonant microelectromechanical systems (MEMS) are already used in applications from gyroscopes to chemical sensors. In this talk, we discuss ongoing work at Berkeley to design and simulate micron-scale mechanical filters for radio-frequency signals. We describe the challenges of building, computing with, and validating meaningful models of these devices. We also describe related work on optimizing the behavior of resonator designs.


Automated Aerodynamic Optimization Using a Cartesian Method

Marian Nemec
NASA Advanced Supercomputing Division

A modular framework for aerodynamic optimization of complex geometries is developed. By working directly with a parametric CAD system, complex-geometry models are modified and tessellated in an automatic fashion. The use of a component-based Cartesian method significantly reduces the demands on the CAD system, and also provides for robust and efficient flowfield analysis. The optimization is controlled using either a genetic or quasi--Newton algorithm. Parallel efficiency of the framework is maintained even when subject to limited CAD resources by dynamically re-allocating the processors of the flow solver. Overall, the resulting framework can explore designs incorporating large shape modifications and changes in topology.

A Non-hydrostatic Model to Simulate Atmospheric Flows in the Presence of Orography

Caroline Bono
Lawrence Berkeley National Laboratory

The goal of this research is to develop a non-hydrostatic model for atmospheric flows in the presence of orography in order to set up a well-posed boundary problem that can be used in an AMR framework. We develop a two-dimensional all-speed algorithm that uses an embedded boundary formulation and captures gravity waves generated in a stratified atmosphere. The all-speed algorithm is further improved by proposing a separation of the numerics of fast and slow gravity waves so that time stepping is only limited by advection dynamics. Results are compared to and agree with the ones available in the literature.


Spatially Adaptive, High Resolution Recovery of Piecewise Smooth Data from its Spectral Information

Jared Tanner
University of California at Davis

Spectral projections enjoy high order convergence for globally smooth functions. However, a single discontinuity introduces O(1) spurious oscillations, Gibbs' Phenomena, and reduces the high order convergence rate to first order. We will show how adaptive order reconstructions can be used to recover exponential convergence away from the immediate neighborhood of discontinuities as well as remove the spurious oscillations. Applications to time dependent problems will be shown.

This work was conducted jointly with Eitan Tadmor.

Prolate Spheroidal Wave Functions, Quadratures, Interpolation and Applications

Hong Xiao
University of California at Davis

Whenever physical signals are measured or generated, the results tend to be band-limited (i.e. have compactly supported Fourier transforms). Indeed, measurements of electromagnetic and acoustic data are band-limited due to the oscillatory character of the processes that have generated the quantities being measured; when the signals being measured come from heat propagation or diffusion processes, they are (practically speaking) band-limited, since the underlying physical processes operate as low-pass filters. The importance of band-limited functions has been recognized for hundreds of years; classical Fourier analysis can be viewed as an apparatus for dealing with such functions. When the latter are defined on the whole line (or on a circle), classical tools are very satisfactory.

However, in many cases, we are confronted with band-limited functions defined on intervals (or, more generally, on compact regions in $\R^n$). In this environment, standard tools based on polynomials are often effective, but not optimal. In fact, the optimal approach was discovered more than 30 years ago by Slepian et al, who observed that for the analysis of band-limited functions on intervals, Prolate Spheroidal Wave Functions (PSWFs) are a natural tool. Although they built the requisite analytical apparatus in a sequence of famous papers, few numerical techniques ensued. Apparently, the principal reason for the lack of popularity of PSWFs was the absence of necessary numerical evaluation schemes.

In this talk, we will present recent developments in the theory of band-limited functions. we will start with noticing that in the modern numerical environment, evaluation of PSWFs presents no serious difficulties, and present a straightforward procedure for the numerical evaluation of PSWFs and related quantities. Based on PSWFs, we have constructed integration and interpolation schemes (both exact on certain classes of band-limited functions), which are analogous to the classical Gaussian quadratures and corresponding interpolation formulae for polynomials. We will illustrate our results with several examples.

This is joint work with V. Rokhlin of Department of Computer Science at Yale University.


Program Participants Back to main page