Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “trees (mathematics)”

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Software Verification Toolkit (SVT): Survey on Available Software Verification Tools and Future Direction

Writing software is difficult. However, writing complex, well tested and designed, and functionally correct software is incredibly difficult. An entire field of study is devoted to the validation and verification of software to address this problem, and in this paper we analyze the landscape of currently available third party software. We have divided our analyses into three separate subsections with regards to software validation: formal methods, static analysis, and test generation. Formal verification is the most complex method in which to validate software correctness, but also the most thorough as it truly validates the mathematical validity of the source code. Static analysis generally is relegated to abstract syntax tree traversal techniques to find errors related to faulty software such as memory leaks or stack overflow issues. Automatic test generation is similar in implementation to static analysis, but pushes a bit further in verifying the boundedness of function inputs and outputs with regards to annotated or parsed criteria. The crux of this report is to analyze and describe the software tools that implement these techniques to validate and verify software. Pros and cons related to installation, utilization, and capabilities of the frameworks are described, and reproducible examples are provided with a focus on usability. The initial survey concluded that the most interesting tools of note are Z3, Isabelle/HOL, and TLA+ with regards to formal verification; and Infer, Frama-C, and SonarQube with regards to static analysis. With these tools in mind, a final conjecture is provided that describes future avenues of utilizing these tools for developing a verification framework to assist in validating existing software at Sandia National Laboratories.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Mixed Integer Nonlinear Programming Approaches to Enhance Resiliency and Response Strategies in Critical Infrastructure

Motivation. Critical infrastructures are large, complex engineered systems that must be operated robustly under abnormal conditions resulting from natural hazards or intentional acts. For example, electric power systems must be robust to line faults, water utilities must rapidly mitigate contamination incidents, and computing networks must adapt to adversarial intrusions to protect critical information. Problem. It is difficult for decision-makers within resiliency analysis in critical infrastructure to optimize designs and develop effective response strategies that can account for uncertainties. Facing incomplete information and the sheer scope that a natural hazard or attack vector may incorporate, response can be ineffective without reliable, scalable decision support tools. These problems are intrinsically nonlinear and involve discrete decisions, and unfortunately, existing off-the-shelf mathematical programming methods cannot support optimization-based decision-making of these nonlinear at scale. Method/Approach and Results. This project emphasized development of fundamental optimization strategies that supported real- time mitigation and response for critical infrastructures. In particular, the project developed multi- tree approaches based on piecewise outer-approximations for solution of mixed-integer nonlinear programming (MINLP) problems. These techniques alternate between an MILP or MISOCP relaxation to obtain a lower bound and candidate discrete solutions and an NLP subproblem to obtain upper bounds. Using tailored relaxations based on problem structure, these methods were used to solve several key applications in resilience and response of critical infrastructure. This work resulted in two open-source, copyrighted software packages: CORAMIN (https://github.com/Coramin/Coramin) -- an object-oriented mathematical programming framework that supports tailored multi-tree algorithms for solution of large- scale mixed-integer nonlinear programming; and EGRET (Electrical Grid Research and Engineering Toolkit) (https://github.com/grid- parity-exchange/Egret) -- a declarative mathematical programming framework built upon CORAMIN and Pyomo for formulation and solution of resilience and operations problems in power grid systems. Furthermore, these tools resulted in several important published results, including the following: The first known global optimization approach that could solve the unit-commitment problem with nonlinear power flow constraints on medium-sized test problems; Improved parallel optimization-based bounds tightening and strengthening of relaxations of AC power flow constraints; and, Optimization-based approaches for improved grid resilience and use of demand response to improve grid resilience with reduction in capital requirements. Result Implications. This project developed first-of-a-kind algorithms for decision-making in critical infrastructure resilience operations and planning, as well as a next-generation toolkit for MINLP researchers. These approaches leveraged high-performance computing architectures to solve some of the largest, most challenging nonlinear discrete optimization problems to global optimality, and these successes were captured in open-source software to enable optimization-based decision-making, and efficient solution of MINLP formulations for electric power transmission grids.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

Range-based memory system

A mechanism is provided for efficient coherence state modification of cached data stored in a range of addresses in a coherent data processing system in which data coherency is maintained across multiple caches. A tag search structure is maintained that identifies address tags and coherence states of cached data indexed by address tags. In response to a request from a device internal to or external from the coherence network, the tag search structure is searched to identify address tags of cached data for which the coherence state is to be modified and requests are issued in the data processing system to modify a coherence state of cached lines with the identified address tags. The request from the external device may specify a range of addresses for which a coherence state change is sought. The tag search structure may be implemented as search tree, for example.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Matching Complexes of Trees and Applications of the Matching Tree Algorithm

A matching complex of a simple graph G is a simplicial complex with faces given by the matchings of G. The topology of matching complexes is mysterious; there are few graphs for which the homotopy type is known. Marietti and Testa showed that matching complexes of forests are contractible or homotopy equivalent to a wedge of spheres. We study two specific families of trees. For caterpillar graphs, we give explicit formulas for the number of spheres in each dimension and for perfect binary trees we find a strict connectivity bound. We also use a tool from discrete Morse theory called the Matching Tree Algorithm to study the connectivity of honeycomb graphs, partially answering a question raised by Jonsson.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2011

Canopy Spectral Invariants. Part 1: A New Concept in Remote Sensing of Vegetation

The concept of canopy spectral invariants expresses the observation that simple algebraic combinations of leaf and canopy spectral reflectance become wavelength independent and determine two canopy structure specific variables the recollision and escape probabilities. These variables specify an accurate relationship between the spectral response of a vegetation canopy to incident solar radiation at the leaf and the canopy scale. They are sensitive to important structural features of the canopy such as forest cover, tree density, leaf area index, crown geometry, forest type and stand age. This paper presents the mathematical basis of the concept which is linked to eigenvalues and eigenvectors of the three-dimensional radiative transfer equation.

Knyazikhin, Yuri↗
DOE OSTI2020

Linking classical PRA models to a dynamic PRA

Here, this paper presents a series of methods designed to incorporate classical Probabilistic Risk Assessment (PRA) models such as Event Trees (ETs) and Fault Trees (FTs) into dynamic PRA. In contrast to classical PRA, dynamic PRA couples stochastic methods with system simulators to determine the risks associated with complex systems such as nuclear power plants. Compared with classical PRA methods, they can evaluate with higher resolution the safety impact of timing and sequencing of events on the progression of the accident. As part of a dynamic PRA analysis, it is not uncommon that parts of the system to be analyzed might not require a computationally expensive simulation model. These parts could be in fact modeled by employing classical PRA models (e.g., a FT). Here, we present a set of methods and tools that can be used to link the most common classical PRA models (ETs, FTs, reliability block diagrams and Markov models) to simulation codes such as RELAP5-3D: creating a “hybrid PRA.” In order to show the potential of such an hybrid PRA we employ this method to verify ET modeling assumptions (e.g., success criteria) using a large break loss of coolant accident initiating event as a test case. In this respect, we link a set of FTs from the original PRA to the RELAP5-3D code and perform a hybrid PRA. The FTs are employed to model the control logic of several safety systems and to propagate component failures throughout the system. Provided the generated dynamic PRA data, we show how conservative assumptions in the original PRA can be identified and how such original PRA can be modified by updating success criteria captured by the set of RELAP5-3D simulation runs.

97 - MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A mathematical assessment of the isolation random forest method for anomaly detection in big data

We present the mathematical analysis of the Isolation Random Forest Method (IRF Method) for anomaly detection, proposed by Liu F.T., Ting K.M. and Zhou Z. H. in their seminal work as a heuristic method for anomaly detection in Big Data. We prove that the IRF space can be endowed with a probability induced by the Isolation Tree algorithm (iTree). In this setting, the convergence of the IRF method is proved, using the Law of Large Numbers. Here, a couple of counterexamples are presented to show that the method is inconclusive and no certificate of quality can be given, when using it as a means to detect anomalies. Hence, an alternative version of the method is proposed whose mathematical foundation is fully justified. Furthermore, a criterion for choosing the number of sampled trees needed to guarantee confidence intervals of the numerical results is presented. Finally, numerical experiments are presented to compare the performance of the classic method with the proposed one.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

ExTreeM: Scalable Augmented Merge Tree Computation via Extremum Graphs

Over the last decade merge trees have been proven to support a plethora of visualization and analysis tasks since they effectively abstract complex datasets. Here, this paper describes the ExTreeM-Algorithm: A scalable algorithm for the computation of merge trees via extremum graphs. The core idea of ExTreeM is to first derive the extremum graph G of an input scalar field f defined on a cell complex K, and subsequently compute the unaugmented merge tree of f on G instead of K; which are equivalent. Any merge tree algorithm can be carried out significantly faster on G, since K in general contains substantially more cells than G. To further speed up computation, ExTreeM includes a tailored procedure to derive merge trees of extremum graphs. The computation of the fully augmented merge tree, i.e., a merge tree domain segmentation of K, can then be performed in an optional post-processing step. All steps of ExTreeM consist of procedures with high parallel efficiency, and we provide a formal proof of its correctness. Our experiments, performed on publicly available datasets, report a speedup of up to one order of magnitude over the state-of-the-art algorithms included in the TTK and VTK-m software libraries, while also requiring significantly less memory and exhibiting excellent scaling behavior.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Order conditions for nonlinearly partitioned Runge-Kutta methods

Recently, a new class of nonlinearly partitioned Runge–Kutta (NPRK) methods was proposed for nonlinearly partitioned systems of autonomous ordinary differential equations y' = F(y, y). The target class of problems are those in which different scales, stiffnesses, or physics are coupled in a nonlinear way, wherein the desired partition cannot be written in a classical additive or component-wise fashion. Here we use a rooted-tree analysis to derive full-order conditions for NPRKM methods, where M denotes the number of nonlinear partitions. Due to the nonlinear coupling and thereby the mixed product differentials, it turns out that the standard node-colored rooted tree analysis used in analyzing ODE integrators does not naturally apply. Instead we develop a new edge-colored rooted-tree framework to address the nonlinear coupling. The resulting order conditions are enumerated, are provided directly for up to fourth order with M = 2 and third order with M = 3, and are related to existing order conditions of additive and partitioned RK methods. We conclude with an example that shows how the nonlinear order conditions can be used to obtain an embedded estimate of the state-dependent nonlinear coupling strength in a dynamical system.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Use of vision and sound to classify feller-buncher operational state

Productivity measures in logging involve simultaneous recognition and classification of event occurrence and timing, and the volume of stems being handled. In full-tree felling systems these measurements are difficult to implement in an autonomous manner because of the unfavorable working environment and the abundance of confounding extraneous events. This paper proposed a vision method that used a lowcost camera to recognize feller-buncher operational events including tree cutting and piling. It used a fine K-nearest neighbors (fKNN) algorithm as the final classifier based on both audio and video features derived from short video segments as inputs. The classifier’s calibration accuracy exceeds 94%. The trained model was tested on videos recorded under various conditions. The overall accurate rates for short segments were greater than 89%. Comparisons were made between the human- and algorithm derived event detection rates, events’ durations, and inter-event timing using continuously recorded videos taken during feller operation. Video results between the fKNN model and manual observation were similar. Statistical comparison using the Kolmogorov–Smirnov test to evaluate measured parameters’ distributions (manual versus automated event duration and inter-event timing) did not show significant differences with the lowest P-value among all Kolmogorov–Smirnov tests equal to 0.12. Here the result indicated the feasibility and potential of using the method for the automatic time study of drive-to-tree feller bunchers.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1975

Attitude dynamics simulation subroutines for systems of hinge-connected rigid bodies with nonrigid appendages

Three computer subroutines designed to solve the vector-dyadic differential equations of rotational motion for systems that may be idealized as a collection of hinge-connected rigid bodies assembled in a tree topology, with an optional flexible appendage attached to each body are reported. Deformations of the appendages are mathematically represented by modal coordinates and are assumed small. Within these constraints, the subroutines provide equation solutions for (1) the most general case of unrestricted hinge rotations, with appendage base bodies nominally rotating at a constant speed, (2) the case of unrestricted hinge rotations between rigid bodies, with the restriction that those rigid bodies carrying appendages are nominally nonspinning, and (3) the case of small hinge rotations and nominally nonrotating appendages. Sample problems and their solutions are presented to illustrate the utility of the computer programs.

Fleischer, G. E.↗
DOE OSTI2024

Probabilistic Context Neighborhood model for lattices

Here we present the Probabilistic Context Neighborhood model designed for two-dimensional lattices as a variation of a Markov random field assuming discrete values. In this model, the neighborhood structure has a fixed geometry but a variable order, depending on the neighbors’ values. Our model extends the Probabilistic Context Tree model, originally applicable to one-dimensional space. It retains advantageous properties, such as representing the dependence neighborhood structure as a graph in a tree format, facilitating an understanding of model complexity. Furthermore, we adapt the algorithm used to estimate the Probabilistic Context Tree to estimate the parameters of the proposed model. We illustrate the accuracy of our estimation methodology through simulation studies. Additionally, we apply the Probabilistic Context Neighborhood model to spatial real-world data, showcasing its practical utility.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Three-dimensional phenotyping of peach tree-crown architecture utilizing terrestrial laser scanning

Tree training systems for temperate fruit have been developed throughout history by pomologists to improve light interception, fruit yield, and fruit quality. These training systems direct crown and branch growth to specific configurations. Quantifying crown architecture could aid the selection of trees that require less pruning or that naturally excel in specific growing/training system conditions. Regarding peaches [Prunus persica (L.) Batsch], access tools such as branching indices have been developed to characterize tree-crown architecture. However, the required branching data (BD) to develop these indices are difficult to collect. Traditionally, BD have been collected manually, but this process is tedious, time-consuming, and prone to human error. These barriers can be circumnavigated by utilizing terrestrial laser scanning (TLS) to obtain a digital twin of the real tree. TLS generates three-dimensional (3D) point clouds of the tree crown, wherein every point contains 3D coordinates (x, y, z). To facilitate the use of these tools for peach, we selected 16 young peach trees scanned in 2021 and 2022. These 16 trees were then modeled and quantified using the open-source software TreeQSM. As a result, “in silico” branching and biometric data for the young peach trees were calculated to demonstrate the capabilities of TLS phenotyping of peach tree-crown architecture. The comparison and analysis of field measurements (in situ) and in silico BD, biometric data, and quantitative structural model branch uncertainty data were utilized to determine the reconstructive model’s reliability as a source substitute for field measurements. Mean average deviation when comparing young tree (YT) height was approx. 5.93%, with crown volume was approx. 13.26% across both 2021 and 2022. All point clouds of the YTs in 2022 showed residuals lower than 12 mm to cylinders fitted to all branches, and mean surface coverage greater than 40% for both the trunk and primary branching orders.

09 BIOMASS FUELS↗
DOE OSTI2020

A non-cooperative meta-modeling game for automated third-party calibrating, validating and falsifying constitutive laws with parallelized adversarial attacks

The evaluation of constitutive models, especially for high-risk and high-regret engineering applications, requires efficient and rigorous third-party calibration, validation and falsification. While there are numerous efforts to develop paradigms and standard procedures to validate models, difficulties may arise due to the sequential, manual, and often biased nature of the commonly adopted calibration and validation processes, thus slowing down data collections, hampering the progress towards discovering new physics, increasing expenses and possibly leading to misinterpretations of the credibility and application ranges of proposed models. This work attempts to introduce concepts from game theory and machine learning techniques to overcome many of these existing difficulties. Here, we introduce an automated meta-modeling game where two competing AI agents systematically generate experimental data to calibrate a given constitutive model and to explore its weakness such that the experiment design and model robustness can be improved through competitions. The two agents automatically search for the Nash equilibrium of the meta-modeling game in an adversarial reinforcement learning framework without human intervention. In particular, a protagonist agent seeks to find the more effective ways to generate data for model calibrations, while an adversary agent tries to find the most devastating test scenarios that expose the weaknesses of the constitutive model calibrated by the protagonist. By capturing all possible design options of the laboratory experiments into a single decision tree, we recast the design of experiments as a game of combinatorial moves that can be resolved through deep reinforcement learning by the two competing players. Our adversarial framework emulates idealized scientific collaborations and competitions among researchers to achieve a better understanding of the application range of the learned material laws and prevent misinterpretations caused by conventional AI-based third-party validation. Numerical examples are given to demonstrate the wide applicability of the proposed meta-modeling game with adversarial attacks on both human-crafted constitutive models and machine learning models.

97 MATHEMATICS AND COMPUTING↗