Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Computational Complexity”

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 1,351 records · Page 75

Chaos, complexity, and random matrices

Chaos and complexity entail an entropic and computational obstruction to describing a system, and thus are intrinsically difficult to characterize. In this paper, we consider time evolution by Gaussian Unitary Ensemble (GUE) Hamiltonians and analytically compute out-of-time-ordered correlation functions (OTOCs) and frame potentials to quantify scrambling, Haar-randomness, and circuit complexity. While our random matrix analysis gives a qualitatively correct prediction of the late-time behavior of chaotic systems, we find unphysical behavior at early times including an O(1) scrambling time and the apparent breakdown of spatial and temporal locality. The salient feature of GUE Hamiltonians which gives us computational traction is the Haar-invariance of the ensemble, meaning that the ensemble-averaged dynamics look the same in any basis. Motivated by this property of the GUE, we introduce k-invariance as a precise definition of what it means for the dynamics of a quantum system to be described by random matrix theory. Here,we envision that the dynamical onset of approximate k-invariance will be a useful tool for capturing the transition from early-time chaos, as seen by OTOCs, to late-time chaos, as seen by random matrix theory.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations

In this work, we present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume or finite-element discretization of high-frequency wave equations. The proposed solver leverages the butterfly algorithm and its hierarchical matrix extension for compressing and factorizing large frontal matrices via graph-distance guided entry evaluation or randomized matrix-vector multiplication-based schemes. Complexity analysis and numerical experiments demonstrate $\mathcal{O}(N\log^2 N)$ computation and $\mathcal{O}(N)$ memory complexity when applied to an $N\times N$ sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.

97 MATHEMATICS AND COMPUTING↗

Predicting synthetic rescues in metabolic networks

An important goal of medical research is to develop methods to recover the loss of cellular function due to mutations and other defects. Many approaches based on gene therapy aim to repair the defective gene or to insert genes with compensatory function. Here, we propose an alternative, network-based strategy that aims to restore biological function by forcing the cell to either bypass the functions affected by the defective gene, or to compensate for the lost function. Focusing on the metabolism of single-cell organisms, we computationally study mutants that lack an essential enzyme, and thus are unable to grow or have a significantly reduced growth rate. We show that several of these mutants can be turned into viable organisms through additional gene deletions that restore their growth rate. In a rather counterintuitive fashion, this is achieved via additional damage to the metabolic network. Using flux balance-based approaches, we identify a number of synthetically viable gene pairs, in which the removal of one enzyme-encoding gene results in a non-viable phenotype, while the deletion of a second enzyme-encoding gene rescues the organism. The systematic network-based identification of compensatory rescue effects may open new avenues for genetic interventions.

59 BASIC BIOLOGICAL SCIENCES↗

Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness

We report the accuracy of deep learning, i.e., deep neural networks, can be characterized by dividing the total error into three main types: approximation error, optimization error, and generalization error. Whereas there are some satisfactory answers to the problems of approximation and optimization, much less is known about the theory of generalization. Most existing theoretical works for generalization fail to explain the performance of neural networks in practice. To derive a meaningful bound, we study the generalization error of neural networks for classification problems in terms of data distribution and neural network smoothness. We introduce the cover complexity (CC) to measure the difficulty of learning a data set and the inverse of the modulus of continuity to quantify neural network smoothness. A quantitative bound for expected accuracy/error is derived by considering both the CC and neural network smoothness. Although most of the analysis is general and not specific to neural networks, we validate our theoretical assumptions and results numerically for neural networks by several data sets of images. The numerical results confirm that the expected error of trained networks scaled with the square root of the number of classes has a linear relationship with respect to the CC. We also observe a clear consistency between test loss and neural network smoothness during the training process. In addition, we demonstrate empirically that the neural network smoothness decreases when the network size increases whereas the smoothness is insensitive to training dataset size.

97 MATHEMATICS AND COMPUTING↗

Compressed Sensing with Sparse Corruptions: Fault-Tolerant Sparse Collocation Approximations

The recovery of approximately sparse or compressible coefficients in a polynomial chaos expansion is a common goal in many modern parametric uncertainty quantification (UQ) problems. However, relatively little effort in UQ has been directed toward theoretical and computational strategies for addressing the sparse corruptions problem, where a small number of measurements are highly corrupted. Such a situation has become pertinent today since modern computational frameworks are sufficiently complex with many interdependent components that may introduce hardware and software failures, some of which can be difficult to detect and result in a highly polluted simulation result. In this paper we present a novel compressive sampling--based theoretical analysis for a regularized $\ell^1$ minimization algorithm that aims to recover sparse expansion coefficients in the presence of measurement corruptions. Our recovery results are uniform (the theoretical guarantees hold for all compressible signals and compressible corruptions vectors) and prescribe algorithmic regularization parameters in terms of a user-defined a priori estimate on the ratio of measurements that are believed to be corrupted. We also propose an iteratively reweighted optimization algorithm that automatically refines the value of the regularization parameter and empirically produces superior results. Lastly, our numerical results test our framework on several medium to high dimensional examples of solutions to parameterized differential equations and demonstrate the effectiveness of our approach.

97 MATHEMATICS AND COMPUTING↗

Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations

The recovery of approximately sparse or compressible coefficients in a polynomial chaos expansion is a common goal in many modern parametric uncertainty quantification (UQ) problems. However, relatively little effort in UQ has been directed toward theoretical and computational strategies for addressing the sparse corruptions problem, where a small number of measurements are highly corrupted. Such a situation has become pertinent today since modern computational frameworks are sufficiently complex with many interdependent components that may introduce hardware and software failures, some of which can be difficult to detect and result in a highly polluted simulation result. In this paper we present a novel compressive sampling-based theoretical analysis for a regularized t1 minimization algorithm that aims to recover sparse expansion coefficients in the presence of measurement corruptions. Our recovery results are uniform (the theoretical guarantees hold for all compressible signals and compressible corruptions vectors), and prescribe algorithmic regularization parameters in terms of a user-defined a priori estimate on the ratio of measurements that are believed to be corrupted. We also propose an iteratively reweighted optimization algorithm that automatically refines the value of the regularization parameter, and empirically produces superior results. Our numerical results test our framework on several medium-to-high dimensional examples of solutions to parameterized differential equations, and demonstrate the effectiveness of our approach.

97 MATHEMATICS AND COMPUTING↗

The RAJA Portability Layer: Overview and Status

As computer architectures become increasingly complex and diverse, application developers face difficult challenges to achieve high performance while maintaining code portability. The problem is especially acute for large ASC multiphysics codes. Efficient parallel execution often requires tuning algorithms and data access to match processor and memory system constraints. Changing compiler directives and parallel programming model constructs on thousands of individual loops in a large code is disruptive and unwieldy. RAJA is a programming approach that we have been developing at Lawrence Livermore National Laboratory to encapsulate platform-specific concerns, related to both hardware and parallel programming models. The RAJA abstraction layer simplifies porting C/C++ codes to various programming models and architectures by reducing effort and developer disruption. In this report, we motivate and describe key aspects of RAJA. We also present a preliminary assessment of RAJA based on exploration in three ASC hydrodynamics codes at LLNL, which was one part of a three-part ASC Level 2 milestone, completed in September 2014.

97 MATHEMATICS AND COMPUTING↗

Dislocation Patterning in Deforming Crystals: Theory, Computational Predictions and Validation (Final Technical Report)

This project was awarded for an initial period of three years, followed by a no-cost extension for one year and a funded one-year renewal. During the first four years, the project focused on investigating the role of dislocation reactions and dislocation correlation in dislocation patterning in FCC metals. During the fifth year, the scope of research was expanded to investigate the effects of composition inhomogeneity on the mesoscale plastic response of Body-Centered Cubic (BCC) alloys. In addition to its impact on metal hardening during deformation, dislocation patterning provides the microstructure information required to understand phenomena like fracture and recrystallization in metals. The Continuum Dislocation Dynamics (CDD) framework was the methodology used during the first four years, followed by the use of Discrete Dislocation Dynamics (DDD) during the fifth year. CDD is a density-based formalism of dislocation dynamics in which the plastic deformation of crystals is predicted together with the mesoscale dislocation patterns by tracking the space-time evolution of dislocations as driven by the applied stress, short-range and long-range interactions of dislocations, and cross slip. CDD is a crystal mechanics approach in which the plastic constitutive part is replaced with the equations of dislocation dynamics, which is driven by the internal stress via a mobility laws, while the evolution of the density gives the eigenstrain required to update the internal stress itself. The governing equations are thus those of crystal mechanics cast as an eigenstrain problem and those of dislocation transport and reactions. Our investigations during the first four years were driven by the hypothesis that that dislocation patterning is triggered by spatiotemporal dislocation density and internal stress fluctuations, and that such fluctuations influence the collective dislocation dynamic through their effects on the short-range reaction rates and the collective dislocation mobility. This hypothesis was tested by modeling the influence of the dislocation reactions and dislocation correlations on collective dislocation dynamics. The main research components during the first four years were: 1) Reformulation of the CDD framework to integrate the dislocation correlations and dislocation reactions. 2) Simulation of the dislocation correlations and quantifying their contribution to the long-range stress of complex dislocation systems. 3) Computational implementation of the updated CDD model for FCC single crystals and development of an efficient CDD code. 4) Investigation of dislocation patterning in FCC crystals based on the updated CDD model. Some key findings from these investigations were: 1) The patterning of dislocations is initiated by cross slip and internal stress fluctuations, and the refinement of the pattern results from junction formation. 2) Patterning is more prominent under high stress. 3) The correlation stress was found to be a significant part of the mean field stress in continuum representations of dislocation dynamics. During the last year of the project, we have established a method for performing dislocation dynamics in inhomogeneous alloys and demonstrated the impact of composition inhomogeneity on the characteristics of initial yielding and dislocation character in BCC alloys. We also tested this method using an irradiated ferritic alloy in which the composition and dislocation loops effects are both present. In doing so, we have considered two aspects of the role of inhomogeneity, the creation of internal coherency stress due to the dependence of the lattice parameter on the local composition, and the dependence of the dislocation mobility on the local composition. These two aspects resulted in an unexpected behavior of the dislocation system, and, in turn, the yielding behavior of BCC alloys. Key findings include: 1) The composition inhomogeneity in BCC alloys alters the well-known role of screw dislocations by forcing a level of waviness on the average dislocation character, thus destroying the screw character dominance in the yielding observed in pure or homogeneous BCC metals. 2) In the case of irradiated alloys, while composition inhomogeneity by itself and dislocation loops by themselves result in some hardening, the superposition of the two mechanisms does not result in the sum of the two contributions via any known rule. The latter result contradicts the classical works related hardening via multiple mechanisms, which state that various hardening mechanisms can be added linearly or using some Pythagorean additive rule. We were able to rationalize this unexpected result by a closer loop at the origin of the hardening mechanisms themselves, which both involved long-range elastic interactions with dislocations. We reached the conclusion that the hardening resulting from the total stress associated with these two mechanisms (current work) differs from the sum of the effects of the individual stress fields (classical literature). We have also found a major flaw in the classical theory of spinodal hardening. The latter theory never considered the impact of composition undulation on the solute hardening. We have built a new general theory accounting for the effect of solute friction together with the composition undulations on the dislocation configuration at Critical Resolved Shear Stress (CRSS), which is yielding a new definition of the spinodal hardening and new different results. This work is the first to recognize the lack of the role of solute in spinodal hardening theory of alloys.

36 MATERIALS SCIENCE↗

Leveraging Machine Learning Capabilities for the Characterization of Irradiated Uranium: A Case Study of Analysis Methods for Nuclear Safeguards and Nuclear Forensics

Nondestructively determining the initial enrichment of irradiated uranium is a complex and laborious multivariable problem due to the presence of fission products. This work demonstrates the capabilities of machine learning to analyze gamma-ray spectral data to determine initial enrichment without knowledge of the decay time of the sample. The approach developed is agnostic to the particular scenario and is applicable to a wide variety of applications in nuclear forensics and nuclear safeguards. We irradiated 5 mg uranium standard reference materials at discrete enrichment values ranging from 0.02% to 97% 235 U (weight percent) in UT Austin’s Nuclear Engineering Teaching Laboratory TRIGA Mark II 1.1 MW research reactor, allowed each to decay for 8 hours, and then measured each sample via gamma-ray spectrometry for 50 hours post-irradiation yielding 1,400 individual gamma-ray spectra discretized into 8,192 energy bins. We then trained decision trees models to analyze individual gamma-ray spectra and estimate the associated initial enrichment without knowledge of the time since end of irradiation. We evaluated the performance of the models with a reserved test set not used for training or calibrating the model. A decision tree model constructed with this procedure achieved a mean absolute error in initial enrichment determination of 2.3% (weight percent 235 U). Next, we implemented a principal component analysis pre-processing routine of the gamma-ray spectrometry data to reduce the dimensionality of the dataset from 8,192 channels in the spectrum to 10 principal components while retaining over 99% of the inherent variance in the data. Decision tree models constructed with these data demonstrated decreased mean absolute error in enrichment determination, reduced computational time, and decreased complexity. A single decision tree model constructed with this procedure achieved a mean absolute error in initial enrichment determination of 0.05% (weight percent 235 U). Furthermore, we analyzed these models with learning curves to ensure that overfitting did not occur. The capabilities provided by these models can be naturally extended to other application-focused measurements in the fields of nuclear safeguards, nuclear forensics, and nuclear non-proliferation.

Drescher, Adam↗

BIPSPI+: Mining Type-Specific Datasets of Protein Complexes to Improve Protein Binding Site Prediction

Computational approaches for predicting protein-protein interfaces are extremely useful for understanding and modelling the quaternary structure of protein assemblies. In particular, partner-specific binding site prediction methods allow delineating the specific residues that compose the interface of protein complexes. In recent years, new machine learning and other algorithmic approaches have been proposed to solve this problem. However, little effort has been made in finding better training datasets to improve the performance of these methods. With the aim of vindicating the importance of the training set compilation procedure, in this work we present BIPSPI+, a new version of our original server trained on carefully curated datasets that outperforms our original predictor. We show how prediction performance can be improved by selecting specific datasets that better describe particular types of protein interactions and interfaces (e.g. homo/hetero). In addition, our upgraded web server offers a new set of functionalities such as the sequence-structure prediction mode, hetero- or homo-complex specialization and the guided docking tool that allows to compute 3D quaternary structure poses using the predicted interfaces. BIPSPI+ is freely available at https://bipspi.cnb.csic.es.

59 BASIC BIOLOGICAL SCIENCES↗

Parallel Execution of Functional Mock-up Units in Buildings Modeling

A Functional Mock-up Interface (FMI) defines a standardized interface to be used in computer simulations to develop complex cyber-physical systems. FMI implementation by a software modeling tool enables the creation of a simulation model that can be interconnected, or the creation of a software library called a Functional Mock-up Unit (FMU). This report describes an FMU wrapper implementation that imports FMUs into a C++ environment and uses an Euler solver that executes FMUs in parallel using Open Multi-Processing (OpenMP). The purpose of this report is to elucidate the runtime performance of the solver when a multi-component system is imported as a single FMU (for the whole system) or as multiple FMUs (for different groups of components as sub-systems). This performance comparison is conducted using two test cases: (1) a simple, multi-tank problem; and (2) a more realistic use case based on the Modelica Buildings Library. In both test cases, the performance gains are promising when each FMU consists of a large number of states and state events that are wrapped in a single FMU. Load balancing is demonstrated to be a critical factor in speeding up parallel execution of multiple FMUs.

97 MATHEMATICS AND COMPUTING↗

A Bayesian Approach for Quantifying Data Scarcity when Modeling Human Behavior via Inverse Reinforcement Learning

Computational models that formalize complex human behaviors enable study and understanding of such behaviors. However, collecting behavior data required to estimate the parameters of such models is often tedious and resource intensive. Thus, estimating dataset size as part of data collection planning (also known as Sample Size Determination) is important to reduce the time and effort of behavior data collection while maintaining an accurate estimate of model parameters. In this paper, we present a sample size determination method based on Uncertainty Quantification (UQ) for a specific Inverse Reinforcement Learning (IRL) model of human behavior, in two cases: 1) pre-hoc experiment design—conducted in the planning stage before any data is collected, to guide the estimation of how many samples to collect; and 2) post-hoc dataset analysis—performed after data is collected, to decide if the existing dataset has sufficient samples and whether more data is needed. Here, we validate our approach in experiments with a realistic model of behaviors of people with Multiple Sclerosis (MS) and illustrate how to pick a reasonable sample size target. Our work enables model designers to perform a deeper, principled investigation of effects of dataset size on IRL.

97 MATHEMATICS AND COMPUTING↗

Time Series Dimension Reduction for Surrogate Models of Port Scanning Cyber Emulations

Surrogate model development is a key resource in the scientific modeling community for providing computational expedience when simulating complex systems without loss of great fidelity. The initial step to development of a surrogate model is identification of the primary governing components of the system. Principal component analysis (PCA) is a widely used data science technique that provides inspection of such driving factors, when the objective for modeling is to capture the greatest sources of variance inherent to a dataset. Although an efficient linear dimension reduction tool, PCA makes the fundamental assumption that the data is continuous and normally distributed. Thus, it provides ideal performance when these conditions are met. In the case for which cyber emulations provide realizations of a port scanning scenario, the data to be modeled follows a discrete time series function comprised of monotonically increasing piece-wise constant steps. The sources of variance are related to the timing and magnitude of these steps. Therefore, we consider using XPCA, an extension to PCA for continuous and discrete random variates. This report provides the documentation of the trade-offs between the PCA and XPCA linear dimension reduction algorithms, for the intended purpose to identify key components of greatest variance in our time series data. These components will ultimately provide the basis for future surrogate models of port scanning cyber emulations.

97 MATHEMATICS AND COMPUTING↗

Mixed-mode oscillations in a three-timescale coupled Morris–Lecar system

Mixed-mode oscillations (MMOs) are complex oscillatory behaviors of multiple-timescale dynamical systems in which there is an alternation of large-amplitude and small-amplitude oscillations. It is well known that MMOs in two-timescale systems can arise either from a canard mechanism associated with folded node singularities or a delayed Andronov–Hopf bifurcation (DHB) of the fast subsystem. While MMOs in two-timescale systems have been extensively studied, less is known regarding MMOs emerging in three-timescale systems. In this work, we examine the mechanisms of MMOs in coupled Morris–Lecar neurons with three distinct timescales. We investigate two kinds of MMOs occurring in the presence of a singularity known as canard-delayed-Hopf (CDH) and in cases where CDH is absent. In both cases, we examine how features and mechanisms of MMOs vary with respect to variations in timescales. Our analysis reveals that MMOs supported by CDH demonstrate significantly stronger robustness than those in its absence. Moreover, we show that the mere presence of CDH does not guarantee the occurrence of MMOs. This work yields important insights into conditions under which the two separate mechanisms in two-timescale context, canard and DHB, can interact in a three-timescale setting and produce more robust MMOs, particularly against timescale variations.

97 MATHEMATICS AND COMPUTING↗

How generic is iodide-tagging photoelectron spectroscopy: An extended investigation on the Gly· X - (Gly = glycine, X = Cl or Br) complexes

We report a joint negative ion photoelectron spectroscopy (NIPES) and quantum chemical computational study on glycine-chloride/bromide complexes (denoted Gly·X - , X = Cl/Br) in close comparison to the previously studied Gly·I - cluster ion. Combining experimental NIPE spectra and theoretical calculations, various Gly·X - complexes were found to adopt the same types of low-lying isomers, albeit with different relative energies. Despite more congested spectral profiles for Gly·Cl - and Gly·Br - , spectral assignments were accomplished with the guidance of the knowledge learned from Gly·I - , where a larger spin–orbit splitting of iodine afforded well-resolved, recognizable spectral peaks. Three canonical plus one zwitterionic isomer for Gly·Cl - and four canonical conformers for Gly·Br - were experimentally identified and characterized in contrast to the five canonical ones observed for Gly·I - under similar experimental conditions. Taken together, this study investigates both genericity and variations in binding patterns for the complexes composed of glycine and various halides, demonstrating that iodide-tagging is an effective spectroscopic means to unravel diverse ion-molecule binding motifs for cluster anions with congested spectral bands by substituting the respective ion with iodide.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

SU-E-T-353: Decoding the Beam Complexity in Intensity-Modulated Radiation Therapy Plans

Purpose: Modern IMRT relies on computers to generate treatment plans of varied complexity. A highly complex treatment plan may use a large number of small and irregular beam apertures in order to achieve high dose conformity. However, excessive beam complexity can increase dosimetric uncertainty, prolong treatment time, and increase susceptibility to target or organ motion. In this study we sought to develop metrics to assess the complexity of IMRT beams and plans. Methods: Based the information of leaf positions and MU for each beam segment, we calculated the following beam complexity metrics: aperture area, shape irregularity, and beam modulation. Then these beam complexity metrics were averaged to obtain the corresponding plan complexity metrics, using the beam MUs as weighting factors. We evaluated and compared the beam and plan complexity scores for 65 IMRT plans from 3 sites (prostate, head and neck, and spine). We also studied how the plan complexity scores were affected by adjusting inverse planning parameters. Results: For prostate IMRT, the lateral beams had large MUs and smaller shape irregularity, while the anterior or posterior beams had larger modulation values. On average, the prostate IMRT plans had the smallest shape irregularity and beam modulation; the HN IMRT plans had the largest aperture area, shape irregularity, and beam modulation; and the spine stereotactic IMRT plans often had small aperture area, which may be associated with relatively large discrepancies between calculated and measures doses. The plan complexity increased as the number of optimization iterations and the number of beam segments increased and as the minimum segment area decreased. Conclusion: Complexity of IMRT beams and plans were quantified in terms of aperture area, shape irregularity and beam modulation. The complexity metrics varied among IMRT plans for different disease sites and were affected when the planning parameters were adjusted.

60 APPLIED LIFE SCIENCES↗

The Changing Paradigm of Data Intensive Computing

Data intensive computing facilitates human understanding of complex problems that must process massive amounts of data. Through the development of new classes of software, algorithms and hardware, data intensive applications provide timely and meaningful analytical results in response to exponentially growing data complexity and associated analysis requirements. This paper considers some of the application drivers for the evolution of data intensive computing from storage centric to analysis centric requirements.

97 MATHEMATICS AND COMPUTING↗

Design and reactivity of pentapyridyl metal complexes for ammonia oxidation

Oxidation of NH3 to N2 by pentapyridyl metal complexes via hydrogen atom abstraction was investigated computationally. Quantum chemical analysis reveals insights on orbital symmetry requirements for efficient NH3 oxidation. The most promising complex, [(PY5)Mo(NH3)]2+, was studied experimentally. It shows conversion of NH3 to N2 upon treatment with 2,4,6-tri-tertbutylphenoxyl radical.

Johnson, Samantha JI↗