We present a model for optimizing the placement of sensors in municipal water networks to detect maliciously-injected contaminants. An optimal sensor configuration minimizes the expected fraction of the population at risk. We formulate this problem as an integer program, which can be solved with generally available IP solvers. We find optimal sensor placements for three real networks with synthetic risk and population data. Our experiments illustrate that this formulation can be solved relatively quickly, and that the predicted sensor configuration is relatively insensitive to uncertainties in the data used for prediction.
We describe COLIN, a Common Optimization Library INterface for C++. COLIN provides C++ template classes that define a generic interface for both optimization problems and optimization solvers. COLIN is specifically designed to facilitate the development of hybrid optimizers, for which one optimizer calls another to solve an optimization subproblem. We illustrate the capabilities of COLIN with an example of a memetic genetic programming solver.
In the LIGA process for manufacturing microcomponents, a polymer film is exposed to an x-ray beam passed through a gold pattern. This is followed by the development stage, in which a selective solvent is used to remove the exposed polymer, reproducing the gold pattern in the polymer film. Development is essentially polymer dissolution, a physical process which is not well understood. We have used coarse-grained molecular dynamics simulation to study the early stage of polymer dissolution. In each simulation a film of non-glassy polymer was brought into contact with a layer of solvent. The mutual penetration of the two phases was tracked as a function of time. Several film thicknesses and two different chain lengths were simulated. In all cases, the penetration process conformed to ideal Fickian diffusion. We did not see the formation of a gel layer or other non-ideal effects. Variations in the Fickian diffusivities appeared to be caused primarily by differences in the bulk polymer film density.
This project is being conducted by Sandia National Laboratories in support of the DARPA Augmented Cognition program. Work commenced in April of 2002. The objective for the DARPA program is to 'extend, by an order of magnitude or more, the information management capacity of the human-computer warfighter.' Initially, emphasis has been placed on detection of an operator's cognitive state so that systems may adapt accordingly (e.g., adjust information throughput to the operator in response to workload). Work conducted by Sandia focuses on development of technologies to infer an operator's ongoing cognitive processes, with specific emphasis on detecting discrepancies between machine state and an operator's ongoing interpretation of events.
Proposed for publication in the Special Issue of
Concurrency and Computation: Practice and Experience - The
High Performance Architectural Challenge: Mass Market Versus
Proprietary Components.
It has recently been shown that local values of the conventional exchange energy per particle cannot be described by an analytic expansion in the density variation. Yet, it is known that the total exchange-correlation (XC) energy per particle does not show any corresponding nonanalyticity. Indeed, the nonanalyticity is here shown to be an effect of the separation into conventional exchange and correlation. We construct an alternative separation in which the exchange part is made well behaved by screening its long-ranged contributions, and the correlation part is adjusted accordingly. This alternative separation is as valid as the conventional one, and introduces no new approximations to the total XC energy. We demonstrate functional development based on this approach by creating and deploying a local-density-approximation-type XC functional. Hence, this work includes both the theory and the practical calculations needed to provide a starting point for an alternative approach towards improved approximations of the total XC energy.
The U.S. Department of Energy recently announced the first five grants for the Genomes to Life (GTL) Program. The goal of this program is to ''achieve the most far-reaching of all biological goals: a fundamental, comprehensive, and systematic understanding of life.'' While more information about the program can be found at the GTL website (www.doegenomestolife.org), this paper provides an overview of one of the five GTL projects funded, ''Carbon Sequestration in Synechococcus Sp.: From Molecular Machines to Hierarchical Modeling.'' This project is a combined experimental and computational effort emphasizing developing, prototyping, and applying new computational tools and methods to elucidate the biochemical mechanisms of the carbon sequestration of Synechococcus Sp., an abundant marine cyanobacteria known to play an important role in the global carbon cycle. 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(2) are important terms in the global environmental response to anthropogenic atmospheric inputs of CO(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. The project includes five subprojects: an experimental investigation, three computational biology efforts, and a fifth which deals with addressing computational infrastructure challenges of relevance to this project and the Genomes to Life program as a whole. Our experimental effort is designed to provide biology and data to drive the computational efforts and includes 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. Our computational efforts include coupling molecular simulation methods with knowledge discovery from diverse biological data sets for high-throughput discovery and characterization of protein-protein complexes and developing 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. Furthermore, given that the ultimate goal of this effort is to develop a systems-level of understanding of how the Synechococcus genome affects carbon fixation at the global scale, we will develop and apply a set of tools for capturing the carbon fixation behavior of complex of Synechococcus at different levels of resolution. Finally, because 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, we have also established a companion computational infrastructure to support this effort as well as the Genomes to Life program as a whole.
Developers of computer codes, analysts who use the codes, and decision makers who rely on the results of the analyses face a critical question: How should confidence in modeling and simulation be critically assessed? Verification and validation (V&V) of computational simulations are the primary methods for building and quantifying this confidence. Briefly, verification is the assessment of the accuracy of the solution to a computational model. Validation is the assessment of the accuracy of a computational simulation by comparison with experimental data. In verification, the relationship of the simulation to the real world is not an issue. In validation, the relationship between computation and the real world, i.e., experimental data, is the issue.
RMPP (reliable message passing protocol) is a lightweight transport protocol designed for clusters that provides end-to-end flow control and fault tolerance. In this article, presentations were made that compares RMPP to TCP, UDP, and "Utopia". The article compared the protocols on four benchmarks: bandwidth, latency, all-to-all, and communication-computation overlap. The results have shown that message-based protocols like RMPP have several advantages over TCP including ease of implementation, support for computation/communication overlap, and low CPU overhead.
Solidification is an important aspect of welding, brazing, soldering, LENS fabrication, and casting. The current trend toward utilizing large-scale process simulations and materials response models for simulation-based engineering is driving the development of new modeling techniques. However, the effective utilization of these models is, in many cases, limited by a lack of fundamental understanding of the physical processes and interactions involved. In addition, experimental validation of model predictions is required. We have developed new and expanded experimental techniques, particularly those needed for in-situ measurement of the morphological and kinetic features of the solidification process. The new high-speed, high-resolution video techniques and data extraction methods developed in this work have been used to identify several unexpected features of the solidification process, including the observation that the solidification front is often far more dynamic than previously thought. In order to demonstrate the utility of the video techniques, correlations have been made between the in-situ observations and the final solidification microstructure. Experimental methods for determination of the solidification velocity in highly dynamic pulsed laser welds have been developed, implemented, and used to validate and refine laser welding models. Using post solidification metallographic techniques, we have discovered a previously unreported orientation relationship between ferrite and austenite in the Fe-Cr-Ni alloy system, and have characterized the conditions under which this new relationship develops. Taken together, the work has expanded both our understanding of, and our ability to characterize, solidification phenomena in complex alloy systems and processes.
We present a technique for determining non-linear resistances, capacitances, and inductances from ring down data in a non-linear RLC circuit. Although the governing differential equations are non-linear, we are able to solve this problem using linear least squares without doing any sort of non-linear iteration.
This paper presents a description of the SIERRA Framework Version 3 parallel transfer operators. The high-level design including object interrelationships, as well as requirements for their use, is discussed. Transfer operators are used for moving field data from one computational mesh to another. The need for this service spans many different applications. The most common application is to enable loose coupling of multiple physics modules, such as for the coupling of a quasi-statics analysis with a thermal analysis. The SIERRA transfer operators support the transfer of nodal and element fields between meshes of different, arbitrary parallel decompositions. Also supplied are ''copy'' transfer operators for efficient transfer of fields between identical meshes. A ''copy'' transfer operator is also implemented for constraint objects. Each of these transfer operators is described. Also, two different parallel algorithms are presented for handling the geometric misalignment between different parallel-distributed meshes.
Increasing concerns for the security of the national infrastructure have led to a growing need for improved management and control of municipal water networks. To deal with this issue, optimization offers a general and extremely effective method to identify (possibly harmful) disturbances, assess the current state of the network, and determine operating decisions that meet network requirements and lead to optimal performance. This paper details an optimization strategy for the identification of source disturbances in the network. Here we consider the source inversion problem modeled as a nonlinear programming problem. Dynamic behavior of municipal water networks is simulated using EPANET. This approach allows for a widely accepted, general purpose user interface. For the source inversion problem, flows and concentrations of the network will be reconciled and unknown sources will be determined at network nodes. Moreover, intrusive optimization and sensitivity analysis techniques are identified to assess the influence of various parameters and models in the network in a computational efficient manner. A number of numerical comparisons are made to demonstrate the effectiveness of various optimization approaches.
This paper presents a high-level overview of the algorithms and supporting functionality provided by SIERRA Framework Version 3 for h-adaptive finite-element mechanics application development. Also presented is a fairly comprehensive description of what is required by the application codes to use the SIERRA h-adaptivity services. In general, the SIERRA framework provides the functionality for hierarchically subdividing elements in a distributed parallel environment, as well as dynamic load balancing. The mechanics application code is required to supply an a posteriori error indicator, prolongation and restriction operators for the field variables, hanging-node constraint handlers, and execution control code. This paper does not describe the Application Programming Interface (API), although references to SIERRA framework classes are given where appropriate.
The SIERRA Framework core services provide essential services for managing the mesh data structure, computational fields, and physics models of an application. An application using these services will supply a set of physics models, define the computational fields that are required by those models, and define the mesh upon which its physics models operate. The SIERRA Framework then manages all of the data for a massively parallel multiphysics application.
Aspen, a powerful economic modeling tool that uses agent modeling and genetic algorithms, can accurately simulate the economy. In it, individuals are hired by firms to produce a good that households then purchase. The firms decide what price to charge for this good, and based on that price, the households determine which firm to purchase from. We will attempt to discover the Nash Equilibrium price found in this model under two different methods of determining how many orders each firm receives. To keep it simple, we will assume there are only two firms in our model, and that these firms compete for the sale of one identical good.
This LDRD project has involved the development and application of Sandia's massively parallel materials modeling software to several significant biophysical systems. They have been successful in applying the molecular dynamics code LAMMPS to modeling DNA, unstructured proteins, and lipid membranes. They have developed and applied a coupled transport-molecular theory code (Tramonto) to study ion channel proteins with gramicidin A as a prototype. they have used the Towhee configurational bias Monte-Carlo code to perform rigorous tests of biological force fields. they have also applied the MP-Sala reacting-diffusion code to model cellular systems. Electroporation of cell membranes has also been studied, and detailed quantum mechanical studies of ion solvation have been performed. In addition, new molecular theory algorithms have been developed (in FasTram) that may ultimately make protein solvation calculations feasible on workstations. Finally, they have begun implementation of a combined molecular theory and configurational bias Monte-Carlo code. They note that this LDRD has provided a basis for several new internal (e.g. several new LDRD) and external (e.g. 4 NIH proposals and a DOE/Genomes to Life) proposals.
This manual describes the use of the Xyce Parallel Electronic Simulator code for simulating electrical circuits at a variety of abstraction levels. The Xyce Parallel Electronic Simulator has been written to support,in a rigorous manner, the simulation needs of the Sandia National Laboratories electrical designers. As such, the development has focused on improving the capability over the current state-of-the-art in the following areas: (1) Capability to solve extremely large circuit problems by supporting large-scale parallel computing platforms (up to thousands of processors). Note that this includes support for most popular parallel and serial computers. (2) Improved performance for all numerical kernels (e.g., time integrator, nonlinear and linear solvers) through state-of-the-art algorithms and novel techniques. (3) A client-server or multi-tiered operating model wherein the numerical kernel can operate independently of the graphical user interface (GUI). (4) Object-oriented code design and implementation using modern coding-practices that ensure that the Xyce Parallel Electronic Simulator will be maintainable and extensible far into the future. The code is a parallel code in the most general sense of the phrase--a message passing parallel implementation--which allows it to run efficiently on the widest possible number of computing platforms. These include serial, shared-memory and distributed-memory parallel as well as heterogeneous platforms. Furthermore, careful attention has been paid to the specific nature of circuit-simulation problems to ensure that optimal parallel efficiency is achieved even as the number of processors grows. Another feature required by designers is the ability to add device models, many specific to the needs of Sandia, to the code. To this end, the device package in the Xyce Parallel Electronic Simulator is designed to support a variety of device model inputs. These input formats include standard analytical models, behavioral models and look-up tables. Combined with this flexible interface is an architectural design that greatly simplifies the addition of circuit models. One of the most important contribution Xyce makes to the designers at Sandia National Laboratories is in providing a platform for computational research and development aimed specifically at the needs of the Laboratory. With Xyce, Sandia now has an ''in-house''capability with which both new electrical (e.g., device model development) and algorithmic (e.g., faster time-integration methods) research and development can be performed. Furthermore, these capabilities will then be migrated to the end users.
This report presents a detailed multi-methods comparison of the spatial errors associated with finite difference, finite element and finite volume semi-discretizations of the scalar advection-diffusion equation. The errors are reported in terms of non-dimensional phase and group speeds, discrete diffusivity, artificial diffusivity, and grid-induced anisotropy. It is demonstrated that Fourier analysis (aka von Neumann analysis) provides an automatic process for separating the spectral behavior of the discrete advective operator into its symmetric dissipative and skew-symmetric advective components. Further it is demonstrated that streamline upwind Petrov-Galerkin and its control-volume finite element analogue, streamline upwind control-volume, produce both an artificial diffusivity and an artificial phase speed in addition to the usual semi-discrete artifacts observed in the discrete phase speed, group speed and diffusivity. For each of the numerical methods considered, asymptotic truncation error and resolution estimates are presented for the limiting cases of pure advection and pure diffusion. The Galerkin finite element method and its streamline upwind derivatives are shown to exhibit super-convergent behavior in terms of phase and group speed when a consistent mass matrix is used in the formulation. In contrast, the CVFEM method and its streamline upwind derivatives yield strictly second-order behavior. While this work can only be considered a first step in a comprehensive multi-methods analysis and comparison, it serves to identify some of the relative strengths and weaknesses of multiple numerical methods in a common mathematical framework.
ALEGRA is an arbitrary Lagrangian-Eulerian finite element code that emphasizes large distortion and shock propagation. This document describes the user input language for the code.
Three years of large-scale PDE-constrained optimization research and development are summarized in this report. We have developed an optimization framework for 3 levels of SAND optimization and developed a powerful PDE prototyping tool. The optimization algorithms have been interfaced and tested on CVD problems using a chemically reacting fluid flow simulator resulting in an order of magnitude reduction in compute time over a black box method. Sandia's simulation environment is reviewed by characterizing each discipline and identifying a possible target level of optimization. Because SAND algorithms are difficult to test on actual production codes, a symbolic simulator (Sundance) was developed and interfaced with a reduced-space sequential quadratic programming framework (rSQP++) to provide a PDE prototyping environment. The power of Sundance/rSQP++ is demonstrated by applying optimization to a series of different PDE-based problems. In addition, we show the merits of SAND methods by comparing seven levels of optimization for a source-inversion problem using Sundance and rSQP++. Algorithmic results are discussed for hierarchical control methods. The design of an interior point quadratic programming solver is presented.
Imaging systems such as Synthetic Aperture Radar collect band-limited data from which an image of a target scene is rendered. The band-limited nature of the data generates sidelobes, or ''spilled energy'' most evident in the neighborhood of bright point-like objects. It is generally considered desirable to minimize these sidelobes, even at the expense of some generally small increase in system bandwidth. This is accomplished by shaping the spectrum with window functions prior to inversion or transformation into an image. A window function that minimizes sidelobe energy can be constructed based on prolate spheroidal wave functions. A parametric design procedure allows doing so even with constraints on allowable increases in system bandwidth. This approach is extended to accommodate spectral notches or holes, although the guaranteed minimum sidelobe energy can be quite high in this case. Interestingly, for a fixed bandwidth, the minimum-mean-squared-error image rendering of a target scene is achieved with no windowing at all (rectangular or boxcar window).
Over the past several decades, the development of computer models to predict the atmospheric transport of hazardous material across a local (on the order of 10s of km) to mesoscale (on the order of 100s of km) region has received considerable attention, for both regulatory purposes, and to guide emergency response teams. Wind inputs to these models cover a spectrum of sophistication and required resources. At one end is the interpolation/extrapolation of available observations, which can be done rapidly, but at the risk of missing important local phenomena. Such a model can also only describe the wind at the time the observations were made. At the other end are sophisticated numerical solutions based on so-called Primitive Equation models. These prognostic models, so-called because in principle they can forecast future conditions, contain the most physics, but can easily consume tens of hours, if not days, of computer time. They may also require orders of magnitude more effort to set up, as both boundary and initial conditions on all the relevant variables must be supplied. The subject of this report is two classes of models intermediate in sophistication between the interpolated and prognostic ends of the spectrum. The first, known as mass-consistent (sometimes referred to as diagnostic) models, attempt to strike a compromise between simple interpolation and the complexity of the Primitive Equation models by satisfying only the conservation of mass (continuity) equation. The second class considered here consists of the so-called linear models, which purport to satisfy both mass and momentum balances. A review of the published literature on these models over the past few decades was performed. Though diagnostic models use a variety of approaches, they tend to fall into a relatively few well-defined categories. Linear models, on the other hand, follow a more uniform methodology, though they differ in detail. The discussion considers the theoretical underpinnings of each category of the diagnostic models, and the linear models, in order to assess the advantages and disadvantages of each. It is concluded that diagnostic models are the better suited of the two for predicting the atmospheric dispersion of hazardous materials in emergency response scenarios, as the linear models are only able to accommodate gently-sloping terrain, and are predicated on several simplifying approximations which can be difficult to justify a priori. Of the various approaches used in diagnostic modeling, that based on the calculus of variations appears to be the most objective, in that it introduces the fewest number of arbitrary parameters. The strengths and weaknesses of models in this category, as they relate to the activities of Sandia's Nuclear Emergency Support Team (NEST), are further highlighted.
This report describes a 3-D fluid mechanics code for predicting flow past bluff bodies whose surfaces can be assumed to be made up of shell elements that are simply connected. Version 1.0 of the VIPAR code (Vortex Inflation PARachute code) is described herein. This version contains several first order algorithms that we are in the process of replacing with higher order ones. These enhancements will appear in the next version of VIPAR. The present code contains a motion generator that can be used to produce a large class of rigid body motions. The present code has also been fully coupled to a structural dynamics code in which the geometry undergoes large time dependent deformations. Initial surface geometry is generated from triangular shell elements using a code such as Patran and is written into an ExodusII database file for subsequent input into VIPAR. Surface and wake variable information is output into two ExodusII files that can be post processed and viewed using software such as EnSight{trademark}.
The DAKOTA (Design Analysis Kit for Optimization and Terascale Applications) toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. DAKOTA contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, analytic reliability, and stochastic finite element methods; parameter estimation with nonlinear least squares methods; and sensitivity analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the DAKOTA toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a developers manual for the DAKOTA software and describes the DAKOTA class hierarchies and their interrelationships. It derives directly from annotation of the actual source code and provides detailed class documentation, including all member functions and attributes.
The DAKOTA (Design Analysis Kit for Optimization and Terascale Applications) toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. DAKOTA contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, analytic reliability, and stochastic finite element methods; parameter estimation with nonlinear least squares methods; and sensitivity analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the DAKOTA toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a user's manual for the DAKOTA software and provides capability overviews and procedures for software execution, as well as a variety of example studies.
