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.
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.
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.
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.
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.
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.
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).
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.
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.
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.
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.