Publications

Finding a q{sup th} root in GF(p), where p and q are prunes, q is large and q{sup 2} divides (p{minus}1) is a difficult problem equivalent to the discrete logarithm problem using an element of order q as the base. This paper describes an authenticated key exchange algorithm utilizing this hard problem.

Several concepts (and assumptions) from the literature for porous metals and ceramics have been synthesized into a consistent model that predicts an admissibility limit on a material's porous yield surface. To ensure positive plastic work, the rate at which a yield surface can collapse as pores grow in tension must be constrained.

A co-simulation tool based on finite element principles has been developed to solve coupled electrostatic-structural problems. An automated mesh morphing algorithm has been employed to update the field mesh after structural deformation. The co-simulation tool has been successfully applied to the hysteric behavior of a MEMS switch.

The conventional approach to treat charged defects in extended systems in first principles calculations is via the supercell approximation using a neutralizing jellium charge. I explicitly show that errors in the resulting electrostatic potential surface are comparable to a band gap energy in semiconductors, for cell sizes typically used in simulations. I present a method for eliminating divergence of the Coulomb potential in charged supercell calculations that correctly treats the electrostatic potential in the local vicinity of a charged defect, via a mixed boundary condition approach. © 2000 The American Physical Society.

Much progress has been made through these years to achieve automatic hexahedral mesh generation. While general meshing algorithms that can take on general geometry are not there yet; many well-proven automatic meshing algorithms now work on certain classes of geometry. This paper presents a feature based volume decomposition approach for automatic Hexahedral Mesh generation. In this approach, feature recognition techniques are introduced to determine decomposition features from a CAD model. The features are then decomposed and mapped with appropriate automatic meshing algorithms suitable for the correspondent geometry. Thus a formerly unmeshable CAD model may become meshable. The procedure of feature decomposition is recursive: sub-models are further decomposed until either they are matched with appropriate meshing algorithms or no more decomposition features are detected. The feature recognition methods employed are convexity based and use topology and geometry information, which is generally available in BREP solid models. The operations of volume decomposition are also detailed in the paper. The final section, the capability of the feature decomposer is demonstrated over some complicated manufactured parts.

The finite element method is being used today to model component assemblies in a wide variety of application areas, including structural mechanics, fluid simulations, and others. Generating hexahedral meshes for these assemblies usually requires the use of geometry decomposition, with different meshing algorithms applied to different regions. While the primary motivation for this approach remains the lack of an automatic, reliable all-hexahedral meshing algorithm, requirements in mesh quality and mesh configuration for typical analyses are also factors. For these reasons, this approach is also sometimes required when producing other types of unstructured meshes. This paper will review progress to date in automating many parts of the hex meshing process, which has halved the time to produce all-hex meshes for large assemblies. Particular issues which have been exposed due to this progress will also be discussed, along with their applicability to the general unstructured meshing problem.

In the last decade there has been interest and research in the area of designing circuits with genetic algorithms, evolutionary algorithms, and genetic programming. However, the ability to design circuits of the size and complexity required by modern engineering design problems, simply by specifying required outputs for given inputs has as yet eluded researchers. This paper describes current research in the area of designing logic circuits using an evolutionary algorithm. The goal of the research is to improve the effectiveness of this method and make it a practical aid for design engineers. A novel method of implementing the algorithm is introduced, and results are presented for various multiprocessing systems. In addition to evolving standard arithmetic circuits, work in the area of evolving circuits that perform digital signal processing tasks is described.

The void percolation threshold is calculated for a distribution of overlapping spheres with equal radii, and for a binary sized distribution of overlapping spheres, where half of the spheres have radii twice as large as the other half. Using systems much larger than previous work, the authors determine a much more precise value for the percolation thresholds and correlation length exponent. The values for the percolation thresholds are shown to be significantly different, in contrast with previous, less precise works that speculated that the threshold might be universal with respect to sphere size distribution.

The authors present a new technique for the design of approximation algorithms that can be viewed as a generalization of randomized rounding. They derive new or improved approximation guarantees for a class of generalized congestion problems such as multicast congestion, multiple TSP etc. Their main mathematical tool is a structural decomposition theorem related to the integrality gap of a relaxation.

In this paper the authors present performance results from several parallel benchmarks and applications on a 400-node Linux cluster at Sandia National Laboratories. They compare the results on the Linux cluster to performance obtained on a traditional distributed-memory massively parallel processing machine, the Intel TeraFLOPS. They discuss the characteristics of these machines that influence the performance results and identify the key components of the system software that they feel are important to allow for scalability of commodity-based PC clusters to hundreds and possibly thousands of processors.

The Reproducing Kernel Particle Method (RKPM) is a discretization technique for partial differential equations that uses the method of weighted residuals, classical reproducing kernel theory and modified kernels to produce either ``mesh-free'' or ``mesh-full'' methods. Although RKPM has many appealing attributes, the method is new, and its numerical performance is just beginning to be quantified. In order to address the numerical performance of RKPM, von Neumann analysis is performed for semi-discretizations of three model one-dimensional PDEs. The von Neumann analyses results are used to examine the global and asymptotic behavior of the semi-discretizations. The model PDEs considered for this analysis include the parabolic and hyperbolic (first and second-order wave) equations. Numerical diffusivity for the former and phase speed for the later are presented over the range of discrete wavenumbers and in an asymptotic sense as the particle spacing tends to zero. Group speed is also presented for the hyperbolic problems. Excellent diffusive and dispersive characteristics are observed when a consistent mass matrix formulation is used with the proper choice of refinement parameter. In contrast, the row-sum lumped mass matrix formulation severely degraded performance. The asymptotic analysis indicates that very good rates of convergence are possible when the consistent mass matrix formulation is used with an appropriate choice of refinement parameter.

The design of general-purpose dynamic load-balancing tools for parallel applications is more challenging than the design of static partitioning tools. Both algorithmic and software engineering issues arise. We have addressed many of these issues in the design of the Zoltan dynamic load-balancing library. Zoltan has an object-oriented interface that makes it easy to use and provides separation between the application and the load-balancing algorithms. It contains a suite of dynamic load-balancing algorithms, including both geometric and graph-based algorithms. Its design makes it valuable both as a partitioning tool for a variety of applications and as a research test-bed for new algorithmic development. In this paper, we describe Zoltan's design and demonstrate its use in an unstructured-mesh finite element application.

Laser deposits fabricated from two different compositions of 304L stainless steel powder were characterized to determine the nature of the solidification and solid state transformations. One of the goals of this work was to determine to what extent novel microstructures consisting of single-phase austenite could be achieved with the thermal conditions of the LENS process. Although ferrite-free deposits were not obtained, structures with very low ferrite content were achieved. It appeared that, with slight changes in alloy composition, this goal could be met via two different solidification and transformation mechanisms.

Effective use of a parallel computer requires that a calculation be carefully divided among the processors. This load balancing problem appears in many guises and has been a fervent area of research for the past decade or more. Although great progress has been made, and useful software tools developed, a number of challenges remain. It is the conviction of the author that these challenges will be easier to address if we first come to terms with some significant shortcomings in our current perspectives. This paper tries to identify several areas in which the prevailing point of view is either mistaken or insufficient. The goal is to motivate new ideas and directions for this important field. © 2000 Elsevier Science Inc.

This paper presents an investigation of a technique for using two-dimensional bodies composed of simple polygons with a body-decoupled uniform Cartesian grid in the Direct Simulation Monte Carlo method (DSMC). The method employs an automated grid preprocessing scheme beginning from a CAD geometry definition file, and is based on polygon triangulation using a trapezoid algorithm. A particle-body intersection time comparison is presented between the Icarus DSMC code using a body-fitted structured grid, and using a structured body-decoupled Cartesian grid with both linear and logarithmic search techniques. A comparison of neutral flow over a cylinder is presented using the structured body fitted grid, and the Cartesian body de-coupled grid.

Some materials may naturally form discontinuities such as cracks as a result of deformation. As an aid to the modeling of such materials, a new framework for the basic equations of continuum mechanics, called the 'peridynamic' formulation, is proposed. The propagation of linear stress waves in the new theory is discussed, and wave dispersion relations are derived. Material stability and its connection with wave propagation is investigated. It is demonstrated by an example that the reformulated approach permits the solution of fracture problems using the same equations either on or off the crack surface or crack tip. This is an advantage for modeling problems in which the location of a crack is not known in advance. © 1999 Elsevier Science Ltd. All rights reserved.

A long-standing conjecture in combinatorial optimization says that the integrality gap of the famous Held-Karp relaxation of the symmetric TSP is precisely 4/3. In this paper, we show that a slight strengthening of this conjecture implies a tight 4/3 integrality gap for a linear programming relaxation of the asymmetric TSP. This is surprising since no constant-factor approximation is known for the latter problem. Our main tools are a new characterization of the integrality gap for linear objective functions over polyhedra, and the isolation of `hard-to-round' solutions of the relaxations.

A capacitated covering integer programs (IP) is an integer program of the form min{cx|Ux≥d, 0≤x≤b, x∈Z+}, where all entries of c, U and d are nonnegative. Given such a formulation, the ratio between the optimal integer solution and the optimal solution to the linear program relaxation can be as bad as ∥d∥, even when U consists of a single row. It is shown that by adding additional inequalities, this ratio can be improved significantly. In the general case, the improved ratio is shown to be bounded by the maximum number of non-zero coefficients in a row of U, and a polynomial-time approximation is proved to achieve this bound.

The theory for immiscible mixtures by Drumheller and Bedform was compared with the theory of Passman, Nunziato, and Walsh. The conditions under these theories reduce to an equivalent formulation are described, and the differences in their microinertial descriptions are also investigated. Two variables play special roles in both theories. They are the true material density and the volume fraction.

Automatic assembly sequencing and visualization tools are valuable in determining the best assembly sequences, but without Human Factors and Figure Models (HFFMs) it is difficult to evaluate or visualize human interaction. In industry, accelerating technological advances and shorter market windows have forced companies to turn to an agile manufacturing paradigm. This trend has promoted computerized automation of product design and manufacturing processes, such as automated assembly planning. However, all automated assembly planning software tools assume that the individual components fly into their assembled configuration and generate what appear to be a perfectly valid operations, but in reality the operations cannot physically be carried out by a human. Similarly, human figure modeling algorithms may indicate that assembly operations are not feasible and consequently force design modifications; however, if they had the capability to quickly generate alternative assembly sequences, they might have identified a feasible solution. To solve this problem HFFMs must be integrated with automated assembly planning to allow engineers to verify that assembly operations are possible and to see ways to make the designs even better. Factories will very likely put humans and robots together in cooperative environments to meet the demands for customized products, for purposes including robotic and automated assembly. For robots to work harmoniously within an integrated environment with humans the robots must have cooperative operational skills. For example, in a human only environment, humans may tolerate collisions with one another if they did not cause much pain. This level of tolerance may or may not apply to robot-human environments. Humans expect that robots will be able to operate and navigate in their environments without collisions or interference. The ability to accomplish this is linked to the sensing capabilities available. Current work in the field of cooperative automation has shown the effectiveness of humans and machines directly interacting to perform tasks. To continue to advance this area of robotics, effective means need to be developed to allow natural ways for people to communicate and cooperate with robots just as they do with one another.

QUICKSILVER is a 3-d electromagnetic particle-in-cell simulation code developed and used at Sandia to model relativistic charged particle transport. It models the time-response of electromagnetic fields and low-density-plasmas in a self-consistent manner: the fields push the plasma particles and the plasma current modifies the fields. Through an LDRD project a new parallel version of QUICKSILVER was created to enable large-scale plasma simulations to be run on massively-parallel distributed-memory supercomputers with thousands of processors, such as the Intel Tflops and DEC CPlant machines at Sandia. The new parallel code implements nearly all the features of the original serial QUICKSILVER and can be run on any platform which supports the message-passing interface (MPI) standard as well as on single-processor workstations. This report describes basic strategies useful for parallelizing and load-balancing particle-in-cell codes, outlines the parallel algorithms used in this implementation, and provides a summary of the modifications made to QUICKSILVER. It also highlights a series of benchmark simulations which have been run with the new code that illustrate its performance and parallel efficiency. These calculations have up to a billion grid cells and particles and were run on thousands of processors. This report also serves as a user manual for people wishing to run parallel QUICKSILVER.

Microstructural evolution due to aging of solder alloys determines their long-term reliability as electrical, mechanical and thermal interconnects in electronics packages. The ability to accurately determine the reliability of existing electronic components as well as to predict the performance of proposed designs depends upon the development of reliable material models. A kinetic Monte Carlo simulation was used to simulate microstructural evolution in solder-class materials. The grain growth model simulated many of the microstructural features observed experimentally in 63Sn-37Pb, a popular near-eutectic solder alloy. The model was validated by comparing simulation results to new experimental data on coarsening of Sn-Pb solder. The computational and experimental grain growth exponent for two-phase solder was found to be much lower than that for normal, single phase grain growth. The grain size distributions of solders obtained from simulations were narrower than that of normal grain growth. It was found that the phase composition of solder is important in determining grain growth behavior.

Abstract not provided.

For a wide variety of scientific and engineering problems the desired solution corresponds to an optimal set of objective function parameters, where the objective function measures a solution's quality. The main goal of the LDRD ''Global Optimization for Engineering Science Problems'' was the development of new robust and efficient optimization algorithms that can be used to find globally optimal solutions to complex optimization problems. This SAND report summarizes the technical accomplishments of this LDRD, discusses lessons learned and describes open research issues.

This report presents a specification for the Portals 3.0 message passing interface. Portals 3.0 is intended to allow scalable, high-performance network communication between nodes of a parallel computing system. Specifically, it is designed to support a parallel computing platform composed of clusters of commodity workstations connected by a commodity system area network fabric. In addition, Portals 3.0 is well suited to massively parallel processing and embedded systems. Portals 3.0 represents an adoption of the data movement layer developed for massively parallel processing platforms, such as the 4500-node Intel TeraFLOPS machine.

Salinas provides a massively parallel implementation of structural dynamics finite element analysis, required for high fidelity, validated models used in modal, vibration, static and shock analysis of weapons systems. This document provides a users guide to the input for Salinas. Details of input specifications for the different solution types, output options, element types and parameters are included. The appendices contain detailed examples, and instructions for running the software on parallel platforms.

In an attempt to automatically produce high-quality all-hex meshes, we investigated a mesh improvement strategy: given an initial poor-quality all-hex mesh, we iteratively changed the element connectivity, adding and deleting elements and nodes, and optimized the node positions. We found a set of hex reconnection primitives. We improved the optimization algorithms so they can untangle a negative-Jacobian mesh, even considering Jacobians on the boundary, and subsequently optimize the condition number of elements in an untangled mesh. However, even after applying both the primitives and optimization we were unable to produce high-quality meshes in certain regions. Our experiences suggest that many boundary configurations of quadrilaterals admit no hexahedral mesh with positive Jacobians, although we have no proof of this.

Predicting the behavior of ion channel proteins is important for understanding biological effects of drugs and toxins. These problems involve steady state transport of ions through very small (1-2 atoms wide) pores. FY99 LDRD funding was used to begin investigations of ion channel proteins using a molecular theory approach. Much of our efforts involved establishing the soundness of the approach by direct comparison with grand canonical molecular dynamics simulations of simple model systems. In addition, several dimensional ion channel models have been implemented to demonstrate the viability of the approach, The seed funding provided by this LDRD grant resulted in 50K of DOWOBER funds for FY99, an invitation to submit a full length 0(500K) proposal for consideration to DOWOBER, and start a larger LDRD effort in computational biophysics beginning in FY00.

Direct metal deposition technologies produce complex, near net shape components from Computer Aided Design (CAD) solid models. Most of these techniques fabricate a component by melting powder in a laser weld pool, rastering the weld bead to form a layer, and additively constructing subsequent layers. This report will describe anew direct metal deposition process, known as WireFeed, whereby a small diameter wire is used instead of powder as the feed material to fabricate components. Currently, parts are being fabricated from stainless steel alloys. Microscopy studies show the WireFeed parts to be filly dense with fine microstructural features. Mechanical tests show stainless steel parts to have high strength values with retained ductility. A model was developed to simulate the microstructural evolution and coarsening during the WireFeed process. Simulations demonstrate the importance of knowing the temperature distribution during fabrication of a WireFeed part. The temperature distribution influences microstructural evolution and, therefore, must be controlled to tailor the microstructure for optimal performance.

Current supercomputers use large parallel arrays of tightly coupled processors to achieve levels of performance far surpassing conventional vector supercomputers. Shock-wave physics codes have been developed for these new supercomputers at Sandia National Laboratories and elsewhere. These parallel codes run fast enough on many simulations to consider using them to study the effects of varying design parameters on the performance of models of conventional munitions and other complex systems. Such studies maybe directed by optimization software to improve the performance of the modeled system. Using a shaped-charge jet design as an archetypal test case and the CTH parallel shock-wave physics code controlled by the Dakota optimization software, we explored the use of automatic optimization tools to optimize the design for conventional munitions. We used a scheme in which a lower resolution computational mesh was used to identify candidate optimal solutions and then these were verified using a higher resolution mesh. We identified three optimal solutions for the model and a region of the design domain where the jet tip speed is nearly optimal, indicating the possibility of a robust design. Based on this study we identified some of the difficulties in using high-fidelity models with optimization software to develop improved designs. These include developing robust algorithms for the objective function and constraints and mitigating the effects of numerical noise in them. We conclude that optimization software running high-fidelity models of physical systems using parallel shock wave physics codes to find improved designs can be a valuable tool for designers. While current state of algorithm and software development does not permit routine, ''black box'' optimization of designs, the effort involved in using the existing tools may well be worth the improvement achieved in designs.

A set of linear and nonlinear stability analysis tools have been developed to analyze steady state incompressible flows in 3D geometries. The algorithms have been implemented to be scalable to hundreds of parallel processors. The linear stability of steady state flows are determined by calculating the rightmost eigenvalues of the associated generalize eigenvalue problem. Nonlinear stability is studied by bifurcation analysis techniques. The boundaries between desirable and undesirable operating conditions are determined for buoyant flow in the rotating disk CVD reactor.

Predicting the properties of nonequilibrium systems from molecular simulations is a growing area of interest. One important class of problems involves steady state diffusion. To study these cases, a grand canonical molecular dynamics approach has been developed by Heffelfinger and van Swol [J. Chem. Phys., 101, 5274 (1994)]. With this method, the flux of particles, the chemical potential gradients, and density gradients can all be measured in the simulation. In this paper, we present a complementary approach that couples a nonlocal density functional theory (DFT) with a transport equation describing steady-state flux of the particles. We compare transport-DFT predictions to GCMD results for a variety of ideal (color diffusion), and nonideal (uphill diffusion and convective transport) systems. In all cases excellent agreement between transport-DFT and GCMD calculations is obtained with diffusion coefficients that are invariant with respect to density and external fields.

The emerging field of haptics represents a fundamental change in human-computer interaction (HCI), and presents solutions to problems that are difficult or impossible to solve with a two-dimensional, mouse-based interface. To take advantage of the potential of haptics, however, innovative interaction techniques and programming environments are needed. This paper describes FGB (FLIGHT GHUI Builder), a programming tool that can be used to create an application specific graphical and haptic user interface (GHUI). FGB is itself a graphical and haptic user interface with which a programmer can intuitively create and manipulate components of a GHUI in real time in a graphical environment through the use of a haptic device. The programmer can create a GHUI without writing any programming code. After a user interface is created, FGB writes the appropriate programming code to a file, using the FLIGHT API, to recreate what the programmer created in the FGB interface. FGB saves programming time and increases productivity, because a programmer can see the end result as it is created, and FGB does much of the programming itself. Interestingly, as FGB was created, it was used to help build itself. The further FGB was in its development, the more easily and quickly it could be used to create additional functionality and improve its own design. As a finished product, FGB can be used to recreate itself in much less time than it originally required, and with much less programming. This paper describes FGB's GHUI components, the techniques used in the interface, how the output code is created, where programming additions and modifications should be placed, and how it can be compared to and integrated with existing API's such as MFC and Visual C++, OpenGL, and GHOST.

Traditionally law enforcement agencies have relied on basic measurement and imaging tools, such as tape measures and cameras, in recording a crime scene. A disadvantage of these methods is that they are slow and cumbersome. The development of a portable system that can rapidly record a crime scene with current camera imaging, 3D geometric surface maps, and contribute quantitative measurements such as accurate relative positioning of crime scene objects, would be an asset to law enforcement agents in collecting and recording significant forensic data. The purpose of this project is to develop a feasible prototype of a fast, accurate, 3D measurement and imaging system that would support law enforcement agents to quickly document and accurately record a crime scene.

The objective of the SIERRA framework is to provide a common software infrastructure for massively parallel computational mechanics applications. The SIERRA framework consolidates the mechanics-independent computational services required by a diverse set of mechanics applications into a shared framework. Consolidation of these computational services eliminates their redundant development and maintenance efforts and streamlines the coupling of independently developed computational mechanics capabilities into integrated multi-mechanics applications.

In this letter we discusses the first application of 3-dimensional nonlocal density functional calculations to the interactions of solvated rigid polymers. The three cases considered are cylindrical polymers, bead-chain polymers, and periodic polymers. We calculate potentials of mean force, and show that polymer surface structure plays a critical role in determining the solvation energy landscape which in turn controls routes to assembly of the macromolecules.

Current hexahedral mesh generation techniques rely on a set of meshing tools, which when combined with geometry decomposition leads to an adequate mesh generation process. Of these tools, sweeping tends to be the workhorse algorithm, accounting for at least 50% of most meshing applications. Constraints which must be met for a volume to be sweepable are derived, and it is proven that these constraints are necessary but not sufficient conditions for sweepability. This paper also describes a new algorithm for detecting extruded or sweepable geometries. This algorithm, based on these constraints, uses topological and local geometric information, and is more robust than feature recognition-based algorithms. A method for computing sweep dependencies in volume assemblies is also given. The auto sweep detect and sweep grouping algorithms have been used to reduce interactive user time required to generate all-hexahedral meshes by filtering out non-sweepable volumes needing further decomposition and by allowing concurrent meshing of independent sweep groups. Parts of the auto sweep detect algorithm have also been used to identify independent sweep paths, for use in volume-based interval assignment.

Sweeping algorithms have become very mature and can create a semi-structured mesh on a large set of solids. However, these algorithms require that all linking surfaces be mappable or submappable. This restriction excludes solids with imprints or protrusions on the linking surfaces. The grafting algorithm allows these solids to be swept. It then locally modifies the position and connectivity of the nodes on the linking surfaces to align with the graft surfaces. Once a high-quality surface mesh is formed on the graft surface, it is swept along the branch creating a 2 3/4-D mesh.

We present a new shape measure for tetrahedral elements that is optimal in the sense that it gives the distance of a tetrahedron from the set of inverted elements. This measure is constructed from the condition number of the linear transformation between a unit equilateral tetrahedron and any tetrahedron with positive volume. We use this shape measure to formulate two optimization objective functions that are differentiated by their goal: the first seeks to improve the average quality of the tetrahedral mesh; the second aims to improve the worst-quality element in the mesh. Because the element condition number is not defined for tetrahedral with negative volume, these objective functions can be used only when the initial mesh is valid. Therefore, we formulate a third objective function using the determinant of the element Jacobian that is suitable for mesh untangling. We review the optimization techniques used with each objective function and present experimental results that demonstrate the effectiveness of the mesh improvement and untangling methods. We show that a combined optimization approach that uses both condition number objective functions obtains the best-quality meshes.

Objective functions for unstructured hexahedral and tetrahedral mesh optimization are analyzed using matrices and matrix norms. Mesh untangling objective functions that create valid meshes are used to initialize the optimization process. Several new objective functions to achieve element invertibility and quality are investigated, the most promising being the ''condition number''. The condition number of the Jacobian matrix of an element forms the basis of a barrier-based objective function that measures the distance to the set of singular matrices and has the ideal matrix as a stationary point. The method was implemented in the Cubit code, with promising results.

Considerable progress has been made on automatic hexahedral mesh generation in recent years. Several automatic meshing algorithms have proven to be very reliable on certain classes of geometry. While it is always worth pursuing general algorithms viable on more general geometry, a combination of the well-established algorithms is ready to take on classes of complicated geometry. By partitioning the entire geometry into meshable pieces matched with appropriate meshing algorithm the original geometry becomes meshable and may achieve better mesh quality. Each meshable portion is recognized as a meshing feature. This paper, which is a part of the feature based meshing methodology, presents the work on shape recognition and volume decomposition to automatically decompose a CAD model into meshable volumes. There are four phases in this approach: (1) Feature Determination to extinct decomposition features, (2) Cutting Surfaces Generation to form the ''tailored'' cutting surfaces, (3) Body Decomposition to get the imprinted volumes; and (4) Meshing Algorithm Assignment to match volumes decomposed with appropriate meshing algorithms. The feature determination procedure is based on the CLoop feature recognition algorithm that is extended to be more general. Results are demonstrated over several parts with complicated topology and geometry.

A new method for lessening skew in mapped meshes is presented. This new method involves progressive subdivision of a surface into loops consisting of four sides. Using these loops, constraints can then be set on the curves of the surface, which will propagate interval assignments across the surface, allowing a mesh with a better skew metric to be generated.

NIST and Sandia have developed a procedure for producing and calibrating critical dimension (CD), or linewidth, reference materials. These reference materials will be used to calibrate metrology instruments used in semiconductor manufacturing. The artifacts, with widths down to 100 nm, are produced in monocrystalline silicon with all feature edges aligned to specific crystal planes. A two-part calibration of these linewidths is used: the primary calibration, with accuracy to within a few lattice plane thicknesses, is accomplished by counting the lattice planes across the sample as-imaged through use of high-resolution transmission electron microscopy (HRTEM). The secondary calibration is the high-precision electrical CD technique. NIST and Sandia are developing critical dimension (CD), or linewidth, reference materials for use by the semiconductor industry. To meet the current requirements of this rapidly changing industry, the widths of the reference features must be at or below the widths of the finest features in production and/or development. Further, these features must produce consistent results no matter which metrology tool (e.g., scanning electron microscope, scanned probe microscope, electrical metrology) is used to make the measurement. This leads to a requirement for the samples to have planar surfaces, known sidewall angles, and uniform material composition. None of the production techniques in use in semiconductor manufacturing can produce features with all these characteristics. In addition, requirements specified in the National Technology Roadmap for Semiconductors indicate that the width of the feature must be accurately calibrated to approximately 1-2 nm, a value well beyond the current capabilities of the instruments used for semiconductor metrology.

This paper presents a new technique for automatically detecting interval constraints for swept volumes with holes. The technique finds true volume constraints that are not necessarily imposed by the surfaces of the volume. A graphing algorithm finds independent, parallel paths of edges from source surfaces to target surfaces. The number of intervals on two paths between a given source and target surface must be equal; in general, the collection of paths determine a set of linear constraints. Linear programming techniques solve the interval assignment problem for the surface and volume constraints simultaneously.

Abstract not provided.

Frequency-domain shot-record migration can produce higher quality images than Kirchhoff migration but typically at a greater cost. The computational cost of shot-record migration is the product of the number of shots in the survey and the expense of each individual migration. Many attempts to reduce this cost have focused on the speed of the individual migrations, trying to achieve a better trade-off between accuracy and speed. Another approach is to reduce the number of migrations. We investigate the simultaneous migration of shot records using frequency-domain shot-record migration algorithms. The difficulty with this approach is the production of so-called cross terms between unrelated shot and receiver wavefields, which generate unwanted artifacts or noise in the final image. To reduce these artifacts and obtain an image comparable in quality to the single-shot-per-migration result, we have introduced a process called phase encoding which shifts or disperses these cross terms. The process of phase encoding thus allows one to trade signal-to-noise ratio for the speed of migrating the entire survey. Several encoding functions and two application strategies have been tested. The first strategy, combining multiple shots per migration and using each shot only once, provides a reduction in computation directly related to the number of shots combined. The second strategy, performing multiple migrations of all the shots in the survey, provides a means to reduce the cross-term noise through stacking the resulting images. The additional noise in both strategies may be tolerated if it is no stronger than the inherent seismic noise in the migrated image, and if the final image is achieved with less cost.

Both the increased complexity of integrated circuits, resulting in six or more levels of integration, and the increasing use of flip-chip packaging have driven the development of integrated circuit (IC) failure analysis tools that can be applied to the backside of the chip. Among these new approaches are focused ion beam (FIB) tools and processes for performing chip edits/repairs from the die backside. This paper describes the use of backside FIB for a failure analysis application rather than for chip repair. Specifically, we used FIB technology to prepare an IC for inspection of voided metal interconnects (''lines'') and vias. Conventional FIB milling was combined with a super-enhanced gas assisted milling process that uses XeF{sub 2} for rapid removal of large volumes of bulk silicon. This combined approach allowed removal of the TiW underlayer from a large number of Ml lines simultaneously, enabling rapid localization and plan view imaging of voids in lines and vias with backscattered electron (BSE) imaging in a scanning electron microscope (SEM). Sequential cross sections of individual voided vias enabled us to develop a 3-d reconstruction of these voids. This information clarified how the voids were formed, helping us identify the IC process steps that needed to be changed.

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. Sometimes, however, points are generated such that there is additional information available to the reconstruction algorithm. We present Spiraling Edge, 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 is filled by the final triangle.

Visualization systems are complex dynamic software systems. Debugging such systems is difficult using conventional debuggers because the programmer must try to imagine the three-dimensional geometry based on a list of positions and attributes. In addition, the programmer must be able to mentally animate changes in those positions and attributes to grasp dynamic behaviors within the algorithm. In this paper we shall show that representing geometry, attributes, and relationships graphically permits visual pattern recognition skills to be applied to the debugging problem. The particular application is a particle system used for isosurface extraction from volumetric data. Coloring particles based on individual attributes is especially helpful when these colorings are viewed as animations over successive iterations in the program. Although we describe a particular application, the types of tools that we discuss can be applied to a variety of problems.

We show that Sorensen's [35] implicitly restarted Arnoldi method (including its block extension) is simultaneous iteration with an implicit projection step to accelerate convergence to the invariant subspace of interest. By using the geometric convergence theory for simultaneous iteration due to Watkins and Elsner [43], we prove that an implicitly restarted Arnoldi method can achieve a super-linear rate of convergence to the dominant invariant subspace of a matrix. Moreover, we show how an IRAM computes a nested sequence of approximations for the partial Schur decomposition associated with the dominant invariant subspace of a matrix.