This paper presents a convergence theory for evolutionary pattern search algorithms (EPSAs). EPSAs are self-adapting evolutionary algorithms that modify the step size of the mutation operator in response to the success of previous optimization steps. Previously, the authors have proven a stationary point convergence theory for EPSAs for which the step size is not allowed to increase. The present analysis generalizes this analysis to prove a convergence theory for EPSAs that are allowed to both increase and decrease the step size. This convergence theory is based on an extension of the convergence theory for generalized pattern search methods.
This paper presents an experimental evaluation of evolutionary pattern search algorithms (EPSAs). Our experimental evaluation of EPSAs indicates that EPSAs can achieve similar performance to EAs on challenging global optimization problems. Additionally, we describe a stopping rule for EPSAs that reliably terminated them near a stationary point of the objective function. The ability for EPSAs to reliably terminate near stationary points offers a practical advantage over other EAs, which are typically stopped by heuristic stopping rules or simple bounds on the number of iterations. Our experiments also illustrate how the rate of the crossover operator can influence the tradeoff between the number of iterations before termination and the quality of the solution found by an EPSA.
Graph partitioning is an important abstraction used in solving many scientific computing problems. Unfortunately, the standard partitioning model does not incorporate considerations that are important in many settings. We address this by describing a generalized partitioning model which incorporates the notion of partition skew and is applicable to a variety of problems. We then develop enhancements to several important partitioning algorithms necessary to solve the generalized partitioning problem. Finally we demonstrate the benefit of employing several of these generalized methods to static decomposition of parallel computing problems.
Finite-difference, prestack depth migrations offers significant improvements over Kirchhoff methods in imaging near or under salt structures. We have implemented a finite-difference prestack depth migration algorithm for use on massively parallel computers which is discussed. The image quality of the finite-difference scheme has been investigated and suggested improvements are discussed.
A key to reducing the risks and costs of associated with oil and gas exploration is the fast, accurate imaging of complex geologies, such as salt domes in the Gulf of Mexico and overthrust regions in U.S. onshore regions. Pre-stack depth migration generally yields the most accurate images, and one approach to this is to solve the scalar-wave equation using finite differences. Current industry computational capabilities are insufficient for the application of finite-difference, 3-D, prestack, depth-migration algorithms. High performance computers and state-of-the-art algorithms and software are required to meet this need. As part of an ongoing ACT1 project funded by the U.S. Department of Energy, we have developed a finite-difference, 3-D prestack, depth-migration code for massively parallel computer systems. The goal of this work is to demonstrate that massively parallel computers (thousands of processors) can be used efficiently for seismic imaging, and that sufficient computing power exists (or soon will exist) to make finite-difference, prestack, depth migration practical for oil and gas exploration.
Tera Computer and Sandia National Laboratories have completed a CRADA, which examined the Tera Multi-Threaded Architecture (MTA) for use with large codes of importance to industry and DOE. The MTA is an innovative architecture that uses parallelism to mask latency between memories and processors. The physical implementation is a parallel computer with high cross-section bandwidth and GaAs processors designed by Tera, which support many small computation threads and fast, lightweight context switches between them. When any thread blocks while waiting for memory accesses to complete, another thread immediately begins execution so that high CPU utilization is maintained. The Tera MTA parallel computer has a single, global address space, which is appealing when porting existing applications to a parallel computer. This ease of porting is further enabled by compiler technology that helps break computations into parallel threads. DOE and Sandia National Laboratories were interested in working with Tera to further develop this computing concept. While Tera Computer would continue the hardware development and compiler research, Sandia National Laboratories would work with Tera to ensure that their compilers worked well with important Sandia codes, most particularly CTH, a shock physics code used for weapon safety computations. In addition to that important code, Sandia National Laboratories would complete research on a robotic path planning code, SANDROS, which is important in manufacturing applications, and would evaluate the MTA performance on this code. Finally, Sandia would work directly with Tera to develop 3D visualization codes, which would be appropriate for use with the MTA. Each of these tasks has been completed to the extent possible, given that Tera has just completed the MTA hardware. All of the CRADA work had to be done on simulators.
Networks at major computational organizations are becoming increasingly complex. The introduction of large massively parallel computers and supercomputers with gigabyte memories are requiring greater and greater bandwidth for network data transfers to widely dispersed clients. For networks to provide adequate data transfer services to high performance computers and remote users connected to them, the networking components must be optimized from a combination of internal and external performance criteria. This paper describes research done at Sandia National Laboratories to model network data services and to visualize the flow of data from source to sink when using the data services.
The Hierarchical High-Performance Storage System (HPSS) Testbed project at Sandia National Laboratories was part of a research collaboration between industry, national research centers, and national laboratories to develop mass storage system software that would scale to meet the capacity and performance required by supercomputer and massively parallel computational environments. This report describes the software that was developed within this collaboration as a result of a cooperative research and development agreement between Sandia National Laboratories and International Business Machines (IBM) Corporation, Government Systems.
The author presents a final report on a Laboratory-Directed Research and Development (LDRD) project, Innovative Computing for Diagnoses from Medical, Magnetic-Resonance Imaging, performed during fiscal years 1992 and 1993. The project defined a role for high-performance computing in surgery: the supercomputer can automatically summarize the three-dimensional extents of lesions and other clinically-relevant structures, and can deliver these summaries to workstation-based, augmented-reality environments at the clinical site. The author developed methods and software to make these summaries from the digital data already acquired using clinical, magnetic-resonance machines. In joint work with Albuquerque`s Department of Veterans Affairs Hospital, the author applied this work, and obtained a basis for planning, for rehearsal, and for guidance during surgery.
Inverse protein folding concerns the identification of an amino acid sequence that folds to a given structure. Sequence design problems attempt to avoid the apparent difficulty of inverse protein folding by defining an energy that can be minimized to find protein-like sequences. The authors evaluate the practical relevance of two sequence design problems by analyzing their computation complexity. They show that the canonical method of sequence design is intractable, and describe approximation algorithms for this problem. The authors also describe an efficient algorithm that exactly solves the grand canonical method. The analysis shows how sequence design problems can fail to reduce the difficulty of the inverse protein folding problem, and highlights the need to analyze these problems to evaluate their practical relevance.
A discrete element computer program named DMC{_}BLAST (Distinct Motion Code) has been under development since 1987 for modeling rock blasting. This program employs explicit time integration and uses spherical or cylindrical elements that are represented as circles in 2-D. DMC{_}BLAST calculations compare favorably with data from actual bench blasts. The blast modeling capabilities of DMC{_}BLAST have been expanded to include independently dipping geologic layers, top surface, bottom surface and pit floor. The pit can also now be defined using coordinates based on the toe of the bench. A method for modeling decked explosives has been developed which allows accurate treatment of the inert materials (stemming) in the explosive column and approximate treatment of different explosives in the same blasthole. A DMC{_}BLAST user can specify decking through a specific geologic layer with either inert material or a different explosive. Another new feature of DMC{_}BLAST is specification of an uplift angle which is the angle between the normal to the blasthole and a vector defining the direction of explosive loading on particles adjacent to the blasthole. A buffer (choke) blast capability has been added for situations where previously blasted material is adjacent to the free face of the bench preventing any significant lateral motion during the blast.
For the past few years, the Minnesota Department of Corrections, assisted by Sandia National Laboratories, has developed a set of standards for perimeter security at medium, close, and maximum custody correctional facilities in the state. During this process, the threat to perimeter security was examined and concepts about correctional perimeter security were developed. This presentation and paper will review the outcomes of this effort, some of the lessons learned, and the concepts developed during this process and in the course of working with architects, engineers and construction firms as the state upgraded perimeter security at some facilities and planned new construction at other facilities.
A mathematical framework is developed for the study of materials containing axisymmetric inclusions or flaws such as ellipsoidal voids, penny-shaped cracks, or fibers of circular cross-section. The general case of nonuniform statistical distributions of such heterogeneities is attacked by first considering a spatially uniform distribution of flaws that are all oriented in the same direction. Assuming an isotropic substrate, the macroscopic material properties of this simpler microstructure naturally should be transversely isotropic. An orthogonal basis for the linear subspace consisting of all double-symmetric transversely-isotropic fourth-order tensors associated with a given material vector is applied to deduce the explicit functional dependence of the material properties of these aligned materials on the shared symmetry axis. The aligned and uniform microstructure seems geometrically simple enough that the macroscopic transversely isotropic properties could be derived in closed form. Since the resulting properties are transversely isotropic, the analyst must therefore be able to identify the appropriate coefficients of the transverse basis. Once these functions are identified, a principle of superposition of strain rates ay be applied to define an expectation integral for the composite properties of a material containing arbitrary anisotropic distributions of axisymmetric inhomogeneities. A proposal for coupling plastic anisotropy to the elastic anisotropy is presented in which the composite yield surface is interpreted as a distortion of the isotropic substrate yield surface; the distortion directions are coupled to the elastic anisotropy directions. Finally, some commonly assumed properties (such as major symmetry) of the Cauchy tangent stiffness tensor are shown to be inappropriate for large distortions of anisotropic materials.
Consider mapping a regular i x j quadrilateral mesh of a rectangle onto a surface. The quality of the mapped mesh of the surface depends heavily on which vertices of the surface correspond to corners of the rectangle. The authors problem is, given an n-sided surface, chose as corners four vertices such that the surface resembles a rectangle with corners at those vertices. Note that n could be quite large, and the length and width of the rectangle, i and j, are not prespecified. In general, there is either a goal number or a prescribed number of mesh edges for each bounding curve of the surface. The goals affect the quality of the mesh, and the prescribed edges may make finding a feasible set of corners difficult. The algorithm need only work for surfaces that are roughly rectangular, particular those without large reflex angles, as otherwise an unstructured meshing algorithm is used instead. The authors report on the theory and implementation of algorithms for this problem. They also given an overview of a solution to a related problem called interval assignment: given a complex of surfaces sharing curves, globally assign the number of mesh edges or intervals for each curve such that it is possible to mesh each surface according to its prescribed quadrilateral meshing algorithm, and assigned and user-prescribed boundary mesh edges and corners. They also note a practical, constructive technique that relies on interval assignment that can generate a quadrilateral mesh of a complex of surfaces such that a compatible hexahedral mesh of the enclosed volume exists.
In this work, high-energy electron beam brazing of a ceramic part is modeled numerically. The part considered consists of a ceramic cylinder and disk between which is sandwiched an annular washer of braze material. An electron beam impinges on the disk, melting the braze metal. The resulting coupled electron-photon and thermal transport equations are solved using Monte Carlo and finite element techniques respectively. Results indicate that increased electron beam current decreases the time required to melt the braze while increasing temperature gradients in the ceramic near the braze. Furnace brazing was also simulated and predicted results indicate increased processing times relative to electron beam brazing.
This research project used Pad++, a user interface originally developed by Jim Holland. The objective was to explore the utility of that user interface to large databases of information such as those found on the World Wide Web. A web browser based on Pad++ was developed in the first year of this project The first year results, including the human factors were documented in a video and were presented at a SNL-wide seminar. The second year of this research project focused on applying the results of the first year research. The work in the second year involves using Pad++ as a basis for tools to manage large complicated web sites. Pad++ is ideally suited to this complex activity. A prototype was developed, which presents Web relationships in 3D hyperspace, following research from the Geometry Center at the University of Minnesota. Various human factors studies were completed, which indicate Pad++ web browsers allow users to comprehend 23% faster than when using Netscape.
The corrections system in the U.S. is supervising over five million offenders. This number is rising fast and so are the direct and indirect costs to society. To improve supervision and reduce the cost of parole and probation, first generation home arrest systems were introduced in 1987. While these systems proved to be helpful to the corrections system, their scope is rather limited because they only cover an offender at a single location and provide only a partial time coverage. To correct the limitations of first-generation systems, second-generation wide area continuous electronic offender monitoring systems, designed to monitor the offender at all times and locations, are now on the drawing board. These systems use radio frequency location technology to track the position of offenders. The challenge for this technology is the development of reliable personal locator devices that are small, lightweight, with long operational battery life, and indoors/outdoors accuracy of 100 meters or less. At the center of a second-generation system is a database that specifies the offender`s home, workplace, commute, and time the offender should be found in each. The database could also define areas from which the offender is excluded. To test compliance, the system would compare the observed coordinates of the offender with the stored location for a given time interval. Database logfiles will also enable law enforcement to determine if a monitored offender was present at a crime scene and thus include or exclude the offender as a potential suspect.
This report presents, Aspen. Sandia National Laboratories is developing this new agent-based microeconomic simulation model of the U.S. economy. The model is notable because it allows a large number of individual economic agents to be modeled at a high level of detail and with a great degree of freedom. Some features of Aspen are (a) a sophisticated message-passing system that allows individual pairs of agents to communicate, (b) the use of genetic algorithms to simulate the learning of certain agents, and (c) a detailed financial sector that includes a banking system and a bond market. Results from runs of the model are also presented.
Findings from a four-year study by an international benchmarking group in the comparison of computational methods for evaluating burnup credit in criticality safety analyses are presented in this paper. Approximately 20 participants from 11 countries have provided results for most problems. Four detailed benchmark problems for Pressurized Water Reactor (PWR) fuel have been completed and are summarized in this paper. Preliminary results from current work addressing burnup credit for Boiling Water Reactor (BWR) fuel will also be discussed as well as planned activities for additional benchmarks including Mixed-Oxide (MOX) fuels, subcritical benchmarks, international databases, and other activities.
Transient dynamics simulations are commonly used to model phenomena such as car crashes, underwater explosions, and the response of shipping containers to high-speed impacts. Physical objects in such a simulation are typically represented by Lagrangian meshes because the meshes can move and deform with the objects as they undergo stress. Fluids (gasoline, water) or fluid-like materials (earth) in the simulation can be modeled using the techniques of smoothed particle hydrodynamics. Implementing a hybrid mesh/particle model on a massively parallel computer poses several difficult challenges. One challenge is to simultaneously parallelize and load-balance both the mesh and particle portions of the computation. A second challenge is to efficiently detect the contacts that occur within the deforming mesh and between mesh elements and particles as the simulation proceeds. These contacts impart forces to the mesh elements and particles which must be computed at each timestep to accurately capture the physics of interest. In this paper we describe new parallel algorithms for smoothed particle hydrodynamics and contact detection which turn out to have several key features in common. Additionally, we describe how to join the new algorithms with traditional parallel finite element techniques to create an integrated particle/mesh transient dynamics simulation. Our approach to this problem differs from previous work in that we use three different parallel decompositions, a static one for the finite element analysis and dynamic ones for particles and for contact detection. We have implemented our ideas in a parallel version of the transient dynamics code PRONTO-3D and present results for the code running on a large Intel Paragon.
This manual describes the use of MPSalsa, an unstructured finite element (FE) code for solving chemically reacting flow problems on massively parallel computers. MPSalsa has been written to enable the rigorous modeling of the complex geometry and physics found in engineering systems that exhibit coupled fluid flow, heat transfer, mass transfer, and detailed reactions. In addition, considerable effort has been made to ensure that the code makes efficient use of the computational resources of massively parallel (MP), distributed memory architectures in a way that is nearly transparent to the user. The result is the ability to simultaneously model both three-dimensional geometries and flow as well as detailed reaction chemistry in a timely manner on MT computers, an ability we believe to be unique. MPSalsa has been designed to allow the experienced researcher considerable flexibility in modeling a system. Any combination of the momentum equations, energy balance, and an arbitrary number of species mass balances can be solved. The physical and transport properties can be specified as constants, as functions, or taken from the Chemkin library and associated database. Any of the standard set of boundary conditions and source terms can be adapted by writing user functions, for which templates and examples exist.
This paper considers the protein structure prediction problem for lattice and off-lattice protein folding models that explicitly represent side chains. Lattice models of proteins have proven extremely useful tools for reasoning about protein folding in unrestricted continuous space through analogy. This paper provides the first illustration of how rigorous algorithmic analyses of lattice models can lead to rigorous algorithmic analyses of off-lattice models. The authors consider two side chain models: a lattice model that generalizes the HP model (Dill 85) to explicitly represent side chains on the cubic lattice, and a new off-lattice model, the HP Tangent Spheres Side Chain model (HP-TSSC), that generalizes this model further by representing the backbone and side chains of proteins with tangent spheres. They describe algorithms for both of these models with mathematically guaranteed error bounds. In particular, the authors describe a linear time performance guaranteed approximation algorithm for the HP side chain model that constructs conformations whose energy is better than 865 of optimal in a face centered cubic lattice, and they demonstrate how this provides a 70% performance guarantee for the HP-TSSC model. This is the first algorithm in the literature for off-lattice protein structure prediction that has a rigorous performance guarantee. The analysis of the HP-TSSC model builds off of the work of Dancik and Hannenhalli who have developed a 16/30 approximation algorithm for the HP model on the hexagonal close packed lattice. Further, the analysis provides a mathematical methodology for transferring performance guarantees on lattices to off-lattice models. These results partially answer the open question of Karplus et al. concerning the complexity of protein folding models that include side chains.
A set of model interface guidelines, called MIG, is presented as a means by which any compliant numerical material model can be rapidly installed into any parent code without having to modify the model subroutines. Here, {open_quotes}model{close_quotes} usually means a material model such as one that computes stress as a function of strain, though the term may be extended to any numerical operation. {open_quotes}Parent code{close_quotes} means a hydrocode, finite element code, etc. which uses the model and enforces, say, the fundamental laws of motion and thermodynamics. MIG requires the model developer (who creates the model package) to specify model needs in a standardized but flexible way. MIG includes a dictionary of technical terms that allows developers and parent code architects to share a common vocabulary when specifying field variables. For portability, database management is the responsibility of the parent code. Input/output occurs via structured calling arguments. As much model information as possible (such as the lists of required inputs, as well as lists of precharacterized material data and special needs) is supplied by the model developer in an ASCII text file. Every MIG-compliant model also has three required subroutines to check data, to request extra field variables, and to perform model physics. To date, the MIG scheme has proven flexible in beta installations of a simple yield model, plus a more complicated viscodamage yield model, three electromechanical models, and a complicated anisotropic microcrack constitutive model. The MIG yield model has been successfully installed using identical subroutines in three vectorized parent codes and one parallel C++ code, all predicting comparable results. By maintaining one model for many codes, MIG facilitates code-to-code comparisons and reduces duplication of effort, thereby reducing the cost of installing and sharing models in diverse new codes.
A unifying framework is developed for the analysis of brittle materials. Heretofore diverse classes of models result from different choices for unspecified coefficient and distribution functions in the unified theory. Material response is described in terms of expectation integrals of transverse symmetry tensors. First, a canonical body containing cracks of all the same orientation is argued to possess macroscopic transverse isotropy. An orthogonal basis for the linear subspace consisting of all double-symmetric transversely-isotropic fourth-order tensors associated with a given material vector is introduced and applied to deduce the explicit functional dependence of the compliance of such contrived materials on the shared crack orientation. A principle of superposition of strain rates is used to write the compliance for a more realistic material consisting of cracks of random size and orientation as an expectation integral of the transverse compliance for each orientation times the joint distribution function for the size and orientation. Utilizing an evolving (initially exponential) size- dependence in the joint distribution, the general theory gives unprecedented agreement with measurements of the dynamic response of alumina to impact loading, especially upon release where the calculations predict the development of considerable deformation- induced anisotropy, challenging the conventional notion of shocks as isotropic phenomena.
This paper describes the design, implementation and performance of a port of the Argonne National Laboratory/Mississippi State University MPICH implementation of the Message Passing Interface standard to the Cray T3D massively parallel processing system. A description of the factors influencing the design and the various stages of implementation are presented. Performance results revealing superior bandwidth and comparable latency as compared to other full message passing systems on the T3D are shown. Further planned improvements and optimizations, including an analysis of a port to the T3E, are mentioned.
As the successor to SUNMOS [8], the Puma operating system provides a flexible, lightweight, high performance message passing environment for massively parallel computers. Message passing in Puma is accomplished through the use of a new mechanism known as a portal. Puma is currently running on the Intel Paragon and is being developed for the Intel TeraFLOPS machine. In this paper we discuss issues regarding the development of the Argonne National Laboratory/Mississippi State University implementation of the Message Passing Interface standard on top of portals. Included is a description of the design and implementation for both MPI point-to- point and collective communications, and MPI-2 one-sided communications.
An analytical and experimental study is conducted to investigate the effect of isolator locations on the effectiveness of vibration isolation systems. The study uses isolators with fixed properties and evaluates potential improvements to the isolation system that can be achieved by optimizing isolator locations. Because the available locations for the isolators are discrete in this application, a Genetic Algorithm (GA) is used as the optimization method. The system is modeled in MATLAB{trademark} and coupled with the GA available in the DAKOTA optimization toolkit under development at Sandia National Laboratories. Design constraints dictated by hardware and experimental limitations are implemented through penalty function techniques. A series of GA runs reveal difficulties in the search on this heavily constrained, multimodal, discrete problem. However, the GA runs provide a variety of optimized designs with predicted performance from 30 to 70 times better than a baseline configuration. An alternate approach is also tested on this problem: it uses continuous optimization, followed by rounding of the solution to neighboring discrete configurations. Results show that this approach leads to either infeasible or poor designs. Finally, a number of optimized designs obtained from the GA searches are tested in the laboratory and compared to the baseline design. These experimental results show a 7 to 46 times improvement in vibration isolation from the baseline configuration.
The theoretical background for the finite element computer program, MPSalsa, is presented in detail. MPSalsa is designed to solve laminar, low Mach number, two- or three-dimensional incompressible and variable density reacting fluid flows on massively parallel computers, using a Petrov-Galerkin finite element formulation. The code has the capability to solve coupled fluid flow, heat transport, multicomponent species transport, and finite-rate chemical reactions, and to solver coupled multiple Poisson or advection-diffusion- reaction equations. The program employs the CHEMKIN library to provide a rigorous treatment of multicomponent ideal gas kinetics and transport. Chemical reactions occurring in the gas phase and on surfaces are treated by calls to CHEMKIN and SURFACE CHEMKIN, respectively. The code employs unstructured meshes, using the EXODUS II finite element data base suite of programs for its input and output files. MPSalsa solves both transient and steady flows by using fully implicit time integration, an inexact Newton method and iterative solvers based on preconditioned Krylov methods as implemented in the Aztec solver library.
In finite-element, transient dynamics simulations, physical objects are typically modeled as Lagrangian meshes because the meshes can move and deform with the objects as they undergo stress. In many simulations, such as computations of impacts or explosions, portions of the deforming mesh come in contact with each other as the simulation progresses. These contacts must be detected and the forces they impart to the mesh must be computed at each timestep to accurately capture the physics of interest. While the finite-element portion of these computations is readily parallelized, the contact detection problem is difficult to implement efficiently on parallel computers and has been a bottleneck to achieving high performance on large parallel machines. In this paper we describe a new parallel algorithm for detecting contacts. Our approach differs from previous work in that we use two different parallel decompositions, a static one for the finite element analysis and dynamic one for contact detection. We present results for this algorithm in a parallel version of the transient dynamics code PRONTO-3D running on a large Intel Paragon.
Fast, accurate imaging of complex, oil-bearing geologies, such as overthrusts and salt domes, is the key to reducing the costs of domestic oil and gas exploration. Geophysicists say that the known oil reserves in the Gulf of Mexico could be significantly increased if accurate seismic imaging beneath salt domes was possible. A range of techniques exist for imaging these regions, but the highly accurate techniques involve the solution of the wave equation and are characterized by large data sets and large computational demands. Massively parallel computers can provide the computational power for these highly accurate imaging techniques. A brief introduction to seismic processing will be presented, and the implementation of a seismic-imaging code for distributed memory computers will be discussed. The portable code, Salvo, performs a wave equation-based, 3-D, prestack, depth imaging and currently runs on the Intel Paragon and the Cray T3D. It used MPI for portability, and has sustained 22 Mflops/sec/proc (compiled FORTRAN) on the Intel Paragon.
The transient dynamics finite element computer program, PRONTO-3D, has been used in conjunction with a damage constitutive model to study the influence of detonation timing on rock fragmentation during blasting. The primary motivation of this study is to investigate the effectiveness of precise detonators in improving fragmentation. PRONTO-3D simulations show that a delay time of 0.0 sec between adjacent blastholes results in significantly more fragmentation than a 0.5 ms delay.
This report describes the development of an agent-based microanalytic simulation model of the US economy. The microsimulation model capitalizes on recent technological advances in evolutionary learning and parallel computing. Results are reported for a test problem that was run using the model. The test results demonstrate the model`s ability to predict business-like cycles in an economy where prices and inventories are allowed to vary. Since most economic forecasting models have difficulty predicting any kind of cyclic behavior. These results show the potential of microanalytic simulation models to improve economic policy analysis and to provide new insights into underlying economic principles. Work already has begun on a more detailed model.
In this paper, a review of the Spatial Twist Contiuum and the basic whisker weaving algorithm are given. Progress in the detection and resolution of several types of degeneracies formed by whisker weaving are discussed. These examples include so-called knife doublets, triple doublets, through-cells and through-chords. Knife doublets and triple doublets are resolved by preventing their formation a-priori, which forces whisker weaving to remove the element(s) causing the degeneracy. Through-chords and through-cells are left in the weave and resolved after the weave has been closed. The paper concludes with three examples of geometries ``closed`` by whisker weaving.
This work gives a proof of convergence for a randomized learning algorithm that describes how anoles (lizards found in the Carribean) learn a foraging threshold distance. This model assumes that an anole will pursue a prey if and only if it is within this threshold of the anole`s perch. This learning algorithm was proposed by the biologist Roughgarden and his colleagues. They experimentally confirmed that this algorithm quickly converges to the foraging threshold that is predicted by optimal foraging theory our analysis provides an analytic confirmation that the learning algorithm converses to this optimal foraging threshold with high probability.
Crystal lattices are infinite periodic graphs that occur naturally in a variety of geometries and which are of fundamental importance in polymer science. Discrete models of protein folding use crystal lattices to define the space of protein conformations. Because various crystal lattices provide discretizations of the same physical phenomenon, it is reasonable to expect that there will exist "invariants" across lattices that define fundamental properties of the protein folding process; an invariant defines a property that transcends particular lattice formulations. This paper identifies two classes of invariants, defined in terms of sublattices that are related to the design of algorithms for the structure prediction problem. The first class of invariants is used to define a master approximation algorithm for which provable performance guarantees exist. This algorithm can be applied to generalizations of the hydrophobic-hydrophilic model that have lattices other than the cubic lattice, including most of the crystal lattices commonly used in protein folding lattice models. The second class of invariants applies to a related lattice model. Using these invariants, we show that for this model the structure prediction problem is intractable across a variety of threedimensional lattices. It turns out that these two classes of invariants are respectively sublattices of the two-and three-dimensional square lattice. As the square lattices are the standard lattices used in empirical protein folding studies, our results provide a rigorous confirmation of the ability of these lattices to provide insight into biological phenomenon. Our results are the first in the literature that identify algorithmic paradigms for the protein structure prediction problem that transcend particular lattice formulations.
Terminal propagation is a method developed in the circuit placement community for adding constraints to graph partitioning problems. This paper adapts and expands this idea, and applies it to the problem of partitioning data structures among the processors of a parallel computer. We show how the constraints in terminal propagation can be used to encourage partitions in which messages are communicated only between architecturally near processors. We then show how these constraints can be handled in two important partitioning algorithms, spectral bisection and multilevel-KL. We compare the quality of partitions generated by these algorithms to each other and to Partitions generated by more familiar techniques.
Crystal lattices are infinite periodic graphs that occur naturally in a variety of geometries and which are of fundamental importance in polymer science. Discrete models of protein folding use crystal lattices to define the space of protein conformations. Because various crystal lattices provide discretizations of the same physical phenomenon, it is reasonable to expect that there will exist ``invariants`` across lattices that define fundamental properties of protein folding process; an invariant defines a property that transcends particular lattice formulations. This paper identifies two classes of invariants, defined in terms of sublattices that are related to the design of algorithms for the structure prediction problem. The first class of invariants is, used to define a master approximation algorithm for which provable performance guarantees exist. This algorithm can be applied to generalizations of the hydrophobic-hydrophilic model that have lattices other than the cubic lattice, including most of the crystal lattices commonly used in protein folding lattice models. The second class of invariants applies to a related lattice model. Using these invariants, we show that for this model the structure prediction problem is intractable across a variety of three-dimensional lattices. It`` turns out that these two classes of invariants are respectively sublattices of the two- and three-dimensional square lattice. As the square lattices are the standard lattices used in empirical protein folding` studies, our results provide a rigorous confirmation of the ability of these lattices to provide insight into biological phenomenon. Our results are the first in the literature that identify algorithmic paradigms for the protein structure prediction problem which transcend particular lattice formulations.
A number of physics problems can be modeled by a set of N elements which have pair-wise interactions with one another. A direct solution technique requires computational effort which is O(N{sup 2}). Fast multipole methods (FMM) have been widely used in recent years to obtain solutions to these problems requiring a computational effort of only 0 (N lnN) or O (N). In this paper we present an overview of several variations of the fast multipole method along with examples of its use in solving a variety of physical problems.
In this report, we present a simple and somewhat preliminary numerical model of a sinusoidal lobed injector. The lobed (corrugated) injector is being considered by several investigators as a potentially efficient device to mix fuel and air for combustion purposes. In this configuration, air flows parallel to the troughs and valleys of corrugations which grow in amplitude in the stream-wise direction. These ramped corrugations produce stream-wise vortices which enhance the downstream mixing. For the lobed injector, the corrugations are actually double walled which allows one to inject fuel through the space between them into the flow downstream of the ramp. The simulation model presented herein is based on a vorticity formulation of the Navier-Stokes equations and is solved using an unsteady viscous vortex method. In order to demonstrate the utility of this method we have simulated the three-dimensional cold mixing process for injection of methane gas into air. The vorticity and fuel concentration field downstream of the injector are simulated for two different injector geometries. We observe from these two simulations that variation of the amplitude of the corrugations can be used to achieve considerably different mixing patterns downstream of the injector.
Occasionally one may be confronted by a hexahedral or quadrilateral mesh containing doublets, two faces sharing two edges. In this case, no amount of smoothing will produce a mesh with agreeable element quality: in the planar case, one of these two faces will always have an angle of at least 180 degrees between the two edges. The authors describe a robust scheme for refining a hexahedral or quadrilateral mesh to separate such faces, so that any two faces share at most one edge. Note that this also ensures that two hexahedra share at most one face in the three dimensional case. The authors have implemented this algorithm and incorporated it into the CUBIT mesh generation environment developed at Sandia National Laboratories.
This paper describes the techniques used to resolve invalid connectivity created as a natural part of the whisker weaving algorithm. These techniques rely on the detection of {open_quotes}repeated hexes{close_quotes} in the STC data, which indicate face pairs which share two edges. The {open_quotes}repeated hex{close_quotes} case is described in detail, including the resolution technique by which a self-intersecting whisker sheet with two independent face loops are created. The algorithm used to construct the primal of an all-hexahedral mesh (i.e. the actual nodes and hex elements) from the connectivity data contained in the STC is also described. The primal is constructed using a {open_quotes}gift-wrapping{close_quotes} algorithm, where all the mesh edges and hexes containing a particular node are found by traversing between hexes already known to share the node. This algorithm is implemented inside the CUBIT code and is used to generate meshes for several example problems.
Aztec is an iterative library that greatly simplifies the parallelization process when solving the linear systems of equations Ax = b where A is a user supplied n x n sparse matrix, b is a user supplied vector of length n and x is a vector of length n to be computed. Aztec is intended as a software tool for users who want to avoid cumbersome parallel programming details but who have large sparse linear systems which require an efficiently utilized parallel processing system. A collection of data transformation tools are provided that allow for easy creation of distributed sparse unstructured matrices for parallel solution. Once the distributed matrix is created, computation can be performed on any of the parallel machines running Aztec: nCUBE 2, IBM SP2 and Intel Paragon, MPI platforms as well as standard serial and vector platforms. Aztec includes a number of Krylov iterative methods such as conjugate gradient (CG), generalized minimum residual (GMRES) and stabilized biconjugate gradient (BICGSTAB) to solve systems of equations. These Krylov methods are used in conjunction with various preconditioners such as polynomial or domain decomposition methods using LU or incomplete LU factorizations within subdomains. Although the matrix A can be general, the package has been designed for matrices arising from the approximation of partial differential equations (PDEs). In particular, the Aztec package is oriented toward systems arising from PDE applications.
This paper defines a class of evolutionary algorithms called evolutionary pattern search algorithms (EPSAs) and analyzes their convergence properties. This class of algorithms is closely related to evolutionary programming, evolutionary strategie and real-coded genetic algorithms. EPSAs are self-adapting systems that modify the step size of the mutation operator in response to the success of previous optimization steps. The rule used to adapt the step size can be used to provide a stationary point convergence theory for EPSAs on any continuous function. This convergence theory is based on an extension of the convergence theory for generalized pattern search methods. An experimental analysis of the performance of EPSAs demonstrates that these algorithms can perform a level of global search that is comparable to that of canonical EAs. We also describe a stopping rule for EPSAs, which reliably terminated near stationary points in our experiments. This is the first stopping rule for any class of EAs that can terminate at a given distance from stationary points.
This paper examines the effects of relaxed synchronization on both the numerical and parallel efficiency of parallel genetic algorithms (GAs). We describe a coarse-grain geographically structured parallel genetic algorithm. Our experiments show that asynchronous versions of these algorithms have a lower run time than-synchronous GAs. Furthermore, we demonstrate that this improvement in performance is partly due to the fact that the numerical efficiency of the asynchronous genetic algorithm is better than the synchronous genetic algorithm. Our analysis includes a critique of the utility of traditional parallel performance measures for parallel GAs, and we evaluate the claims made by several researchers that parallel GAs can have superlinear speedup.
A popular three-dimensional mesh generation scheme is to start with a quadrilateral of the surface of a volume, and then attempt to fill the interior of volume with hexahedra, so that the hexahedra touch the surface in exactly the given quadrilaterals. Folklore has maintained that there are many quadrilateral meshes for which no such compatible hexahedral mesh exists. In this paper we give an existence proof which contradicts this folklore: A quadrilateral mesh need only satisfy some very weak conditions for there to exist a compatible hexahedral mesh. For a volume that is topologically a ball, any quadrilateral mesh composed of an even number of quadrilaterals admits a compatible hexahedral mesh. We extend this to volumes of higher genus: There is a construction to reduce to the ball case if and only if certain cycles of edges are even.
This paper theoretically compares the performance of simulated annealing and evolutionary algorithms. Our main result is that under mild conditions a wide variety of evolutionary algorithms can be shown to have greater performance than simulated annealing after a sufficiently large number of function evaluations. This class of EAs includes variants of evolutionary strategie and evolutionary programming, the canonical genetic algorithm, as well as a variety of genetic algorithms that have been applied to combinatorial optimization problems. The proof of this result is based on a performance analysis of a very general class of stochastic optimization algorithms, which has implications for the performance of a variety of other optimization algorithm.
Adaptive finite element analysis demands a great deal of computational resources, and as such is most appropriately solved in a massively parallel computer environment. This analysis will require other parallel algorithms before it can fully utilize MP computers, one of which is parallel adaptive meshing. A version of the paving algorithm is being designed which operates in parallel but which also retains the robustness and other desirable features present in the serial algorithm. Adaptive paving in a production mode is demonstrated using a Babuska-Rheinboldt error estimator on a classic linearly elastic plate problem. The design of the parallel paving algorithm is described, and is based on the decomposition of a surface into {open_quotes}virtual{close_quotes} surfaces. The topology of the virtual surface boundaries is defined using mesh entities (mesh nodes and edges) so as to allow movement of these boundaries with smoothing and other operations. This arrangement allows the use of the standard paving algorithm on subdomain interiors, after the negotiation of the boundary mesh.
The criminal justice projects at SNL include three projects for the National Institute of Justice (smart gun, restraining foam, aqueous foam, corrections perimeter), a Southwest Border study, and one involving corrections agencies. It is concluded that the national technologies developed to protect nuclear and other high value assets have enormous potential for application to crime and personal safety; the difficulty lies in simplifying the technology transfer and making the new systems affordable.
A Discrete element computer program named DMC (Distinct Motion Code) has been developed for modeling rock blasting. This program employs explicit time integration and uses spherical or cylindrical elements which are represented as circles in 2-D. DMC calculations have been compared with measurements on bench blasts in the field with relatively good comparison. Structural rock mass characteristics have a significant impact on any blast and DMC has not, until now, included these effects. This paper discusses a recently added DMC capability for treating joints and bedding planes in bench blast simulations. Material strength is treated in DMC by creating links between spheres to hold them together. The links can be broken based on any criterion; simple tension, compression and shear are currently employed. Joint sets are treated in DMC by defining the dip of each set toward or away from the bench face along with the joint spacing. Strength links that cross joint planes can have their strength properties modified or they can be deleted. Modification of the link patterns based on joint sets creates distinct blocks of spheres outlined by the intersecting joints. These blocks of spheres move together as a solid unit unless stress and strain conditions within the block indicate that links should be broken. Simulations using this capability show some blocks remaining intact throughout the blast and some being partially or completely broken. When this occurs, the joint pattern is shown to influence the characteristics of the blast. Upon completion of this capability both rock breakage and motion will be modeled during the same simulation. Much work remains to be done on this concept making this paper a progress report on the development of this new capability.
