Poster Abstracts

Poster #1	An algorithm for the infinity-norm fixed point problem
Presenter:	Spencer Shellman School of Computing, University of Utah
E-mail:	shellman@cs.utah.edu
Abstract:	A new algorithm has been developed for solving the fixed point problem f(x)=x for functions that are Lipschitz continuous with constant 1 with respect to the infinity norm. Computed results satisfy the residual error criterion in the infinity norm. The worst-case complexity is less than exponential in the dimension and error tolerance.
Coauthors:	Dr. Krzyzstof Sikorski, School of Computing, University of Utah

Poster #2	Adaptive Wavelet Techniques for the Numerical Solution of Nonlinear evolutionary PDE: Optimum Wavelet Selection based on Wigner Phase Space Representations of Multiresolution Analysis
Presenter:	Dr. Bedros Afeyan Polymath Research, Inc
E-mail:	bedros@polymath-usa.com
Abstract:	WRMR analysis, or the Wigner Representation of Multiresolution analysis in phase space, is a useful technique by which to make a choice between wavelet families for optimal representations in certain function spaces. The WRMR technique will be demonstrated with band limited functions, solutions to the randomly driven Burgers equation and generalized nonlinear schrodinger equations using Mathematica Wavelet Explorer based routines developed at PRI. Adaptive methods of solving NL PDEs using these techniques will be discussed.

Poster #3	Cancelled ~~Object-Oriented Framework for Large Scale Air Pollution Modeling~~
Presenter:	Anton Antonov Wolfram Research, Inc
E-mail:	~~antonov@wolfram.com~~
Abstract:	The object-oriented methodology of patterns and pattern languages was applied to construct the object-oriented version of the large scale air pollution model known as the Danish Eulerian Model (DEM). The obtained framework is amenable to resolve new computational tasks and to be extended with new numerical methods. In the poster will be described the general design of the object-oriented DEM and the design of the different layers. Results from tests and experiments will be presented.

Poster #4	Automatic Performance Tuning of Sparse Matrix Kernels
Presenter:	Richard Vuduc UC, Berkeley
E-mail:	richie@cs.berkeley.edu
Abstract:	We consider automatic performance tuning of the sparse matrix kernels that dominate scientific and engineering computations. Traditionally, such kernels are tuned by hand for a specific target architecture and matrix. We adopt an automated methodology in which we identify and generate a space of algorithms, and then search for the fastest implementation using both run-time experiments and performance models. We present recent results for sparse matrix-vector multiply, triangular solve, and A^tA on various hardware platforms.
Coauthors:	James Demmel, Katherine Yelick, U.C. Berkeley

Poster #5	A survey of Levinson-type methods for Toeplitz systems
Presenter:	Aaron Melman St. Mary's College
E-mail:	melman@stmarys-ca.edu
Abstract:	We present a survey of Levinson-type methods for the solution of strongly nonsingular symmetric Toeplitz systems. Symmetric Toeplitz matrices exhibit an even-odd structure which, until fairly recently, was not fully exploited in Levinson-type algorithms. We will concentrate on the new algorithms which take advantage of this structure, leading to a decrease in complexity and an increase in parallelism.

Poster #6	Parallel Bipartite Matching for Sparse Matrix Computation
Presenter:	Jason Riedy UC, Berkeley
E-mail:	ejr@cs.berkeley.edu
Abstract:	Graph algorithms are notoriously difficult to parallelize, often because of sequential walks across vertices. Re-stating graph problems as matrix optimization problems can lead to parallel algorithms. One example is finding a maximum weight matching in a bipartite graph for pre-pivoting a sparse matrix. Augmenting path algorithms are inherently sequential, while optimization-based auction algorithms allow many parallelizations. We present distributed implementations of the auction algorithm and discuss how variations in implementation and problem structure affect performance.

Poster #7	A numerical method for solving the Bidomain equations in a human heart
Presenter:	Miguel A. Dumett Lawrence Livermore National Laboratory
E-mail:	dumett1@llnl.gov
Abstract:	The Bidomain equations (a system of an elliptic and a parabolic PDEs) are used to model the electrophysiology of the human heart. We present a second order stable generalization of the immersed interface method to solve an anisotropic elliptic PDE on an irregular domain in 2D and 3D and discuss certain extensions. Results show that the discretization matrix obtained is very stable, although accuracy of these methods are affected for the presence of anisotropy.

Poster #8	Towards Fermion Monte Carlo
Presenter:	Leonardo Colletti Center for Applied Scientific Computing, Lawrence Livermore National Laboratory
E-mail:	colletti1@llnl.gov
Abstract:	Among the techniques allowing the calculation of features of a quantum system, Monte Carlo methods are particularly interesting since their capability to lead to the solution of these non-probabilistic problems by means of probabilistic procedures. For bosonic systems they represent the benchmark for other methods, but for many-fermions systems they suffer for the "sign-problem", which arises right from the quantum nature of fermions and represents a fundamental challenge for physics. Methods are today in progress in order to overcome this limit.

Poster #9	Stabilizing MINOS
Presenter:	Michael P. Friedlander Systems Optimization Laboratory (SOL), Stanford University
E-mail:	mpf@stanford.edu
Abstract:	For problems with nonlinear constraints, linearly constrained Lagrangian (LCL) methods sequentially minimize an augmented Lagrangian subject to linearized constraints. Convergence is rapid near aa solution (as proved by Robinson and often observed with MINOS). To induce global convergence, we propose a modified algorithm that also provides for infeasible subproblems and inexact subproblem solutions. Our Matlab LCL implementation is efficient on large problems, using SNOPT as the subproblem solver. We present numerical results on CUTE and COPS test problems.
Coauthors:	Michael Saunders, SOL, Stanford University

Poster #10	SUGAR: A system-level simulator for MEMS devices
Presenter:	David Bindel Polymath Research, Inc
E-mail:	dbindel@cs.berkeley.edu
Abstract:	Designers of micro-electromechanical systems (MEMS) use a wealth of integrated circuit fabrication techniques, but little of the IC simulation technology. To fill this gap, we have designed the SUGAR simulator, which takes its name and heritage from SPICE. We discuss using SUGAR from Matlab or the Web, user interfaces to SUGAR, extending of the system in C or Matlab, and comparing simulation of a MEMS mirror to measured data.
Coauthors:	Jason Clark, UC Berkeley, applied physics David Garmire, UC Berkeley, computer science Babak Jamshidi, UC Berkeley, civil engineering Raffi Kamalian, UC Berkeley, mechanical engineering Shyam Lakshmin, UC Berkeley, computer science Jiawang Nie, UC Berkeley, math Ningning Zhou, UC Berkeley, mechanical engineering Wayne Kao, UC Berkeley, computer science Ernest Zhu, UC Berkeley, computer science Andy Kuo, University of Michigan, electrical engineering Alice Agogino, UC Berkeley, mechanical engineering Zhaojun Bai, UC Davis, math and computer science James Demmel, UC Berkeley, math and computer science Sanjay Govindjee, UC Berkeley, civil engineering Ming Gu, UC Berkeley, math Kristofer S.J. Pister, UC Berkeley, electrical engineering

Poster #11	Image Segmentation Using Normalized Cut
Presenter:	Monika Jankun-Kelly University of California, Davis
E-mail:	jankunm@cs.ucdavis.edu
Abstract:	Image segmentation partitions an image into self-similar segments. The image is represented by a graph, with nodes replacing pixels, and edge weights measuring interpixel similarity. A cut partitions this graph into subgraphs. The normalized cut (Ncut) balances high intersubgraph difference and high intrasubgraph similarity. The best Ncut is found through minimization, which leads to an eigenproblem. This poster presents interesting features of the Ncut segmentation method, structure and properties of the associated eigenproblem, and challenges to overcome.

Poster #12	Parallel Multistep Sparse Approximate Inverse Preconditioning Strategies for General Sparse Matrices
Presenter:	Jun Zhang Laboratory for High Performance Scientific Computing and Computer Simulation, Department of Computer Science, University of Kentucky
E-mail:	jzhang@cs.uky.edu
Abstract:	We develop new concepts and parallel algorithms of multistep successive preconditioning strategies to enhance efficiency and robustness of standard sparse approximate inverse preconditioning techniques. The key idea is to compute a series of simple sparse matrices to approximate the inverse of the original matrix. Studies are conducted to show the advantages of such an approach in terms of both improving preconditioning accuracy and reducing computational cost. Numerical experiments using one prototype implementation to solve a few general sparse matrices on a distributed memory parallel computer are reported.
Coauthors:	Kai Wang, Laboratory for High Performance Scientific Computing and Computer Simulation, Department of Computer Science, University of Kentucky

Poster #13	Sundance: a Rapid-Development Toolkit for Parallel PDE Simulations
Presenter:	Kevin Long Computational Sciences and Mathematics Research, Sandia National Laboratories
E-mail:	krlong@sandia.gov
Abstract:	Research in algorithms for PDE solvers and PDE-constrained optimizers can entail significant startup costs for code development. Sundance provides a set of high-level components allowing flexibility in formulation, discretization, and solution of a finite-element problem. Sundance shields the researcher from tedious bookkeeping code and facilitates quick exploration of ideas, yet still yields high performance and parallel capability. Sundance reduces both the startup time for research and the transition time from research to production code.