Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithm complexity analysis”

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 37 records · Page 2

Efficient Reliability Analysis using Generalized Multifidelity Modeling and Explainable Active Learning

To assess the reliability of critical technologies like nuclear plants and infrastructure systems and improve the robustness of design, engineers have to quantify the uncertainties surrounding the system behavior accurately. However, the complexity of the problem can make standard reliability analysis algorithms prohibitively expensive, primarily due to the high computational cost of estimating the system response at each iteration. This cost can be greatly reduced by using multi-fidelity modeling and machine learning to build a surrogate model to replace the expensive response function. We propose a general and robust method for building surrogates from multiple Low Fidelity (LF) models coupled with machine learning to retain accuracy. Our framework first constructs “Corrected Low Fidelity models” (CLFs) by coupling a High Fidelity (HF) model inferred Gaussian Process correction term with each of the LF models. It then uses the correction terms to assign model probabilities to each of these CLFs in an explainable way before using them to assemble the final surrogate. No assumptions are made about the type of the LF models or their correlation with the HF model. The proposed surrogate modeling framework is used within the subset simulation algorithm (a variance-reduced MCMC-based reliability analysis algorithm) for enhanced efficiency. Additionally, an active learning step is added to the algorithm to adaptively decide when the surrogate is not sufficiently accurate, at which point the HF model is called and used to refine the surrogate. Through a frame buckling example, our method is shown to be highly efficient at reducing the expensive HF model calls while accurately estimating the failure probability.

97 MATHEMATICS AND COMPUTING↗

Parallel k-means Clustering of Geospatial Data Sets Using Manycore CPU Architectures

The increasing availability of high-resolution geospatiotemporal data sets from sources such as observatory networks, remote sensing platforms, and computational Earth system models has opened new possibilities for knowledge discovery and mining of weather, climate, ecological, and other geoscientific data sets fused from disparate sources. Many of the standard tools used on individual workstations are impractical for the analysis and synthesis of data sets of this size; however, new algorithmic approaches that can effectively utilize the complex memory hierarchies and the extremely high levels of parallelism available in state-of-the-art high-performance computing platforms can enable such analysis. Here, we describe pKluster, an open-source tool we have developed for accelerated k-means clustering of geospatial and geospatiotemporal data, and discuss algorithmic modifications and code optimizations we have made to enable it to effectively use parallel machines based on novel CPU architectures—such as the Intel “Knights Landing” Xeon Phi and Skylake Xeon processors—with many cores and hardware threads, and employing significant single instruction, multiple data (SIMD) parallelism. We outline some applications of the code in ecology and climate science contexts and present a detailed discussion of the performance of the code for one such application, LiDAR-derived vertical vegetation structure classification.

Mills, Richard T↗

Contextual Active Online Model Selection with Expert Advice

How can we collect the most useful labels to learn a model selection policy, when presented with arbitrary heterogeneous data streams? In this paper, we formulate this task as a contextual active model selection problem, where at each round the learner receives an unlabeled data point along with a context. The goal is to output the best model for any given context without obtaining an excessive amount of labels. In particular, we focus on the task of selecting pre-trained classifiers, and propose a contextual active model selection algorithm (CAMS), which relies on a novel uncertainty sampling query criterion defined on a given policy class for adaptive model selection. In comparison to prior art, our algorithm does not assume a globally optimal model. We provide rigorous theoretical analysis for the regret and query complexity under both adversarial and stochastic settings. Our experiments on several benchmark classification datasets demonstrate the algorithm’s effectiveness in terms of both regret and query complexity. Notably, to achieve the same accuracy, CAMS incurs less than 10% of the label cost when compared to the best online model selection baselines on CIFAR10.

Liu, Xuefeng↗

Enriched immersed finite element and isogeometric analysis: algorithms and data structures

Immersed finite element methods provide a convenient analysis framework for problems involving geometrically complex domains, such as those found in topology optimization and microstructures for engineered materials. However, their implementation remains a major challenge due to, among other things, the need to apply nontrivial stabilization schemes and generate custom quadrature rules. This article introduces the robust and computationally efficient algorithms and data structures comprising an immersed finite element preprocessing framework. The input to the preprocessor consists of a background mesh and one or more geometries defined on its domain. The output is structured into groups of elements with custom quadrature rules formatted such that common finite element assembly routines may be used without or with only minimal modifications. The key to the preprocessing framework is the construction of material topology information, concurrently with the generation of a quadrature rule, which is then used to perform enrichment and generate stabilization rules. While the algorithmic framework applies to a wide range of immersed finite element methods using different types of meshes, integration, and stabilization schemes, the preprocessor is presented within the context of the extended isogeometric analysis. This method utilizes a structured B-spline mesh, a generalized Heaviside enrichment strategy considering the material layout within individual basis functions’ supports, and face-oriented ghost stabilization. Using a set of examples, the effectiveness of the enrichment and stabilization strategies is demonstrated alongside the preprocessor’s robustness in geometric edge cases. Additionally, the performance and parallel scalability of the implementation are evaluated.

Computer implementation↗

Models and Algorithms for Equilibrium Analysis of Mixed-Material Nucleic Acid Systems

Dynamic programming algorithms within the NUPACK software suite enable analysis of equilibrium base-pairing properties for complex and test tube ensembles containing arbitrary numbers of interacting nucleic acid strands. Currently, calculations are limited to single-material systems that are either all-RNA or all-DNA. Here, to enable analysis of mixed-material systems that are critical for modern applications in vitro, in situ, and in vivo, we develop physical models and dynamic programming algorithms that allow the material of the system to be specified at nucleotide resolution. Free energy parameter sets are constructed for both RNA/DNA and RNA/2'OMe-RNA mixed-material systems by combining available empirical mixed-material parameters with single-material parameter sets to enable treatment of the full complex and test tube ensembles. New dynamic programming recursions account for the material of each nucleotide throughout the recursive process. For a complex with N nucleotides, the mixed-material dynamic programming algorithms maintain the O(N 3 ) time complexity of the single-material algorithms, enabling efficient calculation of diverse physical quantities over complex and test tube ensembles (e.g., complex partition function, equilibrium complex concentrations, equilibrium base-pairing probabilities, minimum free energy secondary structure(s), and Boltzmann-sampled secondary structures) at a cost increase of roughly 2.0-3.5×. The results of existing single-material algorithms are exactly reproduced when applying the new mixed-material algorithms to single-material systems. Accuracy is significantly enhanced using mixed-material models and algorithms to predict RNA/DNA and RNA/2'OMe-RNA duplex melting temperatures from the experimental literature as well as RNA/DNA melt profiles from new experiments. In conclusion, mixed-material analyses can be performed online using the NUPACK web app (www.nupack.org) or locally using the NUPACK Python module.

2′OMe-RNA↗

Reduced-order modeling on a near-term quantum computer

Quantum computing is an advancing area of research in which computer hardware and algorithms are developed to take advantage of quantum mechanical phenomena. In recent studies, quantum algorithms have shown promise in solving linear systems of equations as well as systems of linear ordinary differential equations (ODEs) and partial differential equations (PDEs). Reducedorder modeling (ROM) algorithms for studying fluid dynamics have shown success in identifying linear operators that can describe flowfields, where dynamic mode decomposition (DMD) is a particularly useful method in which a linear operator is identified from data. In this work, DMD is reformulated as an optimization problem to propagate the state of the linearized dynamical system on a quantum computer. This reformulation was chosen as a means of facilitating implementation on a near-term quantum computer. Quadratic unconstrained binary optimization (QUBO), a technique for optimizing quadratic polynomials in binary variables, allows for quantum annealing algorithms to be applied. A quantum circuit model (quantum approximation optimization algorithm, QAOA) is utilized to obtain predictions of the state trajectories. Results are shown for the quantum-ROM predictions for flow over a 2D cylinder at Re = 220 and flow over a NACA0009 airfoil at Re = 500 and α = 15°. The quantum-ROM predictions are found to depend on the number of bits utilized for a fixed point representation and the truncation level of the DMD model. Comparisons with DMD predictions from a classical computer algorithm are made, as well as an analysis of the computational complexity and prospects for future, more fault-tolerant quantum computers.

97 MATHEMATICS AND COMPUTING↗

Composable Programming of Hybrid Workflows for Quantum Simulation

We present a composable design scheme for the development of hybrid quantum/classical algorithms and workflows for applications of quantum simulation. Our object-oriented approach is based on constructing an expressive set of common data structures and methods that enable programming of a broad variety of complex hybrid quantum simulation applications. The abstract core of our scheme is distilled from the analysis of the current quantum simulation algorithms. Subsequently, it allows a synthesis of new hybrid algorithms and workflows via the extension, specialization, and dynamic customization of the abstract core classes defined by our design. We implement our design scheme using the hardware-agnostic programming language QCOR into the QuaSiMo library. To validate our implementation, we test and show its utility on commercial quantum processors from IBM, running some prototypical quantum simulations.

97 MATHEMATICS AND COMPUTING↗

Filling data analysis gaps in time-resolved crystallography by machine learning

There is a growing understanding of the structural dynamics of biological molecules fueled by x-ray crystallography experiments. Time-resolved serial femtosecond crystallography (TR-SFX) with x-ray Free Electron Lasers allows the measurement of ultrafast structural changes in proteins. Nevertheless, this technique comes with some limitations. One major challenge is the quality of data from TR-SFX measurements, which often faces issues like data sparsity, partial recording of Bragg reflections, timing errors, and pixel noise. To overcome these difficulties, conventionally, large volumes of data are collected and grouped into a few temporal bins. The data in each bin are then averaged and paired with the mean of their corresponding jittered timestamps. This procedure provides one structure per bin, resulting in a limited number of averaged structures for the entire time interval spanned by the experiment. Therefore, the information on ultrafast structural dynamics at high temporal resolution is lost. This has initiated research for advanced methods of analyzing experimental TR-SFX data beyond the standard binning and averaging method. To address this problem, we use a machine learning algorithm called Nonlinear Laplacian Spectral Analysis (NLSA), which has emerged as a promising technique for studying the dynamics of complex systems. In this work, we demonstrate the power of this algorithm using synthetic x-ray diffraction snapshots from a protein with significant data incompleteness, timing uncertainties, and noise. Our study confirms that NLSA is a suitable approach that effectively mitigates the effects of these artifacts in TR-SFX data and recovers accurate structural dynamics information hidden in such data.

Trujillo, Justin (ORCID:0000000285505360)↗

Randomized Algorithms for Linear Solvers

Recently, randomized algorithms in numerical linear algebra, specifically those centered around random sketching, have gained traction in primarily theoretical research due to their potential to significantly reduce problem dimensionality at the cost of an O(1) multiplicative distortion factor. It has been assumed that this sketching can be done efficiently, but thorough investigation into how precisely to do it has been neglected. Moreover, the theory-based community has argued for sketching’s ability to reduce computational cost via complexity analysis, but has not researched how it affects the stability of the algorithms. At Sandia, efficient linear solvers that scale well on modern HPC architectures while maintaining stability are imperative for practical applications. In this LDRD, we developed a random sketching strategy that is substantially faster than existing ones, and demonstrate its superior performance in practice on a NVIDIA H100 GPU. Moreover, we show how this can be used to significantly outperform existing linear least squares solvers while improving the solver’s stability as well. Additionally, we demonstrate how this sketching strategy can be used to make a fast, stable QR factorization that can subsequently be used in s-step and block Krylov solvers. Finally, we incorporate a sketching-based block orthogonalization scheme into s-step GMRES, which is stable and faster than existing approaches on the Perlmutter supercomputer.

97 MATHEMATICS AND COMPUTING↗

Understanding nanoscale structural distortions in Pb(Zr 0.2 Ti 0.8 )O 3 by utilizing X-ray nanodiffraction and clustering algorithm analysis

Hard X-ray nanodiffraction provides a unique nondestructive technique to quantify local strain and structural inhomogeneities at nanometer length scales. However, sample mosaicity and phase separation can result in a complex diffraction pattern that can make it challenging to quantify nanoscale structural distortions. In this work, a k-means clustering algorithm was utilized to identify local maxima of intensity by partitioning diffraction data in a three-dimensional feature space of detector coordinates and intensity. This technique has been applied to X-ray nanodiffraction measurements of a patterned ferroelectric PbZr 0.2 Ti 0.8 O 3 sample. The analysis reveals the presence of two phases in the sample with different lattice parameters. A highly heterogeneous distribution of lattice parameters with a variation of 0.02 Å was also observed within one ferroelectric domain. This approach provides a nanoscale survey of subtle structural distortions as well as phase separation in ferroelectric domains in a patterned sample.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Partitioning of Large-Scale Power Electronics-Based Power Systems for Small-Signal Stability Analysis

The nodal admittance matrix (NAM)-based approach is suitable for analyzing the small-signal stability of large-scale power electronics-based power systems (PEPSs) as it preserves the system structure by utilizing the admittance matrix. Previously, NAM-based area partition has been proposed, which divides the system into various subareas and interconnections for easier analysis of the low-dimension matrix compared to the entire system-based high-dimension matrix. However, no partition algorithm has been presented for the NAM-based area partition method. This paper focuses on implementing the spectral partitioning algorithm for partitioning large-scale PEPSs into a low-dimension matrix to reduce the computation complexity of the analysis. These spectral components facilitate data transformation into a new space, enabling the application of traditional clustering methods like k-means. To evaluate the performance of the partitioning method, the subareas and interconnections obtained from the spectral clustering algorithm are incorporated into the NAM-based area partition method for a large system with 140 buses. The computational times of the original method, where the NAM-based criterion is directly applied to the entire system, are compared with those of the NAM-based partition method in MATLAB. PSCAD simulations of the whole system and the obtained subareas are conducted to validate the effectiveness of the proposed algorithm.

Nupur, Nupur↗

Assessment of Local Observation of Atomic Ordering in Alloys via the Radial Distribution Function: A Computational and Experimental Approach

As a powerful analytical technique, atom probe tomography (APT) has the capacity to acquire the spatial distribution of millions of atoms from a complex sample. However, extracting information at the Ångstrom-scale on atomic ordering remains a challenge due to the limits of the APT experiment and data analysis algorithms. The development of new computational tools enable visualization of the data and aid understanding of the physical phenomena such as disorder of complex crystalline structures. Here, we report progress towards this goal using two steps. We describe a computational approach to evaluate atomic ordering in the crystal structure by generating radial distribution functions (RDF). Atomic ordering is rendered as the Fractional Cumulative Radial Distribution Function (FCRDF) which allows for greater visibility of local compositions at short range in the structure. Further, we accommodate in the analysis additional parameters such as uncertainty in the atomic coordinates and the atomic abundance to ascertain short-range ordering in APT data sets. We applied the FCRDF analysis to synthetic and experimental APT data sets for Ni 3 Al. The ability to observe a signal of atomic ordering consistent with the known L1 2 crystal structure is heavily dependent on spatial uncertainty, irrespective of abundance. Detection of atomic ordering is subject to an upper limit of spatial uncertainty of atoms described with Gaussian distributions with a standard deviation of 1.3 Å. The FCRDF analysis was also applied to the APT data set for a six-component alloy, Al 1.3 CoCrCuFeNi. In this case, we are currently able to visualize elemental segregation at the nanoscale, though unambiguous identification of atomic ordering at the Ångstrom (nearest-neighbor) scale remains a goal.

36 MATERIALS SCIENCE↗

A novel framework for hosting capacity analysis with spatio-temporal probabilistic voltage sensitivity analysis

Smart grids are envisioned to accommodate high penetration of distributed photovoltaic (PV) generation, which may cause adverse grid impacts in terms of voltage violations. Therefore, PV Hosting capacity is being used as a planning tool to determine the maximum PV installation capacity that causes the first voltage violation and above which would require infrastructure upgrades. Additionally, traditional methods of Hosting capacity analysis are scenario based and computationally complex as they rely on iterative load flow algorithms that require investigating a large number of scenarios for accurate assessment of PV impacts. Therefore, this paper presents a computationally efficient analytical approach to compute the probability distribution of voltage change due to random behavior of randomly located multiple distributed PVs. The proposed approach is based on Spatio-temporal probabilistic voltage sensitivity analysis that exploits both spatial and temporal uncertainties associated with PV injections. Thereafter, the derived distribution is used to quantify voltage violations for various PV penetration levels and subsequently determine the hosting capacity of the system without the need to examine large number of scenarios. Results of the proposed framework are validated via conventional load flow based simulation approach on the IEEE 37 and IEEE 123 node test systems.

42 ENGINEERING↗

A robust clustering algorithm for analysis of composition-dependent organic aerosol thermal desorption measurements

Abstract. One of the challenges of understanding atmospheric organic aerosol (OA) particles stems from its complex composition. Mass spectrometry is commonly used to characterize the compositional variability of OA. Clustering of a mass spectral dataset helps identify components that exhibit similar behavior or have similar properties, facilitating understanding of sources and processes that govern compositional variability. Here, we developed an algorithm for clustering mass spectra, the noise-sorted scanning clustering (NSSC), appropriate for application to thermal desorption measurements of collected OA particles from the Filter Inlet for Gases and AEROsols coupled to a chemical ionization mass spectrometer (FIGAERO-CIMS). NSSC, which extends the common density-based special clustering of applications with noise (DBSCAN) algorithm, provides a robust, reproducible analysis of the FIGAERO temperature-dependent mass spectral data. The NSSC allows for the determination of thermal profiles for compositionally distinct clusters of mass spectra, increasing the accessibility and enhancing the interpretation of FIGAERO data. Applications of NSSC to several laboratory biogenic secondary organic aerosol (BSOA) systems demonstrate the ability of NSSC to distinguish different types of thermal behaviors for the components comprising the particles along with the relative mass contributions and chemical properties (e.g., average molecular formula) of each mass spectral cluster. For each of the systems examined, more than 80 % of the total mass is clustered into 9–13 mass spectral clusters. Comparison of the average thermograms of the mass spectral clusters between systems indicates some commonality in terms of the thermal properties of different BSOA, although with some system-specific behavior. Application of NSSC to sets of experiments in which one experimental parameter, such as the concentration of NO, is varied demonstrates the potential for mass spectral clustering to elucidate the chemical factors that drive changes in the thermal properties of OA particles. Further quantitative interpretation of the thermograms of the mass spectral clusters will allow for a more comprehensive understanding of the thermochemical properties of OA particles.

54 ENVIRONMENTAL SCIENCES↗

DECA: scalable XHMM exome copy-number variant calling with ADAM and Apache Spark

Abstract Background XHMM is a widely used tool for copy-number variant (CNV) discovery from whole exome sequencing data but can require hours to days to run for large cohorts. A more scalable implementation would reduce the need for specialized computational resources and enable increased exploration of the configuration parameter space to obtain the best possible results. Results DECA is a horizontally scalable implementation of the XHMM algorithm using the ADAM framework and Apache Spark that incorporates novel algorithmic optimizations to eliminate unneeded computation. DECA parallelizes XHMM on both multi-core shared memory computers and large shared-nothing Spark clusters. We performed CNV discovery from the read-depth matrix in 2535 exomes in 9.3 min on a 16-core workstation (35.3× speedup vs. XHMM), 12.7 min using 10 executor cores on a Spark cluster (18.8× speedup vs. XHMM), and 9.8 min using 32 executor cores on Amazon AWS’ Elastic MapReduce. We performed CNV discovery from the original BAM files in 292 min using 640 executor cores on a Spark cluster. Conclusions We describe DECA’s performance, our algorithmic and implementation enhancements to XHMM to obtain that performance, and our lessons learned porting a complex genome analysis application to ADAM and Spark. ADAM and Apache Spark are a performant and productive platform for implementing large-scale genome analyses, but efficiently utilizing large clusters can require algorithmic optimizations and careful attention to Spark’s configuration parameters.

Linderman, Michael D. (ORCID:0000000296437148)↗

Approximate Scheduling of DERs with Discrete Complex Injections

Rapid penetration of renewable energy based Distributed Energy Resources (DER) has the potential to exacerbate the challenges inherent in grid frequency and voltage regulation. However, their real time controllability can be leveraged to not only mitigate such challenges, but improve the economics and quality of grid operations. A plethora of DER scheduling algorithms have been developed for fast and efficient scheduling of these resources. These algorithms schedule the complex - real and reactive power injected into (or drawn from) the grid by the DERs under various cost objective functions and grid constraints. However, a vast majority of such algorithms assume the feasible range of power injections to be continuous. In reality, the control options available for several DERs form a discrete space. This implies that the feasible range of power injections also forms a discrete space. This makes DER scheduling an NP-hard problem. Integer/Mixed Integer program based algorithms, which guarantee optimality in the objective value, have been developed. But these are prohibitively expensive in terms of computational time requirements. On the other hand, fast heuristic based solutions have also been developed. But as they do not provide any guarantee on the optimality of the objective, or on satisfying the constraints, they are unreliable for grid operations. Recent works have developed approximation algorithms which offer the best of both the approaches above: (near) optimality and low computational complexity, both of which are governed by a user defined accuracy parameter ϵ. In this work, we significantly improve upon such existing works by developing an approximation algorithm which schedules DERs with complex injections (as opposed to only real injection) and whose runtime is polynomial (as opposed to exponential) in 1/ϵ. We provide theoretical analysis and support them with experimental results to validate the guarantees provided by our approximation algorithm.

14 SOLAR ENERGY↗

PIPER: Performance Insights for Programmers and Exascale Runtimes

During the lifetime of the project, the PIPER at the University of Utah worked in collaboration with the team from the partner institutions to establish a set of software tools for analyzing and improving the performance parallel computing tools. These activities complement and complete the work performed by the other X-Stack 2 projects with the definition of a common data models and computing infrastructures, which have been a central element in the targeted performance analysis pipeline and new programming models. The University of Utah team have focused mainly on developing data analysis and visualization systems to facilitate exploration, comparison and evaluation of the behavior and performance of complex algorithms in modern HPC infrastructures. This is involved several demonstrations of the performance achieved and presentation of the results in a way that facilitates the users understand bottlenecks and ways to overcome them. One major focus of the University of Utah activities has been the analysis of the performance characteristics of Fat-Tree and Dragonfly topology networks. The work involved the development of practical visualization systems especially in collaboration with the team at LLNL, and published several papers and gave invited talks at prestigious venues such as the Salishan Conference on High-Speed Computing or the International Conference on High Performance Computing, Data, and Analytics. In addition, the university of Utah team has advanced the core activities on analyzing the performance characteristics of I/O and other data movement systems and their practical use for scaling Uintah and other simulation codes poised for use in the exascale computing environments of the future.

42 ENGINEERING↗

Optimization using pathwise algorithmic derivatives of electromagnetic shower simulations

Among the well-known methods to approximate derivatives of expectancies computed by Monte-Carlo simulations, averages of pathwise derivatives are often the easiest one to apply. Computing them via algorithmic differentiation typically does not require major manual analysis and rewriting of the code, even for very complex programs like simulations of particle-detector interactions in high-energy physics. However, the pathwise derivative estimator can be biased if there are discontinuities in the program, which may diminish its value for applications. This work integrates algorithmic differentiation into the electromagnetic shower simulation code HepEmShow based on G4HepEm, allowing us to study how well pathwise derivatives approximate derivatives of energy depositions in a sampling calorimeter with respect to parameters of the beam and geometry. We found that when multiple scattering is disabled in the simulation, means of pathwise derivatives converge quickly to their expected values, and these are close to the actual derivatives of the energy deposition. Additionally, we demonstrate the applicability of this novel gradient estimator for stochastic gradient-based optimization in a model example.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗