Publications

Abstract not provided.

We are pleased to submit our efforts in parallelizing the PRONTO application suite for con- sideration in the SuParCup 99 competition. PRONTO is a finite element transient dynamics simulator which includes a smoothed particle hydrodynamics (SPH) capability; it is similar in scope to the well-known DYNA, PamCrash, and ABAQUS codes. Our efforts over the last few years have produced a fully parallel version of the entire PRONTO code which (1) runs fast and scalably on thousands of processors, (2) has performed the largest finite-element transient dynamics simulations we are aware of, and (3) includes several new parallel algorithmic ideas that have solved some difficult problems associated with contact detection and SPH scalability. We motivate this work, describe the novel algorithmic advances, give performance numbers for PRONTO running on Sandia's Intel Teraflop machine, and highlight two prototypical large-scale computations we have performed with the parallel code. We have successfully parallelized a large-scale production transient dynamics code with a novel algorithmic approach that utilizes multiple decompositions for different key segments of the computations. To be able to simulate a more than ten million element model in a few tenths of second per timestep is unprecedented for solid dynamics simulations, especially when full global contact searches are required. The key reason is our new algorithmic ideas for efficiently parallelizing the contact detection stage. To our knowledge scalability of this computation had never before been demonstrated on more than 64 processors. This has enabled parallel PRONTO to become the only solid dynamics code we are aware of that can run effectively on 1000s of processors. More importantly, our parallel performance compares very favorably to the original serial PRONTO code which is optimized for vector supercomputers. On the container crush problem, a Teraflop node is as fast as a single processor of the Cray Jedi. This means that on the Teraflop machine we can now run simulations with tens of millions of elements thousands of times faster than we could on the Jedi! This is enabling transient dynamics simulations of unprecedented scale and fidelity. Not only can previous applications be run with vastly improved resolution and speed, but qualitatively new and different analyses have been made possible.

Single-level parallel optimization approaches, those in which either the simulation code executes in parallel or the optimiza- tion algorithm invokes multiple simultaneous single-processor analyses, have been investigated previously and been shown to be effective in reducing the time required to compute optimal solutions. However, these approaches have clear performance limita- tions that prevent effective scaling with the thousands of processors available in massively parallel supercomputers. In more recent work, a capability has been developed for multilevel parallelism in which multiple instances of multiprocessor simulations are coordinated simultaneously. This implementation employs a master-slave approach using the Message Passing Interface (MPI) within the DAKOTA software toolkit. Mathematical analysis on achieving peak efficiency in multilevel parallelism has shown that the most effective processor partitioning scheme is the one that limits the size of multiprocessor simulations in favor of concurrent execution of multiple simulations. That is, if both coarse-grained and fine-grained parallelism can be exploited, then preference should be given to the coarse-grained parallelism. This analysis was verified in multilevel paralIel computatiorud experiments on networks of workstations (NOWS) and on the Intel TeraFLOPS massively parallel supercomputer. In current work, methods for exploiting additional coarse-grained parallelism in optimization are being investigated so that fine-grained efficiency losses can be further minimized. These activities are focusing on both algorithmic coarse-grained parallel- ism (multiple independent function evaluations) through the development of speculative gradient methods and concurrent iterator strategies and on function evaluation coarse-grained parallelism (multiple separable simulations within a function evaluation) through the development of general partitioning and nested synchronization facilities. The net result is a total of four separate lev- els of parallelism which can minimize efficiency losses and achieve near linear scaling on massively parallel computers.

Abstract not provided.

Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits.

Evolutionary pattern search algorithms (EPSAs) are a class of evolutionary algorithms (EAs) that have convergence guarantees on a broad class of nonconvex continuous problems. In previous work we have analyzed the empirical performance of EPSAs. This paper revisits that analysis and extends it to a more general model of mutation. We experimentally evaluate how the choice of the set of mutation offsets affects optimization performance for EPSAs. Additionally, we compare EPSAs to self-adaptive EAs with respect to robustness and rate of optimization. All experiments employ a suite of test functions representing a range of modality and number of multiple minima.

Evolutionary programs (EPs) and evolutionary pattern search algorithms (EPSAS) are two general classes of evolutionary methods for optimizing on continuous domains. The relative performance of these methods has been evaluated on standard global optimization test functions, and these results suggest that EPSAs more robustly converge to near-optimal solutions than EPs. In this paper we evaluate the relative performance of EPSAs and EPs on a real-world application: flexible ligand binding in the Autodock docking software. We compare the performance of these methods on a suite of docking test problems. Our results confirm that EPSAs and EPs have comparable performance, and they suggest that EPSAs may be more robust on larger, more complex problems.

Techniques for modeling oil well sand production have been developed using the formulations for superquadric discrete elements and Darcy fluid flow. Discrete element models are generated using the new technique of particle cloning. Discrete element sources and sinks allow simulation of sand production from the initial state through the transition to an equilibrium state where particles are created and removed at the same rate.

Evolutionary algorithms have been successfully applied to a variety of molecular structure prediction problems. In this paper we reconsider the design of genetic algorithms that have been applied to a simple protein structure prediction problem. Our analysis considers the impact of several algorithmic factors for this problem: the confirmational representation, the energy formulation and the way in which infeasible conformations are penalized, Further we empirically evaluated the impact of these factors on a small set of polymer sequences. Our analysis leads to specific recommendations for both GAs as well as other heuristic methods for solving PSP on the HP model.

This report documents a data collection where we recorded redundant range image data from multiple views of a simple scene, and recorded accurate survey measurements of the same scene. Collecting these data was a focus of the research project Automated Geometric Model Builder Using Range Image Sensor Data (96-0384), supported by Sandia's Laboratory-Directed Research and Development (LDRD) Program during fiscal years 1996, 1997, and 1998. The data described here are available from the authors on CDROM, or electronically over the Internet. Included in this data distribution are Computer-Aided Design (CAD) models we constructed from the survey measurements. The CAD models are compatible with the SolidWorks 98 Plus system, the modern Computer-Aided Design software system that is central to Sandia's DeskTop Engineering Project (DTEP). Integration of our measurements (as built) with the constructive geometry process of the CAD system (as designed) delivers on a vision of the research project. This report on our final data collection will also serve as a final report on the project.

A response surface methodology-based technique is presented for treating discretization error in non-deterministic analysis. The response surface, or metamodel, is estimated from computer experiments which vary both uncertain physical parameters and the fidelity of the computational mesh. The resultant metamodel is then used to propagate the variabilities in the continuous input parameters, while the mesh size is taken to zero, its asymptotic limit. With respect to mesh size, the metamodel is equivalent to Richardson extrapolation, in which solutions on coarser and finer meshes are used to estimate discretization error. The method is demonstrated on a one dimensional prismatic bar, in which uncertainty in the third vibration frequency is estimated by propagating variations in material modulus, density, and bar length. The results demonstrate the efficiency of the method for combining non-deterministic analysis with error estimation to obtain estimates of total simulation uncertainty. The results also show the relative sensitivity of failure estimates to solution bias errors in a reliability analysis, particularly when the physical variability of the system is low.

In this paper we evaluate the design of the hybrid evolutionary algorithms (EAs) that are currently used to perform flexible ligand binding in the Autodock docking software. Hybrid EAs incorporate specialized operators that exploit domain-specific features to accelerate an EA's search. We consider hybrid EAs that use an integrated local search operator to reline individuals within each iteration of the search. We evaluate several factors that impact the efficacy of a hybrid EA, and we propose new hybrid EAs that provide more robust convergence to low-energy docking configurations than the methods currently available in Autodock.

Many applications produce three-dimensional points that must be further processed to generate a surface. Surface reconstruction algorithms that start with a set of unorganized points are extremely time-consuming. Often, however, points are generated such that there is additional information available to the reconstruction algorithm. We present a specialized algorithm for surface reconstruction that is three orders of magnitude faster than algorithms for the general case. In addition to sample point locations, our algorithm starts with normal information and knowledge of each point's neighbors. Our algorithm produces a localized approximation to the surface by creating a star-shaped triangulation between a point and a subset of its nearest neighbors. This surface patch is extended by locally triangulating each of the points along the edge of the patch. As each edge point is triangulated, it is removed from the edge and new edge points along the patch's edge are inserted in its place. The updated edge spirals out over the surface until the edge encounters a surface boundary and stops growing in that direction, or until the edge reduces to a small hole that fills itself in.

A computational procedure for extracting substructure-by-substructure flexibility properties from global modal parameters is presented. The present procedure consists of two key features: an element-based direct flexibility method, which uniquely determines the global flexibility without resorting to case-dependent redundancy selections, and the projection of kinematically inadmissible modes that are contained in the iterated substructural matrices. The direct flexibility method is used as the basis of an inverse problem, whose goal is to determine substructural flexibilities given the global flexibility, geometrically determined substructural rigid-body modes, and the local-to-global assembly operators. The resulting procedure, given accurate global flexibility, extracts the exact element-by-element substructural flexibilities for determinate structures. For indeterminate structures, the accuracy depends on the iteration tolerance limits. The procedure is illustrated using both simple and complex numerical examples and appears to be effective for structural applications such as damage localization and finite element model reconciliation.

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. © Springer-Verlag 1999.

Dual control volume grand canonical molecular dynamics (DCV-GCMD) is a boundary-driven non-equilibrium molecular dynamics technique for simulating gradient driven diffusion in multi-component systems. Two control volumes are established at opposite ends of the simulation box. Constant temperature and chemical potential of diffusing species are imposed in the control volumes. This results in stable chemical potential gradients and steady-state diffusion fluxes in the region between the control volumes. We present results and detailed analysis for a new constant-pressure variant of the DCV-GCMD method in which one of the diffusing species for which a steady-state diffusion flux exists does not have to be inserted or deIeted. Constant temperature, pressure and chemical potential of all diffusing species except one are imposed in the control volumes. The constant-pressure method can be applied to situations in which insertion and deletion of large molecules would be prohibitively difficult. As an exampIe, we used the method to shnulate diffusion in a biruuy mixture of spherical particles with a 2:1 size ratio. Steady-state diffusion fluxes of both diffbsi.ng species were established. The constant-pressure diffision coefficients agreed closely with the results of the standard constant-volume calculations. In addition, we show how the concentration, chemical potential and flux profiles can be used to calculate kwd binary and Maxwell-Stefim diffusion coefficients. In the case of the 2:1 size ratio mixture, we found that the binary dlffision coefficients were asymmetric and composition dependent, whereas the Maxwell-Stefan diffision coefficients changed very little with composition and were symmetric. This last result verified that the Gibbs-Duhem relation was satisfied locally, thus validating the assumption of local equilibrium.

A phase-field model for grain growth is briefly described. In this model, a poly-crystalline microstructure is represented by multiple structural order parameter fields whose temporal and spatial evolutions follow the time-dependent Ginzburg-Landau (TDGL) equations. Results from phase-field simulations of two-dimensional (2D) grain growth will be summarized and preliminary results on three-dimensional (3D) grain growth will be presented. The physical interpretation of the structural order parameter fields and the efficient and accurate semi-implicit Fourier spectral method for solving the TDGL equations will be briefly discussed.

Electronic structure calculations frequently invoke periodic boundary conditions to solve for electrostatic potentials. For systems that are electronically charged, or contain dipole (or higher) moments, this artifice introduces spurious potentials due to the interactions between the system and multipole moments of its periodic images in aperiodic directions. I describe a method to properly handle the multipole moments of the electron density in electronic structure calculations using periodic boundary conditions. The density for which an electrostatic potential is to be evaluated is divided into two pieces. A local density is constructed that matches the desired moments of the full density, and its potential computed treating this density as isolated. With the density of this local moment countercharge removed from the full density, the remainder density lacks the troublesome moments and its electrostatic potential can be evaluated accurately using periodic boundary conditions.

A discrete element computer program named DMC_BLAST (Distinct Motion Code) has been under development since 1987 for modeling rock blasting (Preece & Taylor, 1989). This program employs explicit time integration and uses spherical or cylindrical elements that are represented as circles in two dimensions. DMC_BLAST calculations compare favorably with data from actual bench blasts (Preece et al, 1993). Coal seam chilling refers to the shattering of a significant portion of the coal leaving unusable fines. It is also refereed to as coal damage. Chilling is caused during a blast by a combination of explosive shock energy and movement of the adjacent rock. Chilling can be minimized by leaving a buffer zone between the bottom of the blastholes and the coal seam or by changing the blast design to decrease the powder factor or by a combination of both. Blast design in coal mine cast blasting is usually a compromise between coal damage and rock fragmentation and movement (heave). In this paper the damage to coal seams from rock movement is examined using the discrete element computer code DMC_BLAST. A rock material strength option has been incorporated into DMC_BLAST by placing bonds/links between the spherical particles used to model the rock. These bonds tie the particles together but can be broken when the tensile, compressive or shear stress in the bond exceeds the defined strength. This capability has been applied to predict coal seam damage, particularly at the toe of a cast blast where drag forces exerted by movement of the overlying rock can adversely effect the top of the coal at the bench face. A simulation of coal mine cast blasting has been performed with special attention being paid to the strength of the coal and its behavior at t he bench face during movement of the overlying material.

This paper describes a method of modeling swarms of UAVs and/or fighter aircraft using particle simulation concepts. Recent investigations into the use of genetic algorithms to design neural networks for the control of autonomous vehicles (i.e., robots) led to the examination of methods of simulating large collections of robots. This paper describes the successful implementation of a model of swarm dynamics using particle simulation concepts. Several examples of the complex behaviors achieved in a target/interceptor scenario are presented.

The ability to image complex geologies such as salt domes in the Gulf of Mexico and thrusts in mountainous regions is essential for reducing the risk associated with oil exploration. Imaging these structures, however, is computationally expensive as datasets can be terabytes in size. Traditional ray-tracing migration methods cannot handle complex velocity variations commonly found near such salt structures. Instead the authors use the full 3D acoustic wave equation, discretized via a finite difference algorithm. They reduce the cost of solving the apraxial wave equation by a number of numerical techniques including the method of fractional steps and pipelining the tridiagonal solves. The imaging code, Salvo, uses both frequency parallelism (generally 90% efficient) and spatial parallelism (65% efficient). Salvo has been tested on synthetic and real data and produces clear images of the subsurface even beneath complicated salt structures.

The National Institute of Justice has tasked their Satellite Facility at Sandia National Laboratories and their Southeast Regional Technology Center in Charleston, South Carolina to devise new procedures and tools for helping correctional facilities to assess their security vulnerabilities. Thus, a team is visiting selected correctional facilities and performing vulnerability assessments. A vulnerability assessment helps to identi~ the easiest paths for inmate escape, for introduction of contraband such as drugs or weapons, for unexpected intrusion fi-om outside of the facility, and for the perpetration of violent acts on other inmates and correctional employees, In addition, the vulnerability assessment helps to quantify the security risks for the facility. From these initial assessments will come better procedures for performing vulnerability assessments in general at other correctional facilities, as well as the development of tools to assist with the performance of such vulnerability assessments.

Distributed systems have been studied for twenty years and are now coming into wider use as fast networks and powerful workstations become more readily available. In many respects a massively parallel computer resembles a network of workstations and it is tempting to port a distributed operating system to such a machine. However, there are significant differences between these two environments and a parallel operating system is needed to get the best performance out of a massively parallel system. This report characterizes the differences between distributed systems, networks of workstations, and massively parallel systems and analyzes the impact of these differences on operating system design. In the second part of the report, we introduce Puma, an operating system specifically developed for massively parallel systems. We describe Puma portals, the basic building blocks for message passing paradigms implemented on top of Puma, and show how the differences observed in the first part of the report have influenced the design and implementation of Puma.

This white paper presents the initial requirements for developing a new computer model for simulating the effects of extreme acts of terrorism in the United States. General characteristics of the model are proposed and the level of effort to prepare a complete written description of the model, prior to coding, is detailed. The model would simulate the decision processes and interactions of complex U. S. systems engaged in responding to and recovering from four types of terrorist incidents. The incident scenarios span the space of extreme acts of terrorism that have the potential to affect not only the impacted area, but also the entire nation. The model would be useful to decision-makers in assessing and analyzing the vulnerability of the nation's complex infrastructures, in prioritizing resources to reduce risk, and in planning strategies for immediate response and for subsequent recovery from terrorist incidents.

Phase encoding of shot records provides a means of imaging a number of shots within a single migration. This results in a reduction in the required computation for a complete image, a reduction by the number of shots used in each individual migration, trading this increase in speed for additional noise in the resulting image. Some methods for phase encoding have been shown to limit this noise to a tolerable range when combining several shots, enabling speed ups of a factor of a few. In this paper, the authors present a use of phase encoding which allows faster imaging by an order of magnitude or more, with the additional benefit that the individual migrations can be stopped whenever the answer is good enough. This approach may ultimately render 3-D frequency-domain prestack depth migration cost effective.

The Reproducing Kernel Particle Method (RKPM) has many attractive properties that make it ideal for treating a broad class of physical problems. RKPM may be implemented in a mesh-full or a mesh-free manner and provides the ability to tune the method, via the selection of a dilation parameter and window function, in order to achieve the requisite numerical performance. RKPM also provides a framework for performing hierarchical computations making it an ideal candidate for simulating multi-scale problems. Although RKPM has many appealing attributes, the method is quite new and its numerical performance is still being quantified with respect to more traditional discretization methods. In order to assess the numerical performance of RKPM, detailed studies of RKPM on a series of model partial differential equations has been undertaken. The results of von Neumann analyses for RKPM semi-discretizations of one and two-dimensional, first and second-order wave equations are presented in the form of phase and group errors. Excellent dispersion characteristics are found for the consistent mass matrix with the proper choice of dilation parameter. In contrast, the influence of row-sum lumping the mass matrix is shown to introduce severe lagging phase errors. A higher-order mass matrix improves the dispersion characteristics relative to the lumped mass matrix but delivers severe lagging phase errors relative to the fully integrated, consistent mass matrix.

Coupled blast-structural computational simulations using supercomputer capabilities will significantly advance the understanding of how complex structures respond under dynamic loads caused by explosives and earthquakes, an understanding with application to the surety of both federal and nonfederal buildings. Simulation of the effects of explosives on structures is a challenge because the explosive response can best be simulated using Eulerian computational techniques and structural behavior is best modeled using Lagrangian methods. Due to the different methodologies of the two computational techniques and code architecture requirements, they are usually implemented in different computer programs. Explosive and structure modeling in two different codes make it difficult or next to impossible to do coupled explosive/structure interaction simulations. Sandia National Laboratories has developed two techniques for solving this problem. The first is called Smoothed Particle Hydrodynamics (SPH), a relatively new gridless method comparable to Eulerian, that is especially suited for treating liquids and gases such as those produced by an explosive. The SPH capability has been fully implemented into the transient dynamics finite element (Lagrangian) codes PRONTO-2D and -3D. A PRONTO-3D/SPH simulation of the effect of a blast on a protective-wall barrier is presented in this paper. The second technique employed at Sandia National Laboratories uses a relatively new code called ALEGRA which is an ALE (Arbitrary Lagrangian-Eulerian) wave code with specific emphasis on large deformation and shock propagation. ALEGRA is capable of solving many shock-wave physics problems but it is especially suited for modeling problems involving the interaction of decoupled explosives with structures.

This paper presents a graph-based approach to network vulnerability analysis. The method is flexible, allowing analysis of attacks from both outside and inside the network. It can analyze risks to a specific network asset, or examine the universe of possible consequences following a successful attack. The graph-based tool can identify the set of attack paths that have a high probability of success (or a low effort cost) for the attacker. The system could be used to test the effectiveness of making configuration changes, implementing an intrusion detection system, etc. The analysis system requires as input a database of common attacks, broken into atomic steps, specific network configuration and topology information, and an attacker profile. The attack information is matched with the network configuration information and an attacker profile to create a superset attack graph. Nodes identify a stage of attack, for example the class of machines the attacker has accessed and the user privilege level he or she has compromised. The arcs in the attack graph represent attacks or stages of attacks. By assigning probabilities of success on the arcs or costs representing level-of-effort for the attacker, various graph algorithms such as shortest-path algorithms can identify the attack paths with the highest probability of success.

With the increased use of public key cryptography, faster modular multiplication has become an important cryptographic issue. Almost all public key cryptography, including most elliptic curve systems, use modular multiplication. Modular multiplication, particularly for the large public key modulii, is very slow. Increasing the speed of modular multiplication is almost synonymous with increasing the speed of public key cryptography. There are two parts to modular multiplication: multiplication and modular reduction. Though there are fast methods for multiplying and fast methods for doing modular reduction, they do not mix well. Most fast techniques require integers to be in a special form. These special forms are not related and converting from one form to another is more costly than using the standard techniques. To this date it has been better to use the fast modular reduction technique coupled with standard multiplication. Standard modular reduction is much more costly than standard multiplication. Fast modular reduction (Montgomery`s method) reduces the reduction cost to approximately that of a standard multiply. Of the fast multiplication techniques, the redundant number system technique (RNS) is one of the most popular. It is simple, converting a large convolution (multiply) into many smaller independent ones. Not only do redundant number systems increase speed, but the independent parts allow for parallelization. RNS form implies working modulo another constant. Depending on the relationship between these two constants; reduction OR division may be possible, but not both. This paper describes a new technique using ideas from both Montgomery`s method and RNS. It avoids the formula problem and allows fast reduction and multiplication. Since RNS form is used throughout, it also allows the entire process to be parallelized.

This paper presents a graph based approach to network vulnerability analysis. The method is flexible, allowing analysis of attacks from both outside and inside the network. It can analyze risks to a specific network asset, or examine the universe of possible consequences following a successful attack. The analysis system requires as input a database of common attacks, broken into atomic steps, specific network configuration and topology information, and an attacker profile. The attack information is matched with the network configuration information and an attacker profile to create a superset attack graph. Nodes identify a stage of attack, for example the class of machines the attacker has accessed and the user privilege level he or she has compromised. The arcs in the attack graph represent attacks or stages of attacks. By assigning probabilities of success on the arcs or costs representing level of effort for the attacker, various graph algorithms such as shortest path algorithms can identify the attack paths with the highest probability of success.

Design metaphors play an important role in the development of many software projects. However, the influence of metaphors on project functionality, design methodology and the interactions among members of the development team is not well understood. This paper seeks insights into these issues by examining the experiences of a design team in building a system under the influence of a particularly strong design metaphor.

It has been recognized that nondestructive inspection (NDI) techniques and instruments that have proven themselves in the laboratory do not always perform as well under field conditions. In this paper the authors explore combinations of formal laboratory and field experimentation to characterize NDI processes as they may be implemented in field conditions. They also discuss appropriate modeling for probability of detection (POD) curves as applied to data gathered under field conditions. A case is made for expanding the more traditional two-parameter models to models using either three or four parameters. They use NDI data gathered from various airframe inspection programs to illustrate the points.

LDRD research activities have focused on increasing the robustness and efficiency of optimization studies for computationally complex engineering problems. Engineering applications can be characterized by extreme computational expense, lack of gradient information, discrete parameters, non-converging simulations, and nonsmooth, multimodal, and discontinuous response variations. Guided by these challenges, the LDRD research activities have developed application-specific techniques, fundamental optimization algorithms, multilevel hybrid and sequential approximate optimization strategies, parallel processing approaches, and automatic differentiation and adjoint augmentation methods. This report surveys these activities and summarizes the key findings and recommendations.

We are interested in the stability of three-dimensional fluid flows to small disturbances. One computational approach is to solve a sequence of large sparse generalized eigenvalue problems for the leading modes that arise from discretizating the differential equations modeling the flow. The modes of interest are the eigenvalues of largest real part and their associated eigenvectors. We discuss our work to develop an efficient and reliable eigensolver for use by the massively parallel simulation code MPSalsa. MPSalsa allows simulation of complex 3D fluid flow, heat transfer, and mass transfer with detailed bulk fluid and surface chemical reaction kinetics.

A linear least-squares procedure for the determination of modal residues using time-domain system realization theory is presented. The present procedure is intended to complement existing techniques for time-domain system identification and is shown to be theoretically equivalent to residue determination in realization algorithms such as the eigensystem realization algorithm and Q-Markov covariance equivalent realization method. However, isolating the optimal residue estimation problem from the general realization problem affords several alternative strategies as compared to standard realization algorithms for structural dynamics identification. Primary among these are alternative techniques for handling data sets with large numbers of sensors using small numbers of reference point responses and the inclusion of terms that accurately model the effects of residual flexibility. The accuracy and efficiency of the present realization theory-based procedure is demonstrated for both simulated and experimental data.

Given a complete undirected graph with non-negative costs on the edges, the 2-Edge Connected Subgraph Problem consists in finding the minimum cost spanning 2-edge connected subgraph (where multiedges are allowed in the solution). A lower bound for the minimum cost 2-edge connected subgraph is obtained by solving the linear programming relaxation for this problem, which coincides with the subtour relaxation of the traveling salesman problem when the costs satisfy the triangle inequality. The simplest fractional solutions to the subtour relaxation are the (Formula presented)-integral solutions in which every edge variable has a value which is a multiple of (Formula presented). We show that the minimum cost of a 2-edge connected subgraph is at most four-thirds the cost of the minimum cost (Formula presented)-integral solution of the subtour relaxation. This supports the long-standing (Formula presented) Conjecture for the TSP, which states that there is a Hamilton cycle which is within (Formula presented) times the cost of the optimal subtour relaxation solution when the costs satisfy the triangle inequality.

This report describes the methodology for using a genetic programming model to develop tracking behaviors for autonomous, microscale robotic vehicles. The use of such vehicles for surveillance and detection operations has become increasingly important in defense and humanitarian applications. Through an evolutionary process similar to that found in nature, the genetic programming model generates a computer program that when downloaded onto a robotic vehicle`s on-board computer will guide the robot to successfully accomplish its task. Simulations of multiple robots engaged in problem-solving tasks have demonstrated cooperative behaviors. This report also discusses the behavior model produced by genetic programming and presents some results achieved during the study.

A numerical analysis of the deposition of gallium from trimethylgallium (TMG) and arsine in a horizontal CVD reactor with tilted susceptor and a three inch diameter rotating substrate is performed. The three-dimensional model includes complete coupling between fluid mechanics, heat transfer, and species transport, and is solved using an unstructured finite element discretization on a massively parallel computer. The effects of three operating parameters (the disk rotation rate, inlet TMG fraction, and inlet velocity) and two design parameters (the tilt angle of the reactor base and the reactor width) on the growth rate and uniformity are presented. The nonlinear dependence of the growth rate uniformity on the key operating parameters is discussed in detail. Efficient and robust algorithms for massively parallel reacting flow simulations, as incorporated into our analysis code MPSalsa, make detailed analysis of this complicated system feasible.

A discrete element computer program named DMC{underscore}BLAST (Distinct Motion Code) has been under development since 1987 for modeling rock blasting (Preece {ampersand} Taylor, 1989). This program employs explicit time integration and uses spherical or cylindrical elements that are represented as circles in two dimensions (2-D). DMC{underscore}BLAST calculations compare favorably with data from actual bench blasts (Preece et al, 1993). Buffer Choke blasting is commonly used in surface gold mines to break the rock and dilate it sufficiently for ease of digging, with the assumption of insignificant horizontal movement. The blast designs usually call for relatively shallow holes benches ({lt} 11 m) with small blastholes (approx. 165 mm), small burdens and spacings ({lt}5 m), often with 50% or more of the hole stemmed. Control of blast-induced horizontal movement is desired because the ore is assayed in place from the blasthole drill cuttings and digging polygons of ore and waste are laid out before the blast. Horizontal movement at the ore waste boundary can result in dilution of the ore or loss of ore with the waste. The discrete element computer program DMC{underscore}BLAST has been employed to study spatial variation of horizontal rock motion during buffer choke blasting. Patterns of rock motion can be recognized from the discrete element simulations that would be difficult or impossible to recognize in the field (Preece, Tidman and Chung, 1997). Techniques have been developed to calculate ore waste and dilution from the horizontal movement predicted by DMC{underscore}BLAST. Four DMC{underscore}BLAST simulations of buffer blasting have been performed. The blasts are identical except that the burden and spacing are systematically varied which also changes the powder factor. Predictions of ore waste or dilution are made for each burden in the blast, assuming no horizontal movement, to illustrate the spatial variation observed.

A new constitutive model is proposed for the modeling of penetration and large stress waves in concrete. Rate effects are incorporated explicitly into the damage evolution law, hence the term "brittle failure kinetics." The damage variable parameterizes a family of Mohr-Coulomb strength curves. The model, which has been implemented in the CTH code, has been shown to reproduce some distinctive phenomena that occur in penetration of concrete targets. Among these are the sharp spike in deceleration of a rigid penetrator immediately after impact. Another is the size scale effect, which leads to a nonlinear scaling of penetration depth with penetrator size. This paper discusses the theory of the model and some results of an extensive validation effort.

Adaptive numerical methods offer greater efficiency than traditional numerical methods by concentrating computational effort in regions of the problem domain where the solution is difficult to obtain. In this paper, the authors describe progress toward adding mesh refinement to MPSalsa, a computer program developed at Sandia National laboratories to solve coupled three-dimensional fluid flow and detailed reaction chemistry systems for modeling chemically reacting flow on large-scale parallel computers. Data structures that support refinement and dynamic load-balancing are discussed. Results using uniform refinement with mesh sequencing to improve convergence to steady-state solutions are also presented. Three examples are presented: a lid driven cavity, a thermal convection flow, and a tilted chemical vapor deposition reactor.

Computer modeling of Chemical Vapor Deposition (CVD) reactors can greatly aid in the understanding, design, and optimization of these complex systems. Modeling is particularly attractive in these systems since the costs of experimentally evaluating many design alternatives can be prohibitively expensive, time consuming, and even dangerous, when working with toxic chemicals like Arsine (AsH{sub 3}): until now, predictive modeling has not been possible for most systems since the behavior is three-dimensional and governed by complex reaction mechanisms. In addition, CVD reactors often exhibit large thermal gradients, large changes in physical properties over regions of the domain, and significant thermal diffusion for gas mixtures with widely varying molecular weights. As a result, significant simplifications in the models have been made which erode the accuracy of the models` predictions. In this paper, the authors will demonstrate how the vast computational resources of massively parallel computers can be exploited to make possible the analysis of models that include coupled fluid flow and detailed chemistry in three-dimensional domains. For the most part, models have either simplified the reaction mechanisms and concentrated on the fluid flow, or have simplified the fluid flow and concentrated on rigorous reactions. An important CVD research thrust has been in detailed modeling of fluid flow and heat transfer in the reactor vessel, treating transport and reaction of chemical species either very simply or as a totally decoupled problem. Using the analogy between heat transfer and mass transfer, and the fact that deposition is often diffusion limited, much can be learned from these calculations; however, the effects of thermal diffusion, the change in physical properties with composition, and the incorporation of surface reaction mechanisms are not included in this model, nor can transitions to three-dimensional flows be detected.

This technical report describes some lessons learned from implementing the Message Passing Interface (MPI) standard, and some proposed extentions to MPI, at Sandia. The implementations were developed using Sandia-developed lightweight kernels running on the Intel Paragon and Intel TeraFLOPS platforms. The motivations for this research are discussed, and a detailed analysis of several implementation issues is presented.

This report presents a microsimulation model of a transition economy. Transition is defined as the process of moving from a state-enterprise economy to a market economy. The emphasis is on growing a market economy starting from basic microprinciples. The model described in this report extends and modifies the capabilities of Aspen, a new agent-based model that is being developed at Sandia National Laboratories on a massively parallel Paragon computer. Aspen is significantly different from traditional models of the economy. Aspen`s emphasis on disequilibrium growth paths, its analysis based on evolution and emergent behavior rather than on a mechanistic view of society, and its use of learning algorithms to simulate the behavior of some agents rather than an assumption of perfect rationality make this model well-suited for analyzing economic variables of interest from transition economies. Preliminary results from several runs of the model are included.

This paper explores some of the many issues in developing security enhanced MPI for embedded real-time systems supporting the Department of Defense`s Multi-level Security policy (DoD MLS) are presented along with the preliminary design for such an MPI variant. In addition some of the many issues that need to be addressed in creating security enhanced versions of MPI for other domains are discussed. 19 refs.

The Dicer algorithm generates a fine mesh by refining each element in a coarse all-hexahedral mesh generated by any existing all-hexahedral mesh generation algorithm. The fine mesh is geometry-conforming. Using existing all-hexahedral meshing algorithms to define the initial coarse mesh simplifies the overall meshing process and allows dicing to take advantage of improvements in other meshing algorithms immediately. The Dicer algorithm will be used to generate large meshes in support of the ASCI program. The authors also plan to use dicing as the basis for parallel mesh generation. Dicing strikes a careful balance between the interactive mesh generation and multi-million element mesh generation processes for complex 3D geometries, providing an efficient means for producing meshes of varying refinement once the coarse mesh is obtained.

The use of feature recognition as part of an overall decomposition-based hexahedral meshing approach is described in this paper. The meshing approach consists of feature recognition, using a c-loop or hybrid c-loop method, and the use of cutting surfaces to decompose the solid model. These steps are part of an iterative process, which proceeds either until no more features can be recognized or until the model has been completely decomposed into meshable sub-volumes. This method can greatly reduce the time required to generate an all-hexahedral mesh, either through the use of more efficient meshing algorithms on more of the geometry or by reducing the amount of manual decomposition required to mesh a volume.

Simulation of the effects of explosives on structures is a challenge because the explosive response can best be simulated using Eulerian computational techniques and structural behavior is best modeled using Lagrangian methods. Due to the different methodology of the two computational techniques and code architecture requirements, they are usually implemented in different computer programs. Explosive and structure modeling in two different codes make it difficult or next to impossible to do coupled explosive/structure interaction simulations. Sandia National Laboratories has developed two techniques for solving this problem. The first is called Smoothed Particle Hydrodynamics (SPH), a relatively new gridless method comparable to Eulerian, that is especially suited for treating liquids and gases such as those produced by an explosive. The SPH capability has been fully implemented into the transient dynamics finite element (Lagrangian) codes PRONTO-2D and -3D. A PRONTO-3D/SPH simulation of the effect of a blast on a protective-wall barrier is presented in this paper. The second technique employed at Sandia uses a new code called Zapotec that combines the 3-D Eulerian code CTH and the Lagrangian code PRONTO-3D with minimal changes to either code. CTH and PRONTO-3D are currently executing on the Sandia Terraflops machine (9000 Pentium Pro processors). Eulerian simulations with 100 million cells have been completed on the current configuration of the machine (4500 Pentium Pro processors). The CTH and PRONTO-3D combination will soon be executing in a coupled fashion on this machine.

The authors define two simple metrics for accuracy of models built from range imaging information. They apply the metric to a model built from a recent range image taken at the Laser Radar Development and Evaluation Facility (LDERF), Eglin AFB, using a Scannerless Range Imager (SRI) from Sandia National Laboratories. They also present graphical displays of the residual information produced as a byproduct of this measurement, and discuss mechanisms that these data suggest for further improvement in the performance of this already impressive SRI.

A method which is capable of an efficient calculation of the two-dimensional stream function and velocity field produced by a large system of vortices is presented in this report. This work is based on the adaptive scheme of Carrier, Greengard, and Rokhlin with the added feature that the evaluation or target points do not have to coincide with the location of the source or vortex positions. A simple algorithm based on numerical experiments has been developed to optimize the method for cases where the number of vortices N{sub V} differs significantly from the number of target points N{sub T}. The ability to specify separate source and target fields provides an efficient means for calculating boundary conditions, trajectories of passive scalar quantities, and stream-function plots, etc. Test cases have been run to benchmark the truncation errors and CPU time savings associated with the method. For six terms in the series expansions, non-dimensional truncation errors for the magnitudes of the complex potential and velocity fields are on the order of 10{sup {minus}5} and 10{sup {minus}3} respectively. The authors found that the CPU time scales as {radical}(N{sub V}N{sub T}) for N{sub V}/N{sub T} in the range of 0.1 to 10. For {radical}(N{sub V}N{sub T}) less than 200, there is virtually no CPU time savings while for {radical}N{sub V}N{sub T} roughly equal to 20,000, the fast solver obtains solutions in about 1% of the time required for the direct solution technique depending somewhat upon the configuration of the vortex field and the target field.