Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Algorithms and data structure”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 253 records · Page 14

Haar-Like Wavelets on Hierarchical Trees

Here, discrete wavelet methods, originally formulated in the setting of regularly sampled signals, can be adapted to data defined on a point cloud if some multiresolution structure is imposed on the cloud. A wide variety of hierarchical clustering algorithms can be used for this purpose, and the multiresolution structure obtained can be encoded by a hierarchical tree of subsets of the cloud. Prior work introduced the use of Haar-like bases defined with respect to such trees for approximation and learning tasks on unstructured data. This paper builds on that work in two directions. First, we present an algorithm for constructing Haar-like bases on general discrete hierarchical trees. Second, with an eye towards data compression, we present thresholding techniques for data defined on a point cloud with error controlled in the $L$ $\infty$ norm and in a Hölder-type norm. In a concluding trio of numerical examples, we apply our methods to compress a point cloud dataset, study the tightness of the $L$ $\infty$ error bound, and use thresholding to identify MNIST classifiers with good generalizability.

97 MATHEMATICS AND COMPUTING↗

Open data set of live cyanobacterial cells imaged using an X-ray laser

Structural studies on living cells by conventional methods are limited to low resolution because radiation damage kills cells long before the necessary dose for high resolution can be delivered. X-ray free-electron lasers circumvent this problem by outrunning key damage processes with an ultra-short and extremely bright coherent X-ray pulse. Diffraction-before-destruction experiments provide high-resolution data from cells that are alive when the femtosecond X-ray pulse traverses the sample. This paper presents two data sets from micron-sized cyanobacteria obtained at the Linac Coherent Light Source, containing a total of 199,000 diffraction patterns. Utilizing this type of diffraction data will require the development of new analysis methods and algorithms for studying structure and structural variability in large populations of cells and to create abstract models. Such studies will allow us to understand living cells and populations of cells in new ways. New X-ray lasers, like the European XFEL, will produce billions of pulses per day, and could open new areas in structural sciences.

59 BASIC BIOLOGICAL SCIENCES↗

A mass graph-based approach for the identification of modified proteoforms using top-down tandem mass spectra

Motivation: Although proteomics has rapidly developed in the past decade, researchers are still in the early stage of exploring the world of complex proteoforms, which are protein products with various primary structure alterations resulting from gene mutations, alternative splicing, post-translational modifications, and other biological processes. Proteoform identification is essential to mapping proteoforms to their biological functions as well as discovering novel proteoforms and new protein functions. Top-down mass spectrometry is the method of choice for identifying complex proteoforms because it provides a “bird’s eye view” of intact proteoforms. The combinatorial explosion of various alterations on a protein may result in billions of possible proteoforms, making proteoform identification a challenging computational problem. Results: We propose a new data structure, called the mass graph, for efficient representation of proteoforms and design mass graph alignment algorithms. We developed TopMG, a mass graph-based software tool for proteoform identification by top-down mass spectrometry. Experiments on top-down mass spectrometry data sets showed that TopMG outperformed existing methods in identifying complex proteoforms.

Dynamic Programming↗

Special Issue: Geostatistics and Machine Learning

Abstract Recent years have seen a steady growth in the number of papers that apply machine learning methods to problems in the earth sciences. Although they have different origins, machine learning and geostatistics share concepts and methods. For example, the kriging formalism can be cast in the machine learning framework of Gaussian process regression. Machine learning, with its focus on algorithms and ability to seek, identify, and exploit hidden structures in big data sets, is providing new tools for exploration and prediction in the earth sciences. Geostatistics, on the other hand, offers interpretable models of spatial (and spatiotemporal) dependence. This special issue on Geostatistics and Machine Learning aims to investigate applications of machine learning methods as well as hybrid approaches combining machine learning and geostatistics which advance our understanding and predictive ability of spatial processes.

58 GEOSCIENCES↗

Protein structure prediction guided by crosslinking restraints – A systematic evaluation of the impact of the crosslinking spacer length

Recent development of high-resolution mass spectrometry (MS) instruments enables chemical crosslinking (XL) to become a high-throughput method for obtaining structural information about proteins. Restraints derived from XL-MS experiments have been used successfully for structure refinement and protein–protein docking. However, one formidable question is under which circumstances XL-MS data might be sufficient to determine a protein’s tertiary structure de novo? Answering this question will not only include understanding the impact of XL-MS data on sampling and scoring within a de novo protein structure prediction algorithm, it must also determine an optimal crosslinker type and length for protein structure determination. While a longer crosslinker will yield more restraints, the value of each restraint for protein structure prediction decreases as the restraint is consistent with a larger conformational space. In this study, the number of crosslinks and their discriminative power was systematically analyzed in silico on a set of 2055 non-redundant protein folds considering Lys–Lys, Lys–Asp, Lys–Glu, Cys–Cys, and Arg–Arg reactive crosslinkers between 1 and 60 Å. Depending on the protein size a heuristic was developed that determines the optimal crosslinker length. Next, simulated restraints of variable length were used to de novo predict the tertiary structure of fifteen proteins using the BCL::Fold algorithm. The results demonstrate that a distinct crosslinker length exists for which information content for de novo protein structure prediction is maximized. The sampling accuracy improves on average by 1.0 Å and up to 2.2 Å in the most prominent example. XL-MS restraints enable consistently an improved selection of native-like models with an average enrichment of 2.1.

Biochemistry & Molecular Biology↗

Nanoscale Cluster Detection in Massive Atom Probe Tomography Data

Recent technological advances in atom probe tomography (APT) have led to unprecedented data acquisition capabilities that routinely generate data sets containing hundreds of millions of atoms. Detecting nanoscale clusters of different atom types present in these enormous amounts of data and analyzing their spatial correlations with one another are fundamental to understanding the structural properties of the material from which the data is derived. Extant algorithms for nanoscale cluster detection do not scale to large data sets. Here, a scalable, CUDA-based implementation of an autocorrelation algorithm is presented. It isolates spatial correlations amongst atomic clusters present in massive APT data sets in linear time using a linear amount of storage. Correctness of the algorithm is demonstrated using large synthetically generated data with known spatial distributions. Benefits and limitations of using GPU-acceleration for autocorrelation-based APT data analyses are presented with supporting performance results on data sets with up to billions of atoms. To our knowledge, this is the first nanoscale cluster detection algorithm that scales to massive APT data sets and executes on commodity hardware.

Seal, Sudip K↗

Identification of subsurface structures using electromagnetic data and shape priors

We consider the inverse problem of identifying large-scale subsurface structures using the controlled source electromagnetic method. To identify structures in the subsurface where the contrast in electric conductivity can be small, regularization is needed to bias the solution towards preserving structural information. We propose to combine two approaches for regularization of the inverse problem. In the first approach we utilize a model-based, reduced, composite representation of the electric conductivity that is highly flexible, even for a moderate number of degrees of freedom. With a low number of parameters, the inverse problem is efficiently solved using a standard, second-order gradient-based optimization algorithm. Further regularization is obtained using structural prior information, available, e.g., from interpreted seismic data. The reduced conductivity representation is suitable for incorporation of structural prior information. Such prior information cannot, however, be accurately modeled with a gaussian distribution. To alleviate this, we incorporate the structural information using shape priors. The shape prior technique requires the choice of kernel function, which is application dependent. We argue for using the conditionally positive definite kernel which is shown to have computational advantages over the commonly applied gaussian kernel for our problem. Numerical experiments on various test cases show that the methodology is able to identify fairly complex subsurface electric conductivity distributions while preserving structural prior information during the inversion.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Crystal structure solution from experimentally determined atomic pair distribution functions

An extension of the Liga algorithm for structure solution from atomic pair distribution functions (PDFs), to handle periodic crystal structures with multiple elements in the unit cell, is described. The procedure is performed in three separate steps. First, pair distances are extracted from the experimental PDF. In the second step the Liga algorithm is used to find unit-cell sites consistent with these pair distances. Finally, the atom species are assigned over the cell sites by minimizing the overlap of their empirical atomic radii. The procedure has been demonstrated on synchrotron X-ray PDF data from 16 test samples. The structure solution was successful for 14 samples, including cases with enlarged supercells. The algorithm success rate and the reasons for the failed cases are discussed, together with enhancements that should improve its convergence and usability.

36 MATERIALS SCIENCE↗

Fault-tolerant dynamic task graph scheduling

In this paper, we present an approach to fault tolerant execution of dynamic task graphs scheduled using work stealing. In particular, we focus on selective and localized recovery of tasks in the presence of soft faults. We elicit from the user the basic task graph structure in terms of successor and predecessor relationships. The work stealing-based algorithm to schedule such a task graph is augmented to enable recovery when the data and meta-data associated with a task get corrupted. We use this redundancy, and the knowledge of the task graph structure, to selectively recover from faults with low space and time overheads. We show that the fault tolerant design retains the essential properties of the underlying work stealing-based task scheduling algorithm, and that the fault tolerant execution is asymptotically optimal when task re-execution is taken into account. Experimental evaluation demonstrates the low cost of recovery under various fault scenarios.

fault tolerance↗

Investigation of fast and efficient lossless compression algorithms for macromolecular crystallography experiments

Structural biology experiments benefit significantly from state-of-the-art synchrotron data collection. One can acquire macromolecular crystallography (MX) diffraction data on large-area photon-counting pixel-array detectors at framing rates exceeding 1000 frames per second, using 200 Gbps network connectivity, or higher when available. In extreme cases this represents a raw data throughput of about 25 GB s −1 , which is nearly impossible to deliver at reasonable cost without compression. Our field has used lossless compression for decades to make such data collection manageable. Many MX beamlines are now fitted with DECTRIS Eiger detectors, all of which are delivered with optimized compression algorithms by default, and they perform well with current framing rates and typical diffraction data. However, better lossless compression algorithms have been developed and are now available to the research community. Here one of the latest and most promising lossless compression algorithms is investigated on a variety of diffraction data like those routinely acquired at state-of-the-art MX beamlines.

36 MATERIALS SCIENCE↗

A Scalable Hybrid Scheme for Ray-Casting of Unstructured Volume Data

We present an algorithm for parallel volume rendering that is a hybrid between classical object order and image order techniques. The algorithm operates on unstructured grids (and structured ones), and thus can deal with block boundaries interleaving in complex ways. It also deals effectively with cases that are prone to load imbalance, i.e., cases where cell sizes differ dramatically, either because of the nature of the input data, or because of the effects of the camera transformation. The algorithm divides work over resources such that each phase of its processing is bounded in the amount of computation it can perform. We demonstrate its efficacy through a series of studies, varying over camera position, data set size, transfer function, image size, and processor count. At its biggest, our experiments scaled up to 8,192 processors and operated on data sets with more than one billion cells. In total, we find that our hybrid algorithm performs well in all cases. This is because our algorithm naturally adapts its computation based on workload, and can operate like either an object order technique or an image order technique in scenarios where those techniques are efficient.

97 MATHEMATICS AND COMPUTING↗

Probing the structure of complex solids using a distributed computing approach-Applications in zeolite science

We demonstrate the viability of distributed computing techniques employing idle desktop computers in investigating complex structural problems in solids. Through the use of a combined Monte Carlo and energy minimisation method, we show how a large parameter space can be effectively scanned. By controlling the generation and running of different configurations through a database engine, we are able to not only analyse the data 'on the fly' but also direct the running of jobs and the algorithms for generating further structures. As an exemplar case, we probe the distribution of Al and extra-framework cations in the structure of the zeolite Mordenite. We compare our computed unit cells with experiment and find that whilst there is excellent correlation between computed and experimentally derived unit cell volumes, cation positioning and short-range Al ordering (i.e. near neighbour environment), there remains some discrepancy in the distribution of Al throughout the framework. We also show that stability-structure correlations only become apparent once a sufficiently large sample is used. - Graphical Abstract: Aluminium distributions in zeolites are determined using e-science methods. Highlights: > Use of e-science methods to search configurationally space. > Automated control of space searching. > Identify key structural features conveying stability. > Improved correlation of computed structures with experimental data.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Inversion of dynamical Bragg intensities to complex structure factors by iterated projections. For Ultramic. 2020. ("Pico" Festschrift, May 2021)

We discuss a method for recovering complex structure factors from many simultaneously excited Bragg beam intensities is described. The method is applied to simulated transmission electron diffraction data over a wide range of crystal thickness and beam energies. The method is based on iterated projections between structure and scattering matrices, which are related by a matrix unitary transformation, exponential, which we invert. The algorithm removes multiple-scattering perturbations from diffraction data and might be extended to other fields, including X-ray and neutron diffraction and cryo-electron microscopy. Because coherent multiple scattering involves interference between Bragg beams, the method also solves the phase problem. Unlike dynamical inversion from electron microscope images or ptychography data, the method, which starts with Bragg beam intensities, provides complex structure factors unaffected by focusing errors or resolution limitations imposed by lenses. We provide inversions from simulated data with 441 simultaneously excited Bragg beams over a range of thickness and beam energy. We discuss the retrieval of chirality information from enantiomorphs, the efficient incorporation of symmetry information using the irreducible representation of the group of structure matrices, and the effect of HOLZ lines to provide three-dimensional information.

97 MATHEMATICS AND COMPUTING↗

Uncertainty in inventories for life cycle assessment: State‐of‐the‐art, challenges, and new technologies

Uncertainty is a critical factor that can hinder the quality and potential applications of life cycle assessment (LCA) results. A prominent source of uncertainty stems from the life cycle inventory (LCI) data. Various methodologies exist to estimate the uncertainty associated with LCI data, primarily based on the widely used structured pedigree matrix approach or the computationally intensive Monte Carlo simulation. This perspective review explores how new technologies (e.g., computational algorithms and data collection methods) from data science and related fields can contribute to identifying, quantifying, and reducing uncertainty in LCI modeling. A brief overview of the sources of uncertainty in LCI modeling and how they are addressed in current LCA practice is provided. Additionally, several new technologies are identified, and the potential benefits of their implementation in reducing uncertainties in LCI modeling are discussed. This perspective review concludes by identifying potential areas that require further development for these technologies.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

PySpawn: Software for Nonadiabatic Quantum Molecular Dynamics

The ab initio multiple spawning (AIMS) method enables nonadiabatic quantum molecular dynamics simulations in an arbitrary number of dimensions, with potential energy surfaces provided by electronic structure calculations performed on-the-fly. However, the intricacy of the AIMS algorithm complicates software development, deployment on modern shared computer resources, and post-simulation data analysis. PySpawn is a nonadiabatic molecular dynamics software package that addresses these issues. Here, the program is designed to be easily interfaced with electronic structure software, and an interface to the TeraChem software package is described here. PySpawn introduces a task-based reorganization of the AIMS algorithm, allowing fine-grained restart capability and setting the stage for efficient parallelization in a future release. PySpawn includes a user-friendly and interactive Python analysis module that will enable novice users to painlessly adopt AIMS. As a demonstration of PySpawn’s simulation capability and analysis module, we report complete active space self-consistent field–based AIMS simulations of the 1,2- dithienyl-1,2-dicyanoethene molecule, a promising molecular photoswitch.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

ECP Milestone Memo WBS 2.3.4.13 ECP/VTK-m FY18Q4 [MS-18/09-10] Dynamic Types / Rendering Topologies STDA05-16

The STDA05-16 milestone comprises the following 3 distinct deliverables. OpenMP VTK-m currently supports three types of devices: serial CPU, TBB, and CUDA. To run algorithms on multicore CPU-type devices (such as Xeon and Xeon Phi), TBB is required. However, there are known issues with integrating a software product using TBB with another one using OpenMP. Therefore, we will add an OpenMP device to the VTK-m software. When engaged, this device will run parallel algorithms using OpenMP directives. This will mesh more nicely with other code also using OpenMP. Rendering Topological Entities VTK-m currently supports surface rendering by tessellation of data structures,and rendering the resulting triangles. We will extend current functionality to include face, edge, and point rendering. Better Dynamic Types Impl For the best efficiency across all platforms, VTK-m algorithms use static typing with C++ templates. However, many libraries like VTK, ParaView, and Visit use dynamic types with virtual functions because data types often cannot be determined at compile time. We have an interface in VTK-m to merge these two typing mechanisms by generating all possible combinations of static types when faced with a dynamic type. Although this mechanism works, it generates very large executables and takes a very long time to compile. As we move forward, it is clear that these problems will get worse and become infeasible at exascale. We will rectify the problem by introducing some level of virtual methods, which require only a single code path, within VTK-m algorithms. This first milestone produces a design document to propose an approach to the new system.

97 MATHEMATICS AND COMPUTING↗

Basker: Parallel sparse LU factorization utilizing hierarchical parallelism and data layouts

Transient simulation in circuit simulation tools, such as SPICE and Xyce, depend on scalable and robust sparse LU factorizations for efficient numerical simulation of circuits and power grids. As the need for simulations of very large circuits grow, the prevalence of multicore architectures enable us to use shared memory parallel algorithms for such simulations. A parallel factorization is a critical component of such shared memory parallel simulations. We develop a parallel sparse factorization algorithm that can solve problems from circuit simulations efficiently, and map well to architectural features. This new factorization algorithm exposes hierarchical parallelism to accommodate irregular structure that arise in our target problems. It also uses a hierarchical two-dimensional data layout which reduces synchronization costs and maps to memory hierarchy found in multicore processors. We present an OpenMP based implementation of the parallel algorithm in a new multithreaded solver called Basker in the Trilinos framework. Here, we present performance evaluations of Basker on the Intel SandyBridge and Xeon Phi platforms using circuit and power grid matrices taken from the University of Florida sparse matrix collection and from Xyce circuit simulation. Basker achieves a geometric mean speedup of 5.91× on CPU (16 cores) and 7.4× on Xeon Phi (32 cores) relative to state-of-the-art solver KLU. Basker outperforms Intel MKL Pardiso solver (PMKL) by as much as 30× on CPU (16 cores) and 7.5× on Xeon Phi (32 cores) for low fill-in circuit matrices. Furthermore, Basker provides 5.4× speedup on a challenging matrix sequence taken from an actual Xyce simulation.

97 MATHEMATICS AND COMPUTING↗

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗