Publications

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.