Publications

Abstract not provided.

Our aim is to determine the network of events, or the regulatory network, that defines an immune response to a bio-toxin. As a model system, we are studying T cell regulatory network triggered through tyrosine kinase receptor activation using a combination of pathway stimulation and time-series microarray experiments. Our approach is composed of five steps (1) microarray experiments and data error analysis, (2) data clustering, (3) data smoothing and discretization, (4) network reverse engineering, and (5) network dynamics analysis and fingerprint identification. The technological outcome of this study is a suite of experimental protocols and computational tools that reverse engineer regulatory networks provided gene expression data. The practical biological outcome of this work is an immune response fingerprint in terms of gene expression levels. Inferring regulatory networks from microarray data is a new field of investigation that is no more than five years old. To the best of our knowledge, this work is the first attempt that integrates experiments, error analyses, data clustering, inference, and network analysis to solve a practical problem. Our systematic approach of counting, enumeration, and sampling networks matching experimental data is new to the field of network reverse engineering. The resulting mathematical analyses and computational tools lead to new results on their own and should be useful to others who analyze and infer networks.

The thermal challenge problem has been developed at Sandia National Laboratories as a testbed for demonstrating various types of validation approaches and prediction methods. This report discusses one particular methodology to assess the validity of a computational model given experimental data. This methodology is based on Bayesian Belief Networks (BBNs) and can incorporate uncertainty in experimental measurements, in physical quantities, and model uncertainties. The approach uses the prior and posterior distributions of model output to compute a validation metric based on Bayesian hypothesis testing (a Bayes' factor). This report discusses various aspects of the BBN, specifically in the context of the thermal challenge problem. A BBN is developed for a given set of experimental data in a particular experimental configuration. The development of the BBN and the method for ''solving'' the BBN to develop the posterior distribution of model output through Monte Carlo Markov Chain sampling is discussed in detail. The use of the BBN to compute a Bayes' factor is demonstrated.

The formation and functions of living materials and organisms are fundamentally different from those of synthetic materials and devices. Synthetic materials tend to have static structures, and are not capable of adapting to the functional needs of changing environments. In contrast, living systems utilize energy to create, heal, reconfigure, and dismantle materials in a dynamic, non-equilibrium fashion. The overall goal of the project was to organize and reconfigure functional assemblies of nanoparticles using strategies that mimic those found in living systems. Active assembly of nanostructures was studied using active biomolecules to drive the organization and assembly of nanocomposite materials. In this system, kinesin motor proteins and microtubules were used to direct the transport and interactions of nanoparticles at synthetic interfaces. In addition, the kinesin/microtubule transport system was used to actively assemble nanocomposite materials capable of storing significant elastic energy. Novel biophysical measurement tools were also developed for measuring the collective force generated by kinesin motor proteins, which will provide insight on the mechanical constraints of active assembly processes. Responsive reconfiguration of nanostructures was studied in terms of using active biomolecules to mediate the optical properties of quantum dot (QD) arrays through modulation of inter-particle spacing and associated energy transfer interaction. Design rules for kinesin-based transport of a wide range of nanoscale cargo (e.g., nanocrystal quantum dots, micron-sized polymer spheres) were developed. Three-dimensional microtubule organizing centers were assembled in which the polar orientation of the microtubules was controlled by a multi-staged assembly process. Overall, a number of enabling technologies were developed over the course of this project, and will drive the exploitation of energy-driven processes to regulate the assembly, disassembly, and dynamic reorganization of nanomaterials.

Understanding the properties and behavior of biomembranes is fundamental to many biological processes and technologies. Microdomains in biomembranes or ''lipid rafts'' are now known to be an integral part of cell signaling, vesicle formation, fusion processes, protein trafficking, and viral and toxin infection processes. Understanding how microdomains form, how they depend on membrane constituents, and how they act not only has biological implications, but also will impact Sandia's effort in development of membranes that structurally adapt to their environment in a controlled manner. To provide such understanding, we created physically-based models of biomembranes. Molecular dynamics (MD) simulations and classical density functional theory (DFT) calculations using these models were applied to phenomena such as microdomain formation, membrane fusion, pattern formation, and protein insertion. Because lipid dynamics and self-organization in membranes occur on length and time scales beyond atomistic MD, we used coarse-grained models of double tail lipid molecules that spontaneously self-assemble into bilayers. DFT provided equilibrium information on membrane structure. Experimental work was performed to further help elucidate the fundamental membrane organization principles.

This report documents research to develop robust and efficient solution techniques for solving large-scale systems of nonlinear equations. The most widely used method for solving systems of nonlinear equations is Newton's method. While much research has been devoted to augmenting Newton-based solvers (usually with globalization techniques), little has been devoted to exploring the application of different models. Our research has been directed at evaluating techniques using different models than Newton's method: a lower order model, Broyden's method, and a higher order model, the tensor method. We have developed large-scale versions of each of these models and have demonstrated their use in important applications at Sandia. Broyden's method replaces the Jacobian with an approximation, allowing codes that cannot evaluate a Jacobian or have an inaccurate Jacobian to converge to a solution. Limited-memory methods, which have been successful in optimization, allow us to extend this approach to large-scale problems. We compare the robustness and efficiency of Newton's method, modified Newton's method, Jacobian-free Newton-Krylov method, and our limited-memory Broyden method. Comparisons are carried out for large-scale applications of fluid flow simulations and electronic circuit simulations. Results show that, in cases where the Jacobian was inaccurate or could not be computed, Broyden's method converged in some cases where Newton's method failed to converge. We identify conditions where Broyden's method can be more efficient than Newton's method. We also present modifications to a large-scale tensor method, originally proposed by Bouaricha, for greater efficiency, better robustness, and wider applicability. Tensor methods are an alternative to Newton-based methods and are based on computing a step based on a local quadratic model rather than a linear model. The advantage of Bouaricha's method is that it can use any existing linear solver, which makes it simple to write and easily portable. However, the method usually takes twice as long to solve as Newton-GMRES on general problems because it solves two linear systems at each iteration. In this paper, we discuss modifications to Bouaricha's method for a practical implementation, including a special globalization technique and other modifications for greater efficiency. We present numerical results showing computational advantages over Newton-GMRES on some realistic problems. We further discuss a new approach for dealing with singular (or ill-conditioned) matrices. In particular, we modify an algorithm for identifying a turning point so that an increasingly ill-conditioned Jacobian does not prevent convergence.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

This SAND report provides the technical progress through April 2005 of the Sandia-led project, ''Carbon Sequestration in Synechococcus Sp.: From Molecular Machines to Hierarchical Modeling'', funded by the DOE Office of Science GenomicsGTL Program. Understanding, predicting, and perhaps manipulating carbon fixation in the oceans has long been a major focus of biological oceanography and has more recently been of interest to a broader audience of scientists and policy makers. It is clear that the oceanic sinks and sources of CO{sub 2} are important terms in the global environmental response to anthropogenic atmospheric inputs of CO{sub 2} and that oceanic microorganisms play a key role in this response. However, the relationship between this global phenomenon and the biochemical mechanisms of carbon fixation in these microorganisms is poorly understood. In this project, we will investigate the carbon sequestration behavior of Synechococcus Sp., an abundant marine cyanobacteria known to be important to environmental responses to carbon dioxide levels, through experimental and computational methods. This project is a combined experimental and computational effort with emphasis on developing and applying new computational tools and methods. Our experimental effort will provide the biology and data to drive the computational efforts and include significant investment in developing new experimental methods for uncovering protein partners, characterizing protein complexes, identifying new binding domains. We will also develop and apply new data measurement and statistical methods for analyzing microamy experiments. Computational tools will be essential to our efforts to discover and characterize the function of the molecular machines of Synechococcus. To this end, molecular simulation methods will be coupled with knowledge discovery from diverse biological data sets for high-throughput discovery and characterization of protein-protein complexes. In addition, we will develop a set of novel capabilities for inference of regulatory pathways in microbial genomes across multiple sources of information through the integration of computational and experimental technologies. These capabilities will be applied to Synechococcus regulatory pathways to characterize their interaction map and identify component proteins in these pathways. We will also investigate methods for combining experimental and computational results with visualization and natural language tools to accelerate discovery of regulatory pathways. The ultimate goal of this effort is develop and apply new experimental and computational methods needed to generate a new level of understanding of how the Synechococcus genome affects carbon fixation at the global scale. Anticipated experimental and computational methods will provide ever-increasing insight about the individual elements and steps in the carbon fixation process, however relating an organism's genome to its cellular response in the presence of varying environments will require systems biology approaches. Thus a primary goal for this effort is to integrate the genomic data generated from experiments and lower level simulations with data from the existing body of literature into a whole cell model. We plan to accomplish this by developing and applying a set of tools for capturing the carbon fixation behavior of complex of Synechococcus at different levels of resolution. Finally, the explosion of data being produced by high-throughput experiments requires data analysis and models which are more computationally complex, more heterogeneous, and require coupling to ever increasing amounts of experimentally obtained data in varying formats. These challenges are unprecedented in high performance scientific computing and necessitate the development of a companion computational infrastructure to support this effort.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

This report describes the test and evaluation methods by which the Teraflops Operating System, or TOS, that resides on Sandia's massively-parallel computer Janus is verified for production release. Also discussed are methods used to build TOS before testing and evaluating, miscellaneous utility scripts, a sample test plan, and a proposed post-test method for quickly examining the large number of test results. The purpose of the report is threefold: (1) to provide a guide to T&E procedures, (2) to aid and guide others who will run T&E procedures on the new ASCI Red Storm machine, and (3) to document some of the history of evaluation and testing of TOS. This report is not intended to serve as an exhaustive manual for testers to conduct T&E procedures.

Threats to water distribution systems include release of contaminants and Denial of Service (DoS) attacks. A better understanding, and validated computational models, of the flow in water distribution systems would enable determination of sensor placement in real water distribution networks, allow source identification, and guide mitigation/minimization efforts. Validation data are needed to evaluate numerical models of network operations. Some data can be acquired in real-world tests, but these are limited by 1) unknown demand, 2) lack of repeatability, 3) too many sources of uncertainty (demand, friction factors, etc.), and 4) expense. In addition, real-world tests have limited numbers of network access points. A scale-model water distribution system was fabricated, and validation data were acquired over a range of flow (demand) conditions. Standard operating variables included system layout, demand at various nodes in the system, and pressure drop across various pipe sections. In addition, the location of contaminant (salt or dye) introduction was varied. Measurements of pressure, flowrate, and concentration at a large number of points, and overall visualization of dye transport through the flow network were completed. Scale-up issues that that were incorporated in the experiment design include Reynolds number, pressure drop across nodes, and pipe friction and roughness. The scale was chosen to be 20:1, so the 10 inch main was modeled with a 0.5 inch pipe in the physical model. Controlled validation tracer tests were run to provide validation to flow and transport models, especially of the degree of mixing at pipe junctions. Results of the pipe mixing experiments showed large deviations from predicted behavior and these have a large impact on standard network operations models.3

Abstract not provided.

This work focuses on different methods to generate confidence regions for nonlinear parameter identification problems. Three methods for confidence region estimation are considered: a linear approximation method, an F-test method, and a Log-Likelihood method. Each of these methods are applied to three case studies. One case study is a problem with synthetic data, and the other two case studies identify hydraulic parameters in groundwater flow problems based on experimental well-test results. The confidence regions for each case study are analyzed and compared. Although the F-test and Log-Likelihood methods result in similar regions, there are differences between these regions and the regions generated by the linear approximation method for nonlinear problems. The differing results, capabilities, and drawbacks of all three methods are discussed.

The goal of our paper is to compare a number of algorithms for computing a large number of eigenvectors of the generalized symmetric eigenvalue problem arising from a modal analysis of elastic structures. The shift-invert Lanczos algorithm has emerged as the workhorse for the solution of this generalized eigenvalue problem; however, a sparse direct factorization is required for the resulting set of linear equations. Instead, our paper considers the use of preconditioned iterative methods. We present a brief review of available preconditioned eigensolvers followed by a numerical comparison on three problems using a scalable algebraic multigrid (AMG) preconditioner. Copyright © 2005 John Wiley & Sons, Ltd.

Semantic graphs offer one promising avenue for intelligence analysis in homeland security. They provide a mechanism for describing a wide variety of relationships between entities of potential interest. The vertices are nouns of various types, e.g. people, organizations, events, etc. Edges in the graph represent different types of relationships between entities, e.g. 'is friends with', 'belongs-to', etc. Semantic graphs offer a number of potential advantages as a knowledge representation system. They allow information of different kinds, and collected in differing ways, to be combined in a seamless manner. A semantic graph is a very compressed representation of some of relationship information. It has been reported that the semantic graph can be two orders of magnitude smaller than the processed intelligence data. This allows for much larger portions of the data universe to be resident in computer memory. Many intelligence queries that are relevant to the terrorist threat are naturally expressed in the language of semantic graphs. One example is the search for 'interesting' relationships between two individuals or between an individual and an event, which can be phrased as a search for short paths in the graph. Another example is the search for an analyst-specified threat pattern, which can be cast as an instance of subgraph isomorphism. It is important to note than many kinds of analysis are not relationship based, so these are not good candidates for semantic graphs. Thus, a semantic graph should always be used in conjunction with traditional knowledge representation and interface methods. Operations that involve looking for chains of relationships (e.g. friend of a friend) are not efficiently executable in a traditional relational database. However, the semantic graph can be thought of as a pre-join of the database, and it is ideally suited for these kinds of operations. Researchers at Sandia National Laboratories are working to facilitate semantic graph analysis. Since intelligence datasets can be extremely large, the focus of this work is on the use of parallel computers. We have been working to develop scalable parallel algorithms that will be at the core of a semantic graph analysis infrastructure. Our work has involved two different thrusts, corresponding to two different computer architectures. The first architecture of interest is distributed memory, message passing computers. These machines are ubiquitous and affordable, but they are challenging targets for graph algorithms. Much of our distributed-memory work to date has been collaborative with researchers at Lawrence Livermore National Laboratory and has focused on finding short paths on distributed memory parallel machines. Our implementation on 32K processors of BlueGene/Light finds shortest paths between two specified vertices in just over a second for random graphs with 4 billion vertices.

Abstract not provided.

Electromagnetic induction is a classic geophysical exploration method designed for subsurface characterization--in particular, sensing the presence of geologic heterogeneities and fluids such as groundwater and hydrocarbons. Several approaches to the computational problems associated with predicting and interpreting electromagnetic phenomena in and around the earth are addressed herein. Publications resulting from the project include [31]. To obtain accurate and physically meaningful numerical simulations of natural phenomena, computational algorithms should operate in discrete settings that reflect the structure of governing mathematical models. In section 2, the extension of algebraic multigrid methods for the time domain eddy current equations to the frequency domain problem is discussed. Software was developed and is available in Trilinos ML package. In section 3 we consider finite element approximations of De Rham's complex. We describe how to develop a family of finite element spaces that forms an exact sequence on hexahedral grids. The ensuing family of non-affine finite elements is called a van Welij complex, after the work [37] of van Welij who first proposed a general method for developing tangentially and normally continuous vector fields on hexahedral elements. The use of this complex is illustrated for the eddy current equations and a conservation law problem. Software was developed and is available in the Ptenos finite element package. The more popular methods of geophysical inversion seek solutions to an unconstrained optimization problem by imposing stabilizing constraints in the form of smoothing operators on some enormous set of model parameters (i.e. ''over-parametrize and regularize''). In contrast we investigate an alternative approach whereby sharp jumps in material properties are preserved in the solution by choosing as model parameters a modest set of variables which describe an interface between adjacent regions in physical space. While still over-parametrized, this choice of model space contains far fewer parameters than before, thus easing the computational burden, in some cases, of the optimization problem. And most importantly, the associated finite element discretization is aligned with the abrupt changes in material properties associated with lithologic boundaries as well as the interface between buried cultural artifacts and the surrounding Earth. In section 4, algorithms and tools are described that associate a smooth interface surface to a given triangulation. In particular, the tools support surface refinement and coarsening. Section 5 describes some preliminary results on the application of interface identification methods to some model problems in geophysical inversion. Due to time constraints, the results described here use the GNU Triangulated Surface Library for the manipulation of surface meshes and the TetGen software library for the generation of tetrahedral meshes.

The peridynamic model was introduced by Silling in 1998. In this paper, we demonstrate the application of the quasistatic peridynamic model to two-dimensional, linear elastic, plane stress and plane strain problems, with special attention to the modeling of plain and reinforced concrete structures. We consider just one deviation from linearity--that which arises due to the irreversible sudden breaking of bonds between particles. The peridynamic model starts with the assumption that Newton's second law holds true on every infinitesimally small free body (or particle) within the domain of analysis. A specified force density function, called the pairwise force function, (with units of force per unit volume per unit volume) between each pair of infinitesimally small particles is postulated to act if the particles are closer together than some finite distance, called the material horizon. The pairwise force function may be assumed to be a function of the relative position and the relative displacement between the two particles. In this paper, we assume that for two particles closer together than the specified 'material horizon' the pairwise force function increases linearly with respect to the stretch, but at some specified stretch, the pairwise force function is irreversibly reduced to zero.

Abstract not provided.

Due to advances in CMOS fabrication technology, high performance computing capabilities have continually grown. More capable hardware has allowed a range of complex scientific applications to be developed. However, these applications present a bottleneck to future performance. Entrenched 'legacy' codes - 'Dusty Decks' - demand that new hardware must remain compatible with existing software. Additionally, conventional architectures faces increasing challenges. Many of these challenges revolve around the growing disparity between processor and memory speed - the 'Memory Wall' - and difficulties scaling to large numbers of parallel processors. To a large extent, these limitations are inherent to the traditional computer architecture. As data is consumed more quickly, moving that data to the point of computation becomes more difficult. Barring any upward revision in the speed of light, this will continue to be a fundamental limitation on the speed of computation. This work focuses on these solving these problems in the context of Light Weight Processing (LWP). LWP is an innovative technique which combines Processing-In-Memory, short vector computation, multithreading, and extended memory semantics. It applies these techniques to try and answer the questions 'What will a next-generation supercomputer look like?' and 'How will we program it?' To that end, this work presents four contributions: (1) An implementation of MPI which uses features of LWP to substantially improve message processing throughput; (2) A technique leveraging extended memory semantics to improve message passing by overlapping computation and communication; (3) An OpenMP library modified to allow efficient partitioning of threads between a conventional CPU and LWPs - greatly improving cost/performance; and (4) An algorithm to extract very small 'threadlets' which can overcome the inherent disadvantages of a simple processor pipeline.

Abstract not provided.

Abstract not provided.

Abstract not provided.

In gas chromatography, a chemical sample separates into its constituent components as it travels along a long thin column. As the component chemicals exit the column they are detected and identified, allowing the chemical makeup of the sample to be determined. For correct identification of the component chemicals, the distribution of the concentration of each chemical along the length of the column must be nearly symmetric. The prediction and control of asymmetries in gas chromatography has been an active research area since the advent of the technique. In this paper, we develop from first principles a general model for isothermal linear chromatography. We use this model to develop closed-form expressions for terms related to the first, second, and third moments of the distribution of the concentration, which determines the velocity, diffusion rate, and asymmetry of the distribution. We show that for all practical experimental situations, only fronting peaks are predicted by this model, suggesting that a nonlinear chromatography model is required to predict tailing peaks. For situations where asymmetries arise, we analyze the rate at which the concentration distribution returns to a normal distribution. Numerical examples are also provided.

Abstract not provided.

Abstract not provided.

The approximate solution of optimization and control problems for systems governed by linear, elliptic partial differential equations is considered. Such problems are most often solved using methods based on the application of the Lagrange multiplier rule followed by discretization through, e.g., a Galerkin finite element method. As an alternative, we show how least-squares finite element methods can be used for this purpose. Penalty-based formulations, another approach widely used in other settings, have not enjoyed the same level of popularity in the partial differential equation case perhaps because naively defined penalty-based methods can have practical deficiencies. We use methodologies associated with modern least-squares finite element methods to develop and analyze practical penalty methods for the approximate solution of optimization problems for systems governed by linear, elliptic partial differential equations. We develop an abstract theory for such problems; along the way, we introduce several methods based on least-squares notions, and compare and constrast their properties.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Wereportonthedesignofgeneral,flexible,consistentandefficientinterfacestodirectsolveralgorithmsforthesolutionofsystemsoflinearequations.Wesupposethatsuchalgorithmsareavailableinformofsoftwarelibraries,andweintroduceaframeworktofacilitatetheusageoftheselibraries.Thisframeworkiscomposedbytwocomponents:anabstractmatrixinterfacetoaccessthelinearsystemmatrixelements,andanabstractsolverinterfacethatcontrolsthesolutionofthelinearsystem.Wedescribeaconcreteimplementationoftheproposedframework,whichallowsahigh-levelviewandusageofmostofthecurrentlyavailablelibrariesthatimplementsdirectsolutionmethodsforlinearsystems.Wecommentontheadvantagesandlimitationoftheframework.3

Under conditions that were predicted as 'safe' by well-established TCAD packages, radiation hardness can still be significantly degraded by a few lucky arsenic ions reaching the gate oxide during self-aligned CMOS source/drain ion implantation. The most likely explanation is that both oxide traps and interface traps are created when ions penetrate and damage the gate oxide after channeling or traveling along polysilicon grain boundaries during the implantation process.

Abstract not provided.

Graph partitioning is often used for load balancing in parallel computing, but it is known that hypergraph partitioning has several advantages. First, hypergraphs more accurately model communication volume, and second, they are more expressive and can better represent nonsymmetric problems. Hypergraph partitioning is particularly suited to parallel sparse matrix-vector multiplication, a common kernel in scientific computing. We present a parallel software package for hypergraph (and sparse matrix) partitioning developed at Sandia National Labs. The algorithm is a variation on multilevel partitioning. Our parallel implementation is novel in that it uses a two-dimensional data distribution among processors. We present empirical results that show our parallel implementation achieves good speedup on several large problems (up to 33 million nonzeros) with up to 64 processors on a Linux cluster.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

The latency and throughput of MPI messages are critically important to a range of parallel scientific applications. In many modern networks, both of these performance characteristics are largely driven by the performance of a processor on the network interface. Because of the semantics of MPI, this embedded processor is forced to traverse a linked list of posted receives each time a message is received. As this list grows long, the latency of message reception grows and the throughput of MPI messages decreases. This paper presents a novel hardware feature to handle list management functions on a network interface. By moving functions such as list insertion, list traversal, and list deletion to the hardware unit, latencies are decreased by up to 20% in the zero length queue case with dramatic improvements in the presence of long queues. Similarly, the throughput is increased by up to 10% in the zero length queue case and by nearly 100% in the presence queues of 30 messages.

Abstract not provided.

Proliferation of degrees-of-freedom has plagued discontinuous Galerkin methodology from its inception over 30 years ago. This paper develops a new computational formulation that combines the advantages of discontinuous Galerkin methods with the data structure of their continuous Galerkin counterparts. The new method uses local, element-wise problems to project a continuous finite element space into a given discontinuous space, and then applies a discontinuous Galerkin formulation. The projection leads to parameterization of the discontinuous degrees-of-freedom by their continuous counterparts and has a variational multiscale interpretation. This significantly reduces the computational burden and, at the same time, little or no degradation of the solution occurs. In fact, the new method produces improved solutions compared with the traditional discontinuous Galerkin method in some situations.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Controlled seeding of perturbations is employed to study the evolution of wire array z-pinch implosion instabilities which strongly impact x-ray production when the 3D plasma stagnates on axis. Wires modulated in radius exhibit locally enhanced magnetic field and imploding bubble formation at discontinuities in wire radius due to the perturbed current path. Wires coated with localized spectroscopic dopants are used to track turbulent material flow. Experiments and MHD modeling offer insight into the behavior of z-pinch instabilities.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

The success of Lagrangian contact modeling leads one to believe that important aspects of this capability may be used for multi-material modeling when only a portion of the simulation can be represented in a Lagrangian frame. We review current experience with two dual mesh technologies where one of these meshes is a Lagrangian mesh and the other is an Arbitrary Lagrangian/Eulerian (ALE) mesh. These methods are cast in the framework of an operator-split ALE algorithm where a Lagrangian step is followed by a remesh/remap step. An interface-coupled methodology is considered first. This technique is applicable to problems involving contact between materials of dissimilar compliance. The technique models the more compliant (soft) material as ALE while the less compliant (hard) material and associated interface are modeled in a Lagrangian fashion. Loads are transferred between the hard and soft materials via explicit transient dynamics contact algorithms. The use of these contact algorithms remove the requirement of node-tonode matching at the soft-hard interface. In the context of the operator-split ALE algorithm, a single Lagrangian step is performed using a mesh to mesh contact algorithm. At the end of the Lagrangian step the meshes will be slightly offset at the interface but non-interpenetrating. The ALE mesh nodes at the interface are then remeshed to their initial location relative to the Lagrangian body faces and the ALE mesh is smoothed, translated and rotated to follow Lagrangian body. Robust remeshing in the ALE region is required for success of this algorithm, and we describe current work in this area. The second method is an overlapping grid methodology that requires mapping of information between a Lagrangian mesh and an ALE mesh. The Lagrangian mesh describes a relatively hard body that interacts with softer material contained in the ALE mesh. A predicted solution for the velocity field is performed independently on both meshes. Element-centered velocity and momentum are transferred between the meshes using the volume transfer capability implemented in contact algorithms. Data from the ALE mesh is mapped to a phantom mesh that surrounds the Lagrangian mesh, providing for the reaction to the predicted motion of the Lagrangian material. Data from the Lagrangian mesh is mapped directly to the ALE mesh. A momentum balance is performed on both meshes to adjust the velocity field to account for the interaction of the material from the other mesh. Subsequent, remeshing and remapping of the ALE mesh is performed to allow large deformation of the softer material. We overview current progress using this approach and discuss avenues for future research and development.

Abstract not provided.

We provide a common framework for compatible discretizations using algebraic topology to guide our analysis. The main concept is the natural inner product on cochains, which induces a combinatorial Hodge theory. The framework comprises of mutually consistent operations of differentiation and integration, has a discrete Stokes theorem, and preserves the invariants of the DeRham cohomology groups. The latter allows for an elementary calculation of the kernel of the discrete Laplacian. Our framework provides an abstraction that includes examples of compatible finite element, finite volume and finite difference methods. We describe how these methods result from the choice of a reconstruction operator and when they are equivalent.

Abstract not provided.

Abstract not provided.

The overlap of computation and communication has long been considered to be a significant performance benefit for applications. Similarly, the ability of the Message Passing Interface (MPI) to make independent progress (that is, to make progress on outstanding communication operations while not in the MPI library) is also believed to yield performance benefits. Using an intelligent network interface to offload the work required to support overlap and independent progress is thought to be an ideal solution, but the benefits of this approach have not been studied in depth at the application level. This lack of analysis is complicated by the fact that most MPI implementations do not sufficiently support overlap or independent progress. Recent work has demonstrated a quantifiable advantage for an MPI implementation that uses offload to provide overlap and independent progress. The study is conducted on two different platforms with each having two MPI implementations (one with and one without independent progress). Thus, identical network hardware and virtually identical software stacks are used. Furthermore, one platform, ASCI Red, allows further separation of features such as overlap and offload. Thus, this paper extends previous work by further qualifying the source of the performance advantage: offload, overlap, or independent progress.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Molecular dynamics calculations are performed to study the effect of deformation sequence and history on the inelastic behavior of copper interfaces on the nanoscale. An asymmetric 45 deg tilt bicrystal interface is examined, representing an idealized high-angle grain boundary interface. The interface model is subjected to three different deformation paths: tension then shear, shear then tension, and combined proportional tension and shear. Analysis shows that path-history dependent material behavior is confined within a finite layer of deformation around the bicrystal interface. The relationships between length scale and interface properties, such as the thickness of the path-history dependent layer and the interface strength, are discussed in detail.

A conforming representation composed of 2D finite elements and finite Fourier series is applied to 3D nonlinear non-ideal magnetohydrodynamics using a semi-implicit time-advance. The self-adjoint semi-implicit operator and variational approach to spatial discretization are synergistic and enable simulation in the extremely stiff conditions found in high temperature plasmas without sacrificing the geometric flexibility needed for modeling laboratory experiments. Growth rates for resistive tearing modes with experimentally relevant Lundquist number are computed accurately with time-steps that are large with respect to the global Alfven time and moderate spatial resolution when the finite elements have basis functions of polynomial degree (p) two or larger. An error diffusion method controls the generation of magnetic divergence error. Convergence studies show that this approach is effective for continuous basis functions with p {ge} 2, where the number of test functions for the divergence control terms is less than the number of degrees of freedom in the expansion for vector fields. Anisotropic thermal conduction at realistic ratios of parallel to perpendicular conductivity (x{parallel}/x{perpendicular}) is computed accurately with p {ge} 3 without mesh alignment. A simulation of tearing-mode evolution for a shaped toroidal tokamak equilibrium demonstrates the effectiveness of the algorithm in nonlinear conditions, and its results are used to verify the accuracy of the numerical anisotropic thermal conduction in 3D magnetic topologies.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

In this paper we present a two-level overlapping domain decomposition preconditioner for the finite-element discretization of elliptic problems in two and three dimensions. The computational domain is partitioned into overlapping subdomains, and a coarse space correction, based on aggregation techniques, is added. Our definition of the coarse space does not require the introduction of a coarse grid. We consider a set of assumptions on the coarse basis functions to bound the condition number of the resulting preconditioned system. These assumptions involve only geometrical quantities associated with the aggregates and the subdomains. We prove that the condition number using the two-level additive Schwarz preconditioner is O(H/{delta} + H{sub 0}/{delta}), where H and H{sub 0} are the diameters of the subdomains and the aggregates, respectively, and {delta} is the overlap among the subdomains and the aggregates. This extends the bounds presented in [C. Lasser and A. Toselli, Convergence of some two-level overlapping domain decomposition preconditioners with smoothed aggregation coarse spaces, in Recent Developments in Domain Decomposition Methods, Lecture Notes in Comput. Sci. Engrg. 23, L. Pavarino and A. Toselli, eds., Springer-Verlag, Berlin, 2002, pp. 95-117; M. Sala, Domain Decomposition Preconditioners: Theoretical Properties, Application to the Compressible Euler Equations, Parallel Aspects, Ph.D. thesis, Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland, 2003; M. Sala, Math. Model. Numer. Anal., 38 (2004), pp. 765-780]. Numerical experiments on a model problem are reported to illustrate the performance of the proposed preconditioner.

This manual describes the use of theXyceParallel Electronic Simulator.Xycehasbeen designed as a SPICE-compatible, high-performance analog circuit simulator, andhas been written to support the simulation needs of the Sandia National Laboratorieselectrical designers. This development has focused on improving capability over thecurrent state-of-the-art in the following areas:%04Capability to solve extremely large circuit problems by supporting large-scale par-allel computing platforms (up to thousands of processors). Note that this includessupport for most popular parallel and serial computers.%04Improved performance for all numerical kernels (e.g., time integrator, nonlinearand linear solvers) through state-of-the-art algorithms and novel techniques.%04Device models which are specifically tailored to meet Sandia's needs, includingmany radiation-aware devices.3 XyceTMUsers' Guide%04Object-oriented code design and implementation using modern coding practicesthat ensure that theXyceParallel Electronic Simulator will be maintainable andextensible far into the future.Xyceis a parallel code in the most general sense of the phrase - a message passingparallel implementation - which allows it to run efficiently on the widest possible numberof computing platforms. These include serial, shared-memory and distributed-memoryparallel as well as heterogeneous platforms. Careful attention has been paid to thespecific nature of circuit-simulation problems to ensure that optimal parallel efficiencyis achieved as the number of processors grows.The development ofXyceprovides a platform for computational research and de-velopment aimed specifically at the needs of the Laboratory. WithXyce, Sandia hasan %22in-house%22 capability with which both new electrical (e.g., device model develop-ment) and algorithmic (e.g., faster time-integration methods, parallel solver algorithms)research and development can be performed. As a result,Xyceis a unique electricalsimulation capability, designed to meet the unique needs of the laboratory.4 XyceTMUsers' GuideAcknowledgementsThe authors would like to acknowledge the entire Sandia National Laboratories HPEMS(High Performance Electrical Modeling and Simulation) team, including Steve Wix, CarolynBogdan, Regina Schells, Ken Marx, Steve Brandon and Bill Ballard, for their support onthis project. We also appreciate very much the work of Jim Emery, Becky Arnold and MikeWilliamson for the help in reviewing this document.Lastly, a very special thanks to Hue Lai for typesetting this document with LATEX.TrademarksThe information herein is subject to change without notice.Copyrightc 2002-2003 Sandia Corporation. All rights reserved.XyceTMElectronic Simulator andXyceTMtrademarks of Sandia Corporation.Orcad, Orcad Capture, PSpice and Probe are registered trademarks of Cadence DesignSystems, Inc.Silicon Graphics, the Silicon Graphics logo and IRIX are registered trademarks of SiliconGraphics, Inc.Microsoft, Windows and Windows 2000 are registered trademark of Microsoft Corporation.Solaris and UltraSPARC are registered trademarks of Sun Microsystems Corporation.Medici, DaVinci and Taurus are registered trademarks of Synopsys Corporation.HP and Alpha are registered trademarks of Hewlett-Packard company.Amtec and TecPlot are trademarks of Amtec Engineering, Inc.Xyce's expression library is based on that inside Spice 3F5 developed by the EECS De-partment at the University of California.All other trademarks are property of their respective owners.ContactsBug Reportshttp://tvrusso.sandia.gov/bugzillaEmailxyce-support%40sandia.govWorld Wide Webhttp://www.cs.sandia.gov/xyce5 XyceTMUsers' GuideThis page is left intentionally blank6

Abstract not provided.

We apply density functional theory (DFT) and the DFT+U technique to study the adsorption of transition metal porphine molecules on atomistically flat Au(111) surfaces. DFT calculations using the Perdew?Burke?Ernzerhof exchange correlation functional correctly predict the palladium porphine (PdP) low-spin ground state. PdP is found to adsorb preferentially on gold in a flat geometry, not in an edgewise geometry, in qualitative agreement with experiments on substituted porphyrins. It exhibits no covalent bonding to Au(111), and the binding energy is a small fraction of an electronvolt. The DFT+U technique, parametrized to B3LYP-predicted spin state ordering of the Mn d-electrons, is found to be crucial for reproducing the correct magnetic moment and geometry of the isolated manganese porphine (MnP) molecule. Adsorption of Mn(II)P on Au(111) substantially alters the Mn ion spin state. Its interaction with the gold substrate is stronger and more site-specific than that of PdP. The binding can be partially reversed by applying an electric potential, which leads to significant changes in the electronic and magnetic properties of adsorbed MnP and 0.1 {angstrom} changes in the Mn-nitrogen distances within the porphine macrocycle. We conjecture that this DFT+U approach may be a useful general method for modeling first-row transition metal ion complexes in a condensed-matter setting.

Abstract not provided.

Abstract not provided.

This paper is about making reversible logic a reality for supercomputing. Reversible logic offers a way to exceed certain basic limits on the performance of computers, yet a powerful case will have to be made to justify its substantial development expense. This paper explores the limits of current, irreversible logic for supercomputers, thus forming a threshold above which reversible logic is the only solution. Problems above this threshold are discussed, with the science and mitigation of global warming being discussed in detail. To further develop the idea of using reversible logic in supercomputing, a design for a 1 Zettaflops supercomputer as required for addressing global climate warming is presented. However, to create such a design requires deviations from the mainstream of both the software for climate simulation and research directions of reversible logic. These deviations provide direction on how to make reversible logic practical.

In contrast to traditional terascale simulations that have known, fixed data inputs, dynamic data-driven (DDD) applications are characterized by unknown data and informed by dynamic observations. DDD simulations give rise to inverse problems of determining unknown data from sparse observations. The main difficulty is that the optimality system is a boundary value problem in 4D space-time, even though the forward simulation is an initial value problem. We construct special-purpose parallel multigrid algorithms that exploit the spectral structure of the inverse operator. Experiments on problems of localizing airborne contaminant release from sparse observations in a regional atmospheric transport model demonstrate that 17-million-parameter inversion can be effected at a cost of just 18 forward simulations with high parallel efficiency. On 1024 Alphaserver EV68 processors, the turnaround time is just 29 minutes. Moreover, inverse problems with 135 million parameters - corresponding to 139 billion total space-time unknowns - are solved in less than 5 hours on the same number of processors. These results suggest that ultra-high resolution data-driven inversion can be carried out sufficiently rapidly for simulation-based 'real-time' hazard assessment.

Abstract not provided.

We address the problem of partitioning and dynamic load balancing on clusters with heterogeneous hardware resources. We propose DRUM, a model that encapsulates hardware resources and their interconnection topology. DRUM provides monitoring facilities for dynamic evaluation of communication, memory, and processing capabilities. Heterogeneity is quantified by merging the information from the monitors to produce a scalar number called 'power.' This power allows DRUM to be used easily by existing load-balancing procedures such as those in the Zoltan Toolkit while placing minimal burden on application programmers. We demonstrate the use of DRUM to guide load balancing in the adaptive solution of a Laplace equation on a heterogeneous cluster. We observed a significant reduction in execution time compared to traditional methods.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

The solution of the governing steady transport equations for momentum, heat and mass transfer in fluids undergoing non-equilibrium chemical reactions can be extremely challenging. The difficulties arise from both the complexity of the nonlinear solution behavior as well as the nonlinear, coupled, non-symmetric nature of the system of algebraic equations that results from spatial discretization of the PDEs. In this paper, we briefly review progress on developing a stabilized finite element (FE) capability for numerical solution of these challenging problems. The discussion considers the stabilized FE formulation for the low Mach number Navier-Stokes equations with heat and mass transport with non-equilibrium chemical reactions, and the solution methods necessary for detailed analysis of these complex systems. The solution algorithms include robust nonlinear and linear solution schemes, parameter continuation methods, and linear stability analysis techniques. Our discussion considers computational efficiency, scalability, and some implementation issues of the solution methods. Computational results are presented for a CFD benchmark problem as well as for a number of large-scale, 2D and 3D, engineering transport/reaction applications.

Abstract not provided.

As current experimental and simulation methods cannot determine the mobility of flat boundaries across the large misorientation phase space, we have developed a computational method for imposing an artificial driving force on boundaries. In a molecular dynamics simulation, this allows us to go beyond the inherent timescale restrictions of the technique and induce non-negligible motion in flat boundaries of arbitrary misorientation. For different series of symmetric boundaries, we find both expected and unexpected results. In general, mobility increases as the grain boundary plane deviates from (111), but high-coincidence and low-angle boundaries represent special cases. These results agree with and enrich experimental observations.

Abstract not provided.

Abstract not provided.

Abstract not provided.

While it had been known for a long time how to transform an asymmetric traveling salesman (ATS) problem on the complete graph with n vertices into a symmetric traveling salesman (STS) problem on an incomplete graph with 2n vertices, no method was available for using this correspondence to derive facets of the symmetric polytope from facets of the asymmetric polytope until the work of E. Balas and M. Fischetti in [Lifted cycle inequalities for the asymmetric traveling salesman problem, Mathematics of Operations Research 24 (2) (1999) 273-292] suggested an approach. The original Balas-Fischetti method uses a standard sequential lifting procedure for the computation of the coefficient of the edges that are missing in the incomplete STS graph, which is a difficult task when addressing classes of (as opposed to single) inequalities. In this paper we introduce a systematic procedure for accomplishing the lifting task. The procedure exploits the structure of the tight STS tours and organizes them into a suitable tree structure. The potential of the method is illustrated by deriving large new classes of facet-defining STS inequalities.

Abstract not provided.

Abstract not provided.

Combinatorial algorithms have long played a pivotal enabling role in many applications of parallel computing. Graph algorithms in particular arise in load balancing, scheduling, mapping and many other aspects of the parallelization of irregular applications. These are still active research areas, mostly due to evolving computational techniques and rapidly changing computational platforms. But the relationship between parallel computing and discrete algorithms is much richer than the mere use of graph algorithms to support the parallelization of traditional scientific computations. Important, emerging areas of science are fundamentally discrete, and they are increasingly reliant on the power of parallel computing. Examples include computational biology, scientific data mining, and network analysis. These applications are changing the relationship between discrete algorithms and parallel computing. In addition to their traditional role as enablers of high performance, combinatorial algorithms are now customers for parallel computing. New parallelization techniques for combinatorial algorithms need to be developed to support these nontraditional scientific approaches. This chapter will describe some of the many areas of intersection between discrete algorithms and parallel scientific computing. Due to space limitations, this chapter is not a comprehensive survey, but rather an introduction to a diverse set of techniques and applications with a particular emphasis on work presented at the Eleventh SIAM Conference on Parallel Processing for Scientific Computing. Some topics highly relevant to this chapter (e.g. load balancing) are addressed elsewhere in this book, and so we will not discuss them here.

Abstract not provided.

In this article we describe stress nets, a technique for exploring 2D tensor fields. Our method allows a user to examine simultaneously the tensors eigenvectors (both major and minor) as well as scalar-valued tensor invariants. By avoiding noise-advection techniques, we are able to display both principal directions of the tensor field as well as the derived scalars without cluttering the display. We present a CPU-only implementation of stress nets as well as a hybrid CPU/GPU approach and discuss the relative strengths and weaknesses of each. Stress nets have been used as part of an investigation into crack propagation. They were used to display the directions of maximum shear in a slab of material under tension as well as the magnitude of the shear forces acting on each point. Our methods allowed users to find new features in the data that were not visible on standard plots of tensor invariants. These features disagree with commonly accepted analytical crack propagation solutions and have sparked renewed investigation. Though developed for a materials mechanics problem, our method applies equally well to any 2D tensor field having unique characteristic directions.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Empirical studies suggest that consumption is more sensitive to current income than suggested under the permanent income hypothesis, which raises questions regarding expectations for future income, risk aversion, and the role of economic confidence measures. This report surveys a body of fundamental economic literature as well as burgeoning computational modeling methods to support efforts to better anticipate cascading economic responses to terrorist threats and attacks. This is a three part survey to support the incorporation of models of economic confidence into agent-based microeconomic simulations. We first review broad underlying economic principles related to this topic. We then review the economic principle of confidence and related empirical studies. Finally, we provide a brief survey of efforts and publications related to agent-based economic simulation.

Simulations within density functional theory (DFT) are a common component of research into the physics of materials. With the broad success of DFT, it is easily forgotten that computational DFT methods invariably do not directly represent simulated properties, but require careful construction of models that are computable approximations to a physical property. Perhaps foremost among these computational considerations is the routine use of the supercell approximation to construct finite models to represent infinite systems. Pitfalls in using supercells (k-space sampling, boundary conditions, cell sizes) are often underappreciated. We present examples (e.g. vacancy defects) that exhibit a surprising or significant dependence on supercells, and describe workable solutions. We describe procedures needed to construct meaningful models for simulations of real material systems, focusing on k-space and cell size issues.

Abstract not provided.

We propose a new class of Discontinuous Galerkin (DG) methods based on variational multiscale ideas. Our approach begins with an additive decomposition of the discontinuous finite element space into continuous (coarse) and discontinuous (fine) components. Variational multiscale analysis is used to define an interscale transfer operator that associates coarse and fine scale functions. Composition of this operator with a donor DG method yields a new formulation that combines the advantages of DG methods with the attractive and more efficient computational structure of a continuous Galerkin method. The new class of DG methods is illustrated for a scalar advection-diffusion problem.

This paper analyzes the accuracy of the shift-invert Lanczos iteration for computing eigenpairs of the symmetric definite generalized eigenvalue problem. We provide bounds for the accuracy of the eigenpairs produced by shift-invert Lanczos given a residual reduction. We discuss the implications of our analysis for practical shift-invert Lanczos iterations. When the generalized eigenvalue problem arises from a conforming finite element method, we also comment on the uniform accuracy of bounds (independent of the mesh size h).

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

We have found that developing a computational framework for reconstructing error control codes for engineered data and ultimately for deciphering genetic regulatory coding sequences is a challenging and uncharted area that will require advances in computational technology for exact solutions. Although exact solutions are desired, computational approaches that yield plausible solutions would be considered sufficient as a proof of concept to the feasibility of reverse engineering error control codes and the possibility of developing a quantitative model for understanding and engineering genetic regulation. Such evidence would help move the idea of reconstructing error control codes for engineered and biological systems from the high risk high payoff realm into the highly probable high payoff domain. Additionally this work will impact biological sensor development and the ability to model and ultimately develop defense mechanisms against bioagents that can be engineered to cause catastrophic damage. Understanding how biological organisms are able to communicate their genetic message efficiently in the presence of noise can improve our current communication protocols, a continuing research interest. Towards this end, project goals include: (1) Develop parameter estimation methods for n for block codes and for n, k, and m for convolutional codes. Use methods to determine error control (EC) code parameters for gene regulatory sequence. (2) Develop an evolutionary computing computational framework for near-optimal solutions to the algebraic code reconstruction problem. Method will be tested on engineered and biological sequences.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Supercomputer architects strive to maximize the performance of scientific applications. Unfortunately, the large, unwieldy nature of most scientific applications has lead to the creation of artificial benchmarks, such as SPEC-FP, for architecture research. Given the impact that these benchmarks have on architecture research, this paper seeks an understanding of how they relate to real-world applications within the Department of Energy. Since the memory system has been found to be a particularly key issue for many applications, the focus of the paper is on the relationship between how the SPEC-FP benchmarks and DOE applications use the memory system. The results indicate that while the SPEC-FP suite is a well balanced suite, supercomputing applications typically demand more from the memory system and must perform more 'other work' (in the form of integer computations) along with the floating point operations. The SPEC-FP suite generally demonstrates slightly more temporal locality leading to somewhat lower bandwidth demands. The most striking result is the cumulative difference between the benchmarks and the applications in terms of the requirements to sustain the floating-point operation rate: the DOE applications require significantly more data from main memory (not cache) per FLOP and dramatically more integer instructions per FLOP.

Abstract not provided.

This report is a white paper summarizing the literature and different approaches to the problem of calibrating computer model parameters in the face of model uncertainty. Model calibration is often formulated as finding the parameters that minimize the squared difference between the model-computed data (the predicted data) and the actual experimental data. This approach does not allow for explicit treatment of uncertainty or error in the model itself: the model is considered the %22true%22 deterministic representation of reality. While this approach does have utility, it is far from an accurate mathematical treatment of the true model calibration problem in which both the computed data and experimental data have error bars. This year, we examined methods to perform calibration accounting for the error in both the computer model and the data, as well as improving our understanding of its meaning for model predictability. We call this approach Calibration under Uncertainty (CUU). This talk presents our current thinking on CUU. We outline some current approaches in the literature, and discuss the Bayesian approach to CUU in detail.

We compare inexact Newton and coordinate descent optimization methods for improving the quality of a mesh by repositioning the vertices, where the overall quality is measured by the harmonic mean of the mean-ratio metric. The effects of problem size, element size heterogeneity, and various vertex displacement schemes on the performance of these algorithms are assessed for a series of tetrahedral meshes.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

This report describes an integrated approach for designing communication, sensing, and control systems for mobile distributed systems. Graph theoretic methods are used to analyze the input/output reachability and structural controllability and observability of a decentralized system. Embedded in each network node, this analysis will automatically reconfigure an ad hoc communication network for the sensing and control task at hand. The graph analysis can also be used to create the optimal communication flow control based upon the spatial distribution of the network nodes. Edge coloring algorithms tell us that the minimum number of time slots in a planar network is equal to either the maximum number of adjacent nodes (or degree) of the undirected graph plus some small number. Therefore, the more spread out that the nodes are, the fewer number of time slots are needed for communication, and the smaller the latency between nodes. In a coupled system, this results in a more responsive sensor network and control system. Network protocols are developed to propagate this information, and distributed algorithms are developed to automatically adjust the number of time slots available for communication. These protocols and algorithms must be extremely efficient and only updated as network nodes move. In addition, queuing theory is used to analyze the delay characteristics of Carrier Sense Multiple Access (CSMA) networks. This report documents the analysis, simulation, and implementation of these algorithms performed under this Laboratory Directed Research and Development (LDRD) effort.

This report describes a system level study on the use of a swarm of sea gliders to detect, confirm and kill littoral submarine threats. The report begins with a description of the problem and derives the probability of detecting a constant speed threat without networking. It was concluded that glider motion does little to improve this probability unless the speed of a glider is greater than the speed of the threat. Therefore, before detection, the optimal character for a swarm of gliders is simply to lie in wait for the detection of a threat. The report proceeds by describing the effect of noise on the localization of a threat once initial detection is achieved. This noise is estimated as a function of threat location relative to the glider and is temporally reduced through the use of an information or Kalman filtering. In the next section, the swarm probability of confirming and killing a threat is formulated. Results are compared to a collection of stationary sensors. These results show that once a glider has the ability to move faster than the threat, the performance of the swarm is equal to the performance of a stationary swarm of gliders with confirmation and kill ranges equal to detection range. Moreover, at glider speeds greater than the speed of the threat, swarm performance becomes a weak function of speed. At these speeds swarm performance is dominated by detection range. Therefore, to future enhance swarm performance or to reduce the number of gliders required for a given performance, detection range must be increased. Communications latency is also examined. It was found that relatively large communication delays did little to change swarm performance. Thus gliders may come to the surface and use SATCOMS to effectively communicate in this application.

Complex simulations (in particular, those involving multiple coupled physics) cannot be understood solely using geometry-based visualizations. Such visualizations are necessary in interpreting results and gaining insights into kinematics, however they are insufficient when striving to understand why or how something happened, or when investigating a simulation's dynamic evolution. For multiphysics simulations (e.g. those including solid dynamics with thermal conduction, magnetohydrodynamics, and radiation hydrodynamics) complex interactions between physics and material properties take place within the code which must be investigated in other ways. Drawing on the extensive previous work in view coordination, brushing and linking techniques, and powerful visualization libraries, we have developed Prism, an application targeted for a specific analytic need at Sandia National Laboratories. This multiview scientific visualization tool tightly integrates geometric and phase space views of simulation data and material models. Working closely with analysts, we have developed this production tool to promote understanding of complex, multiphysics simulations. We discuss the current implementation of Prism, along with specific examples of results obtained by using the tool.

Abstract not provided.

Abstract not provided.

We present an exchange-correlation functional that enables an accurate treatment of systems with electronic surfaces. The functional is developed within the subsystem functional paradigm [1], combining the local density approximation for interior regions with a new functional designed for surface regions. It is validated for a variety of materials by calculations of: (i) properties where surface effects exist, and (ii) established bulk properties. Good and coherent results are obtained, indicating that this functional may serve well as universal first choice for solid state systems. The good performance of this first subsystem functional also suggests that yet improved functionals can be constructed by this approach.

We develop a specialized treatment of electronic surface regions which, via the subsystem functional approach [1], can be used in functionals for self-consistent density-functional theory (DFT). Approximations for both exchange and correlation energies are derived for an electronic surface. An interpolation index is used to combine this surface-specific functional with a functional for interior regions. When the local density approximation (LDA) is used for the interior region, the end result is a straightforward density-gradient dependent functional that shows promising results. Further improvement of the treatment of the interior region by the use of a local gradient expansion approximation is also discussed.

Abstract not provided.

Abstract not provided.

Abstract not provided.

ALEGRA is an arbitrary Lagrangian-Eulerian finite element code that emphasizes large distortion and shock propagation in inviscid fluids and solids. This document describes user options for modeling resistive magnetohydrodynamics, thermal conduction, and radiation transport effects, and two material temperature physics.

To establish mechanical properties and failure criteria of silicon carbide (SiC-N) ceramics, a series of quasi-static compression tests has been completed using a high-pressure vessel and a unique sample alignment jig. This report summarizes the test methods, set-up, relevant observations, and results from the constitutive experimental efforts. Results from the uniaxial and triaxial compression tests established the failure threshold for the SiC-N ceramics in terms of stress invariants (I{sub 1} and J{sub 2}) over the range 1246 < I{sub 1} < 2405. In this range, results are fitted to the following limit function (Fossum and Brannon, 2004) {radical}J{sub 2}(MPa) = a{sub 1} - a{sub 3}e -a{sub 2}(I{sub 1}/3) + a{sub 4} I{sub 1}/3, where a{sub 1} = 10181 MPa, a{sub 2} = 4.2 x 10{sup -4}, a{sub 3} = 11372 MPa, and a{sub 4} = 1.046. Combining these quasistatic triaxial compression strength measurements with existing data at higher pressures naturally results in different values for the least-squares fit to this function, appropriate over a broader pressure range. These triaxial compression tests are significant because they constitute the first successful measurements of SiC-N compressive strength under quasistatic conditions. Having an unconfined compressive strength of {approx}3800 MPa, SiC-N has been heretofore tested only under dynamic conditions to achieve a sufficiently large load to induce failure. Obtaining reliable quasi-static strength measurements has required design of a special alignment jig and load-spreader assembly, as well as redundant gages to ensure alignment. When considered in combination with existing dynamic strength measurements, these data significantly advance the characterization of pressure-dependence of strength, which is important for penetration simulations where failed regions are often at lower pressures than intact regions.

This report summarizes the research and development performed from October 2002 to September 2004 at Sandia National Laboratories under the Laboratory-Directed Research and Development (LDRD) project ''Massively-Parallel Linear Programming''. We developed a linear programming (LP) solver designed to use a large number of processors. LP is the optimization of a linear objective function subject to linear constraints. Companies and universities have expended huge efforts over decades to produce fast, stable serial LP solvers. Previous parallel codes run on shared-memory systems and have little or no distribution of the constraint matrix. We have seen no reports of general LP solver runs on large numbers of processors. Our parallel LP code is based on an efficient serial implementation of Mehrotra's interior-point predictor-corrector algorithm (PCx). The computational core of this algorithm is the assembly and solution of a sparse linear system. We have substantially rewritten the PCx code and based it on Trilinos, the parallel linear algebra library developed at Sandia. Our interior-point method can use either direct or iterative solvers for the linear system. To achieve a good parallel data distribution of the constraint matrix, we use a (pre-release) version of a hypergraph partitioner from the Zoltan partitioning library. We describe the design and implementation of our new LP solver called parPCx and give preliminary computational results. We summarize a number of issues related to efficient parallel solution of LPs with interior-point methods including data distribution, numerical stability, and solving the core linear system using both direct and iterative methods. We describe a number of applications of LP specific to US Department of Energy mission areas and we summarize our efforts to integrate parPCx (and parallel LP solvers in general) into Sandia's massively-parallel integer programming solver PICO (Parallel Interger and Combinatorial Optimizer). We conclude with directions for long-term future algorithmic research and for near-term development that could improve the performance of parPCx.

Abstract not provided.

Abstract not provided.

Abstract not provided.

This SAND report provides the technical progress through October 2004 of the Sandia-led project, %22Carbon Sequestration in Synechococcus Sp.: From Molecular Machines to Hierarchical Modeling,%22 funded by the DOE Office of Science Genomes to Life Program. Understanding, predicting, and perhaps manipulating carbon fixation in the oceans has long been a major focus of biological oceanography and has more recently been of interest to a broader audience of scientists and policy makers. It is clear that the oceanic sinks and sources of CO2 are important terms in the global environmental response to anthropogenic atmospheric inputs of CO2 and that oceanic microorganisms play a key role in this response. However, the relationship between this global phenomenon and the biochemical mechanisms of carbon fixation in these microorganisms is poorly understood. In this project, we will investigate the carbon sequestration behavior of Synechococcus Sp., an abundant marine cyanobacteria known to be important to environmental responses to carbon dioxide levels, through experimental and computational methods. This project is a combined experimental and computational effort with emphasis on developing and applying new computational tools and methods. Our experimental effort will provide the biology and data to drive the computational efforts and include significant investment in developing new experimental methods for uncovering protein partners, characterizing protein complexes, identifying new binding domains. We will also develop and apply new data measurement and statistical methods for analyzing microarray experiments. Computational tools will be essential to our efforts to discover and characterize the function of the molecular machines of Synechococcus. To this end, molecular simulation methods will be coupled with knowledge discovery from diverse biological data sets for high-throughput discovery and characterization of protein-protein complexes. In addition, we will develop a set of novel capabilities for inference of regulatory pathways in microbial genomes across multiple sources of information through the integration of computational and experimental technologies. These capabilities will be applied to Synechococcus regulatory pathways to characterize their interaction map and identify component proteins in these - 4 - pathways. We will also investigate methods for combining experimental and computational results with visualization and natural language tools to accelerate discovery of regulatory pathways. The ultimate goal of this effort is develop and apply new experimental and computational methods needed to generate a new level of understanding of how the Synechococcus genome affects carbon fixation at the global scale. Anticipated experimental and computational methods will provide ever-increasing insight about the individual elements and steps in the carbon fixation process, however relating an organism's genome to its cellular response in the presence of varying environments will require systems biology approaches. Thus a primary goal for this effort is to integrate the genomic data generated from experiments and lower level simulations with data from the existing body of literature into a whole cell model. We plan to accomplish this by developing and applying a set of tools for capturing the carbon fixation behavior of complex of Synechococcus at different levels of resolution. Finally, the explosion of data being produced by high-throughput experiments requires data analysis and models which are more computationally complex, more heterogeneous, and require coupling to ever increasing amounts of experimentally obtained data in varying formats. These challenges are unprecedented in high performance scientific computing and necessitate the development of a companion computational infrastructure to support this effort. More information about this project, including a copy of the original proposal, can be found at www.genomes-to-life.org Acknowledgment We want to gratefully acknowledge the contributions of the GTL Project Team as follows: Grant S. Heffelfinger1*, Anthony Martino2, Andrey Gorin3, Ying Xu10,3, Mark D. Rintoul1, Al Geist3, Matthew Ennis1, Hashimi Al-Hashimi8, Nikita Arnold3, Andrei Borziak3, Bianca Brahamsha6, Andrea Belgrano12, Praveen Chandramohan3, Xin Chen9, Pan Chongle3, Paul Crozier1, PguongAn Dam10, George S. Davidson1, Robert Day3, Jean Loup Faulon2, Damian Gessler12, Arlene Gonzalez2, David Haaland1, William Hart1, Victor Havin3, Tao Jiang9, Howland Jones1, David Jung3, Ramya Krishnamurthy3, Yooli Light2, Shawn Martin1, Rajesh Munavalli3, Vijaya Natarajan3, Victor Olman10, Frank Olken4, Brian Palenik6, Byung Park3, Steven Plimpton1, Diana Roe2, Nagiza Samatova3, Arie Shoshani4, Michael Sinclair1, Alex Slepoy1, Shawn Stevens8, Chris Stork1, Charlie Strauss5, Zhengchang Su10, Edward Thomas1, Jerilyn A. Timlin1, Xiufeng Wan11, HongWei Wu10, Dong Xu11, Gong-Xin Yu3, Grover Yip8, Zhaoduo Zhang2, Erik Zuiderweg8 *Author to whom correspondence should be addressed (gsheffe%40sandia.gov) 1. Sandia National Laboratories, Albuquerque, NM 2. Sandia National Laboratories, Livermore, CA 3. Oak Ridge National Laboratory, Oak Ridge, TN 4. Lawrence Berkeley National Laboratory, Berkeley, CA 5. Los Alamos National Laboratory, Los Alamos, NM 6. University of California, San Diego 7. University of Illinois, Urbana/Champaign 8. University of Michigan, Ann Arbor 9. University of California, Riverside 10. University of Georgia, Athens 11. University of Missouri, Columbia 12. National Center for Genome Resources, Santa Fe, NM Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000.

Abstract not provided.

Local topological modification is widely used to improve mesh quality after automatic generation of tetrahedral and quadrilateral meshes. These same techniques are also used to support adaptive refinement of these meshes. In contrast, few methods are known for locally modifying the topology of hexahedral meshes. Most efforts to do this have been based on fixed transition templates or global refinement. In contrast, a dual-based 'pillowing' method has been used which, while local, is still quite restricted in its application, and is typically applied in a template-based fashion. In this presentation, I will describe the generalization of a dual-based approach to the local topological modification of hex meshes and its application to clean up hexahedral meshes. A set of three operations for locally modifying hex mesh topology has been shown to reproduce the so-called 'flipping' operations described by Bern et. al as well as other commonly-used refinement templates. I will describe the implementation of these operators and their application to real meshes. Challenging aspects of this work have included visualization of a hex mesh and its dual (especially for poor-quality meshes); the incremental modification of both the primal (i.e. the mesh) and the dual simultaneously; and the interactive steering of these operations with the goal of improving hex meshes which would otherwise have unacceptable quality. These aspects will be discussed in the context of improving hex meshes generated by curve contraction-based whisker weaving. Application of these techniques for improving other hexahedral mesh types, for example those resulting from tetrahedral subdivision, will also be discussed.

Abstract not provided.

We design a density-functional-theory (DFT) exchange-correlation functional that enables an accurate treatment of systems with electronic surfaces. Surface-specific approximations for both exchange and correlation energies are developed. A subsystem functional approach is then used: an interpolation index combines the surface functional with a functional for interior regions. When the local density approximation is used in the interior, the result is a straightforward functional for use in self-consistent DFT. The functional is validated for two metals (Al, Pt) and one semiconductor (Si) by calculations of (i) established bulk properties (lattice constants and bulk moduli) and (ii) a property where surface effects exist (the vacancy formation energy). Good and coherent results indicate that this functional may serve well as a universal first choice for solid-state systems and that yet improved functionals can be constructed by this approach.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Spreading of bacteria in a highly advective, disordered environment is examined. Predictions of super-diffusive spreading for a simplified reaction-diffusion equation are tested. Concentration profiles display anomalous growth and super-diffusive spreading. A perturbation analysis yields a crossover time between diffusive and super-diffusive behavior. The time's dependence on the convection velocity and disorder is tested. Like the simplified equation, the full linear reaction-diffusion equation displays super-diffusive spreading perpendicular to the convection. However, for mean positive growth rates the full nonlinear reaction-diffusion equation produces symmetric spreading with a Fisher wavefront, whereas net negative growth rates cause an asymmetry, with a slower wavefront velocity perpendicular to the convection.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

We consider the accuracy of predictions made by integer programming (IP) models of sensor placement for water security applications. We have recently shown that IP models can be used to find optimal sensor placements for a variety of different performance criteria (e.g. minimize health impacts and minimize time to detection). However, these models make a variety of simplifying assumptions that might bias the final solution. We show that our IP modeling assumptions are similar to models developed for other sensor placement methodologies, and thus IP models should give similar predictions. However, this discussion highlights that there are significant differences in how temporal effects are modeled for sensor placement. We describe how these modeling assumptions can impact sensor placements.

Abstract not provided.

In recent years, several integer programming models have been proposed to place sensors in municipal water networks in order to detect intentional or accidental contamination. Although these initial models assumed that it is equally costly to place a sensor at any place in the network, there clearly are practical cost constraints that would impact a sensor placement decision. Such constraints include not only labor costs but also the general accessibility of a sensor placement location. In this paper, we extend our integer program to explicitly model the cost of sensor placement. We partition network locations into groups of varying placement cost, and we consider the public health impacts of contamination events under varying budget constraints. Thus our models permit cost/benefit analyses for differing sensor placement designs. As a control for our optimization experiments, we compare the set of sensor locations selected by the optimization models to a set of manually-selected sensor locations.

Abstract not provided.

Abstract not provided.

Abstract not provided.

This SAND report provides the technical progress through June 2004 of the Sandia-led project, ''Carbon Sequestration in Synechococcus Sp.: From Molecular Machines to Hierarchical Modeling'', funded by the DOE Office of Science Genomes to Life Program. Understanding, predicting, and perhaps manipulating carbon fixation in the oceans has long been a major focus of biological oceanography and has more recently been of interest to a broader audience of scientists and policy makers. It is clear that the oceanic sinks and sources of CO{sub 2} are important terms in the global environmental response to anthropogenic atmospheric inputs of CO{sub 2} and that oceanic microorganisms play a key role in this response. However, the relationship between this global phenomenon and the biochemical mechanisms of carbon fixation in these microorganisms is poorly understood. In this project, we will investigate the carbon sequestration behavior of Synechococcus Sp., an abundant marine cyanobacteria known to be important to environmental responses to carbon dioxide levels, through experimental and computational methods. This project is a combined experimental and computational effort with emphasis on developing and applying new computational tools and methods. Our experimental effort will provide the biology and data to drive the computational efforts and include significant investment in developing new experimental methods for uncovering protein partners, characterizing protein complexes, identifying new binding domains. We will also develop and apply new data measurement and statistical methods for analyzing microarray experiments. Computational tools will be essential to our efforts to discover and characterize the function of the molecular machines of Synechococcus. To this end, molecular simulation methods will be coupled with knowledge discovery from diverse biological data sets for high-throughput discovery and characterization of protein-protein complexes. In addition, we will develop a set of novel capabilities for inference of regulatory pathways in microbial genomes across multiple sources of information through the integration of computational and experimental technologies. These capabilities will be applied to Synechococcus regulatory pathways to characterize their interaction map and identify component proteins in these pathways. We will also investigate methods for combining experimental and computational results with visualization and natural language tools to accelerate discovery of regulatory pathways. The ultimate goal of this effort is develop and apply new experimental and computational methods needed to generate a new level of understanding of how the Synechococcus genome affects carbon fixation at the global scale. Anticipated experimental and computational methods will provide ever-increasing insight about the individual elements and steps in the carbon fixation process, however relating an organism's genome to its cellular response in the presence of varying environments will require systems biology approaches. Thus a primary goal for this effort is to integrate the genomic data generated from experiments and lower level simulations with data from the existing body of literature into a whole cell model. We plan to accomplish this by developing and applying a set of tools for capturing the carbon fixation behavior of complex of Synechococcus at different levels of resolution. Finally, the explosion of data being produced by high-throughput experiments requires data analysis and models which are more computationally complex, more heterogeneous, and require coupling to ever increasing amounts of experimentally obtained data in varying formats. These challenges are unprecedented in high performance scientific computing and necessitate the development of a companion computational infrastructure to support this effort.

ALEGRA is an arbitrary Lagrangian-Eulerian finite element code that emphasizes large distortion and shock propagation in inviscid fluids and solids. This document describes user options for modeling resistive magnetohydrodynamic, thermal conduction, and radiation emission effects.

We have developed a novel approach to modeling the transmembrane spanning helical bundles of integral membrane proteins using only a sparse set of distance constraints, such as those derived from MS3-D, dipolar-EPR and FRET experiments. Algorithms have been written for searching the conformational space of membrane protein folds matching the set of distance constraints, which provides initial structures for local conformational searches. Local conformation search is achieved by optimizing these candidates against a custom penalty function that incorporates both measures derived from statistical analysis of solved membrane protein structures and distance constraints obtained from experiments. This results in refined helical bundles to which the interhelical loops and amino acid side-chains are added. Using a set of only 27 distance constraints extracted from the literature, our methods successfully recover the structure of dark-adapted rhodopsin to within 3.2 {angstrom} of the crystal structure.

ALEGRA is an arbitrary Lagrangian-Eulerian multi-material finite element code used for modeling solid dynamics problems involving large distortion and shock propagation. This document describes the basic user input language and instructions for using the software.

Sensitivity analysis is critically important to numerous analysis algorithms, including large scale optimization, uncertainty quantification,reduced order modeling, and error estimation. Our research focused on developing tools, algorithms and standard interfaces to facilitate the implementation of sensitivity type analysis into existing code and equally important, the work was focused on ways to increase the visibility of sensitivity analysis. We attempt to accomplish the first objective through the development of hybrid automatic differentiation tools, standard linear algebra interfaces for numerical algorithms, time domain decomposition algorithms and two level Newton methods. We attempt to accomplish the second goal by presenting the results of several case studies in which direct sensitivities and adjoint methods have been effectively applied, in addition to an investigation of h-p adaptivity using adjoint based a posteriori error estimation. A mathematical overview is provided of direct sensitivities and adjoint methods for both steady state and transient simulations. Two case studies are presented to demonstrate the utility of these methods. A direct sensitivity method is implemented to solve a source inversion problem for steady state internal flows subject to convection diffusion. Real time performance is achieved using novel decomposition into offline and online calculations. Adjoint methods are used to reconstruct initial conditions of a contamination event in an external flow. We demonstrate an adjoint based transient solution. In addition, we investigated time domain decomposition algorithms in an attempt to improve the efficiency of transient simulations. Because derivative calculations are at the root of sensitivity calculations, we have developed hybrid automatic differentiation methods and implemented this approach for shape optimization for gas dynamics using the Euler equations. The hybrid automatic differentiation method was applied to a first order approximation of the Euler equations and used as a preconditioner. In comparison to other methods, the AD preconditioner showed better convergence behavior. Our ultimate target is to perform shape optimization and hp adaptivity using adjoint formulations in the Premo compressible fluid flow simulator. A mathematical formulation for mixed-level simulation algorithms has been developed where different physics interact at potentially different spatial resolutions in a single domain. To minimize the implementation effort, explicit solution methods can be considered, however, implicit methods are preferred if computational efficiency is of high priority. We present the use of a partial elimination nonlinear solver technique to solve these mixed level problems and show how these formulation are closely coupled to intrusive optimization approaches and sensitivity analyses. Production codes are typically not designed for sensitivity analysis or large scale optimization. The implementation of our optimization libraries into multiple production simulation codes in which each code has their own linear algebra interface becomes an intractable problem. In an attempt to streamline this task, we have developed a standard interface between the numerical algorithm (such as optimization) and the underlying linear algebra. These interfaces (TSFCore and TSFCoreNonlin) have been adopted by the Trilinos framework and the goal is to promote the use of these interfaces especially with new developments. Finally, an adjoint based a posteriori error estimator has been developed for discontinuous Galerkin discretization of Poisson's equation. The goal is to investigate other ways to leverage the adjoint calculations and we show how the convergence of the forward problem can be improved by adapting the grid using adjoint-based error estimates. Error estimation is usually conducted with continuous adjoints but if discrete adjoints are available it may be possible to reuse the discrete version for error estimation. We investigate the advantages and disadvantages of continuous and discrete adjoints through a simple example.

The purpose of the Sandia National Laboratories (SNL) Advanced Simulation and Computing (ASC) Software Quality Plan is to clearly identify the practices that are the basis for continually improving the quality of ASC software products. Quality is defined in DOE/AL Quality Criteria (QC-1) as conformance to customer requirements and expectations. This quality plan defines the ASC program software quality practices and provides mappings of these practices to the SNL Corporate Process Requirements (CPR 1.3.2 and CPR 1.3.6) and the Department of Energy (DOE) document, ASCI Software Quality Engineering: Goals, Principles, and Guidelines (GP&G). This quality plan identifies ASC management and software project teams' responsibilities for cost-effective software engineering quality practices. The SNL ASC Software Quality Plan establishes the signatories commitment to improving software products by applying cost-effective software engineering quality practices. This document explains the project teams opportunities for tailoring and implementing the practices; enumerates the practices that compose the development of SNL ASC's software products; and includes a sample assessment checklist that was developed based upon the practices in this document.

We summarize the results of a project to develop evolutionary computing methods for the design of behaviors of embodied agents in the form of autonomous vehicles. We conceived and implemented a strategy called graduated embodiment. This method allows high-level behavior algorithms to be developed using genetic programming methods in a low-fidelity, disembodied modeling environment for migration to high-fidelity, complex embodied applications. This project applies our methods to the problem domain of robot navigation using adaptive waypoints, which allow navigation behaviors to be ported among autonomous mobile robots with different degrees of embodiment, using incremental adaptation and staged optimization. Our approach to biomimetic behavior engineering is a hybrid of human design and artificial evolution, with the application of evolutionary computing in stages to preserve building blocks and limit search space. The methods and tools developed for this project are directly applicable to other agent-based modeling needs, including climate-related conflict analysis, multiplayer training methods, and market-based hypothesis evaluation.

Order-of-accuracy verification is necessary to ensure that software correctly solves a given set of equations. One method to verify the order of accuracy of a code is the method of manufactured solutions. In this study, a manufactured solution has been derived and implemented that allows verification of not only the Euler, Navier-Stokes, and Reynolds-Averaged Navier-Stokes (RANS) equation sets, but also some of their associated boundary conditions (BC's): slip, no-slip (adiabatic and isothermal), and outflow (subsonic, supersonic, and mixed). Order-of-accuracy verification has been performed for the Euler and Navier-Stokes equations and these BC's in a compressible computational fluid dynamics code. All of the results shown are on skewed, non-uniform meshes. RANS results will be presented in a future paper. The observed order of accuracy was lower than the expected order of accuracy in two cases. One of these cases resulted in the identification and correction of a coding mistake in the CHAD gradient correction that was reducing the observed order of accuracy. This mistake would have been undetectable on a Cartesian mesh. During the search for the CHAD gradient correction problem, an unrelated coding mistake was found and corrected. The other case in which the observed order of accuracy was less than expected was a test of the slip BC; although no specific coding or formulation mistakes have yet been identified. After the correction of the identified coding mistakes, all of the aforementioned equation sets and BC's demonstrated the expected (or at least acceptable) order of accuracy except the slip condition.

Abstract not provided.

Abstract not provided.

Modal analysis of three-dimensional structures frequently involves finite element discretizations with millions of unknowns and requires computing hundreds or thousands of eigenpairs. In this presentation we review methods based on domain decomposition for such eigenspace computations in structural dynamics. We distinguish approaches that solve the eigenproblem algebraically (with minimal connections to the underlying partial differential equation) from approaches that tightly couple the eigensolver with the partial differential equation.

An alternative theory of solid mechanics, known as the peridynamic theory, formulates problems in terms of integral equations rather than partial differential equations. This theory assumes that particles in a continuum interact with each other across a finite distance, as in molecular dynamics. Damage is incorporated in the theory at the level of these two-particle interactions, so localization and fracture occur as a natural outgrowth of the equation of motion and constitutive models. A numerical method for solving dynamic problems within the peridynamic theory is described. Accuracy and numerical stability are discussed. Examples illustrate the properties of the method for modeling brittle dynamic crack growth.

Abstract not provided.

A classification system is developed to identify driving situations from labeled examples of previous occurrences. The purpose of the classifier is to provide physical context to a separate system that mitigates unnecessary distractions, allowing the driver to maintain focus during periods of high difficulty. While watching videos of driving, we asked different users to indicate their perceptions of the current situation. We then trained a classifier to emulate the human recognition of driving situations using the Sandia Cognitive Framework. In unstructured conditions, such as driving in urban areas and the German autobahn, the classifier was able to correctly predict human perceptions of driving situations over 95% of the time. This paper focuses on the learning algorithms used to train the driving-situation classifier. Future work will reduce the human efforts needed to train the system. © 2005 IEEE.

Abstract not provided.

IFPACK provides a suite of object-oriented algebraic preconditioners for the solution of preconditioned iterative solvers. IFPACK constructors expect the (distributed) real sparse matrix to be an Epetra RowMatrix object. IFPACK can be used to define point and block relaxation preconditioners, various flavors of incomplete factorizations for symmetric and non-symmetric matrices, and one-level additive Schwarz preconditioners with variable overlap. Exact LU factorizations of the local submatrix can be accessed through the AMESOS packages. IFPACK , as part of the Trilinos Solver Project, interacts well with other Trilinos packages. In particular, IFPACK objects can be used as preconditioners for AZTECOO, and as smoothers for ML. IFPACK is mainly written in C++, but only a limited subset of C++ features is used, in order to enhance portability.

We consider linear systems arising from the use of the finite element method for solving a certain class of linear elliptic problems. Our main result is that these linear systems, which are symmetric and positive semidefinite, are well approximated by symmetric diagonally dominant matrices. Our framework for defining matrix approximation is support theory. Significant graph theoretic work has already been developed in the support framework for preconditioners in the diagonally dominant case, and in particular it is known that such systems can be solved with iterative methods in nearly linear time. Thus, our approximation result implies that these graph theoretic techniques can also solve a class of finite element problems in nearly linear time. We show that the quality of our approximation, which controls the number of iterations in the preconditioned iterative solver, depends primarily on a mesh quality measure but not on the problem size or shape of the domain.

Abstract not provided.

In large-scale parallel applications a graph coloring is often carried out to schedule computational tasks. In this paper, we describe a new distributed-memory algorithm for doing the coloring itself in parallel. The algorithm operates in an iterative fashion; in each round vertices are speculatively colored based on limited information, and then a set of incorrectly colored vertices, to be recolored in the next round, is identified. Parallel speedup is achieved in part by reducing the frequency of communication among processors. Experimental results on a PC cluster using up to 16 processors show that the algorithm is scalable. © Springer-Verlag Berlin Heidelberg 2005.