Search NASA⌕ Search

SEARCH · Search NASA

Results for “hierarchical algorithm”

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 163 records · Page 9

A Study of Clustering Techniques and Hierarchical Matrix Formats for Kernel Ridge Regression

We present memory-efficient and scalable algorithms for kernel methods used in machine learning. Using hierarchical matrix approximations for the kernel matrix the memory requirements, the number of floating point operations, and the execution time are drastically reduced compared to standard dense linear algebra routines. We consider both the general H matrix hierarchical format as well as Hierarchically Semi-Separable (HSS) matrices. Furthermore, we investigate the impact of several preprocessing and clustering techniques on the hierarchical matrix compression. Effective clustering of the input leads to a ten-fold increase in efficiency of the compression. The algorithms are implemented using the STRUMPACK solver library. These results confirm that - with correct tuning of the hyperparameters - classification using kernel ridge regression with the compressed matrix does not lose prediction accuracy compared to the exact - not compressed - kernel matrix and that our approach can be extended to O(1M) datasets, for which computation with the full kernel matrix becomes prohibitively expensive. We present numerical experiments in a distributed memory environment up to 1,024 processors of the NERSC's Cori supercomputer using well-known datasets to the machine learning community that range from dimension 8 up to 784.

97 MATHEMATICS AND COMPUTING↗

Using Heaps in Recursive Hierarchical Segmentation of Data

A modification to increase processing speed has been made in the algorithm and implementing software reported in Modified Recursive Hierarchical Segmentation of Data (GSC-14681-1), NASA Tech Briefs, Vol. 30, No. 6 (June 2006), page 51. That software performs recursive hierarchical segmentation of data having spatial characteristics (e.g., spectral-image data). The segmentation process includes an iterative subprocess, in each iteration of which it is necessary to determine a best pair of regions to merge [merges being justified by one or more measure(s) similarity of pixels in the regions]. In the previously reported version of the algorithm and software, the choice of a best pair of regions to merge involved the use of a fully sorted list of regions. That version was computationally inefficient because a fully sorted list is not needed: what is needed is only the identity of the pair of regions characterized by the smallest measure of dissimilarity. The present modification replaces the use of a fully sorted list with the use of data heaps, which are computationally more efficient for performing the required comparisons among dissimilarity measures. The modification includes the incorporation of standard and modified functions for creating and updating data heaps

Tilton, James C.↗

Hierarchical Distributed Voltage Regulation in Networked Autonomous Grids: Preprint

We propose a novel algorithm to solve optimal power flow (OPF) that aims at dispatching controllable distributed energy resources (DERs) for voltage regulation at minimum cost. The proposed algorithm features unprecedented scalability to large distribution networks by utilizing an information structure based on networked autonomous grids (AGs). Specifically, each AG is a subtree of a large distribution network that has a tree topology. The topology and line parameters of each AG are known only to a regional coordinator (RC) that is responsible for communicating with and dispatching the DERs within this AG. The reduced network, where each AG is treated as a node, is managed by a central coordinator (CC), which knows the topology and line parameters of the reduced network only and communicates with all the RCs. We jointly explore this information structure and the structure of the linearized distribution power flow (LinDistFlow) model to derive a hierarchical, distributed implementation of the primal-dual gradient algorithm that solves OPF. The proposed implementation significantly reduces the computation burden compared to the centrally coordinated implementation of the primal-dual algorithm. Numerical results on a 4,521-node test feeder show that the proposed hierarchical distributed algorithm can achieve more than 10-fold improvement in the speed of convergence compared to the centrally coordinated primal-dual algorithm.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Isosurface Extraction in Time-Varying Fields Using a Temporal Hierarchical Index Tree

Many high-performance isosurface extraction algorithms have been proposed in the past several years as a result of intensive research efforts. When applying these algorithms to large-scale time-varying fields, the storage overhead incurred from storing the search index often becomes overwhelming. this paper proposes an algorithm for locating isosurface cells in time-varying fields. We devise a new data structure, called Temporal Hierarchical Index Tree, which utilizes the temporal coherence that exists in a time-varying field and adoptively coalesces the cells' extreme values over time; the resulting extreme values are then used to create the isosurface cell search index. For a typical time-varying scalar data set, not only does this temporal hierarchical index tree require much less storage space, but also the amount of I/O required to access the indices from the disk at different time steps is substantially reduced. We illustrate the utility and speed of our algorithm with data from several large-scale time-varying CID simulations. Our algorithm can achieve more than 80% of disk-space savings when compared with the existing techniques, while the isosurface extraction time is nearly optimal.

Shen, Han-Wei↗

Framework for a space shuttle main engine health monitoring system

A framework developed for a health management system (HMS) which is directed at improving the safety of operation of the Space Shuttle Main Engine (SSME) is summarized. An emphasis was placed on near term technology through requirements to use existing SSME instrumentation and to demonstrate the HMS during SSME ground tests within five years. The HMS framework was developed through an analysis of SSME failure modes, fault detection algorithms, sensor technologies, and hardware architectures. A key feature of the HMS framework design is that a clear path from the ground test system to a flight HMS was maintained. Fault detection techniques based on time series, nonlinear regression, and clustering algorithms were developed and demonstrated on data from SSME ground test failures. The fault detection algorithms exhibited 100 percent detection of faults, had an extremely low false alarm rate, and were robust to sensor loss. These algorithms were incorporated into a hierarchical decision making strategy for overall assessment of SSME health. A preliminary design for a hardware architecture capable of supporting real time operation of the HMS functions was developed. Utilizing modular, commercial off-the-shelf components produced a reliable low cost design with the flexibility to incorporate advances in algorithm and sensor technology as they become available.

Hawman, Michael W.↗

Tools and Models for Integrating Multiple Cellular Networks

In this grant, we have systematically investigated the integrated networks, which are responsible for the coordination of activity between metabolic pathways in prokaryotes. We have developed several computational tools to analyze the topology of the integrated networks consisting of metabolic, regulatory, and physical interaction networks. The tools are all open-source, and they are available to download from Github, and can be incorporated in the Knowledgebase. Here, we summarize our work as follow. Understanding the topology of the integrated networks is the first step toward understanding its dynamics and evolution. For Aim 1 of this grant, we have developed a novel algorithm to determine and measure the hierarchical structure of transcriptional regulatory networks [1]. The hierarchy captures the direction of information flow in the network. The algorithm is generally applicable to regulatory networks in prokaryotes, yeast and higher organisms. Integrated datasets are extremely beneficial in understanding the biology of a system in a compact manner due to the conflation of multiple layers of information. Therefore for Aim 2 of this grant, we have developed several tools and carried out analysis for integrating system-wide genomic information. To make use of the structural data, we have developed DynaSIN for protein-protein interactions networks with various dynamical interfaces [2]. We then examined the association between network topology with phenotypic effects such as gene essentiality. In particular, we have organized E. coli and S. cerevisiae transcriptional regulatory networks into hierarchies. We then correlated gene phenotypic effects by tinkering with different layers to elucidate which layers were more tolerant to perturbations [3]. In the context of evolution, we also developed a workflow to guide the comparison between different types of biological networks across various species using the concept of rewiring [4], and Furthermore, we have developed CRIT for correlation analysis in systems biology [5]. For Aim 3, we have further investigated the scaling relationship that the number of Transcription Factors (TFs) in a genome is proportional to the square of the total number of genes. We have extended the analysis from transcription factors to various classes of functional categories, and from individual categories to joint distribution [6]. By introducing a new analytical framework, we have generalized the original toolbox model to take into account of metabolic network with arbitrary network topology [7].

09 BIOMASS FUELS↗

Multiscale registration of planning CT and daily cone beam CT images for adaptive radiation therapy

Adaptive radiation therapy (ART) is the incorporation of daily images in the radiotherapy treatment process so that the treatment plan can be evaluated and modified to maximize the amount of radiation dose to the tumor while minimizing the amount of radiation delivered to healthy tissue. Registration of planning images with daily images is thus an important component of ART. In this article, the authors report their research on multiscale registration of planning computed tomography (CT) images with daily cone beam CT (CBCT) images. The multiscale algorithm is based on the hierarchical multiscale image decomposition of E. Tadmor, S. Nezzar, and L. Vese [Multiscale Model. Simul. 2(4), pp. 554-579 (2004)]. Registration is achieved by decomposing the images to be registered into a series of scales using the (BV, L{sup 2}) decomposition and initially registering the coarsest scales of the image using a landmark-based registration algorithm. The resulting transformation is then used as a starting point to deformably register the next coarse scales with one another. This procedure is iterated at each stage using the transformation computed by the previous scale registration as the starting point for the current registration. The authors present the results of studies of rectum, head-neck, and prostate CT-CBCT registration, and validate their registration method quantitatively using synthetic results in which the exact transformations our known, and qualitatively using clinical deformations in which the exact results are not known.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Prioritized Threshold Allocation for Distributed Frequency Response

Higher penetration of renewable generation will increase the demand for adequate (and cost-effective) controllable resources on the grid that can mitigate and contain the contingencies locally before it can cause a network-wide collapse. However, end-use constraints can potentially lead to load unavailability when an event occurs, leading to unreliable demand response services. Sensors measurements and knowledge of the local load dynamics could be leveraged to improve the performance of load control algorithms. In the context of hierarchical frequency response using ensemble of switching loads, we present a metric to evaluate the fitness of each device in successfully providing the ancillary service. Furthermore a fitness-based assignment of control set-points is formulated which achieves reliable performance under different operating conditions. Monte Carlo simulations of ensembles of electric water heaters and residential air-conditioners are performed to evaluate the proposed control algorithm.

Nandanoori, Sai Pushpak↗

The application of the reduced order model Kalman filter to motion estimation of degraded image sequences

Motion estimation is a field of great interest because of its many applications in areas such as robotics and image coding. The optic flow method is one such scheme which, although fairly accurate, is prone to error in the presence of noise. This thesis describes the use of the reduced order model Kalman filter (ROMKF) in reducing errors in displacement estimation due to degradation of the sequence. The implementation of filtering and motion estimation algorithms on the SUN workstation is also discussed. Results from preliminary testing were used to determine the degrees of freedom available for the ROMKF in the SUN software. The tests indicated that increasing the state to the left leads to slight improvement over the minimum state case. Therefore, the software uses the minimum model, with the option of adding states to the left only. The ROMKF was then used in conjunction with a hierarchical pel recursive motion estimation algorithm. Applying the ROMKF to the degraded displacements themselves generally yielded slight improvements in cases with noise degradation and noise plus blur. Filtering the images of the degraded sequence prior to motion estimation was less effective in these cases. Both methods performed badly in the case of blur alone, resulting in increased displacement errors. This is thought to be due in part to filter artifacts. Some improvements were obtained by varying the filter parameters when filtering the displacements directly. This result suggests that further study in varying filter parameters may lead to better results. The results of this thesis indicate that the ROMKF can play a part in reducing motion estimation errors from degraded sequences. However, more work needs to be done before the use of the ROMKF can be a practical solution.

Simpson, Elizabeth C.↗

Reciprocal insulation analysis of Hi-C data shows that TADs represent a functionally but not structurally privileged scale in the hierarchical folding of chromosomes

Understanding how regulatory sequences interact in the context of chromosomal architecture is a central challenge in biology. Chromosome conformation capture revealed that mammalian chromosomes possess a rich hierarchy of structural layers, from multi-megabase compartments to sub-megabase topologically associating domains (TADs) and sub-TAD contact domains. TADs appear to act as regulatory microenvironments by constraining and segregating regulatory interactions across discrete chromosomal regions. However, it is unclear whether other (or all) folding layers share similar properties, or rather TADs constitute a privileged folding scale with maximal impact on the organization of regulatory interactions. Here, we present a novel algorithm named CaTCH that identifies hierarchical trees of chromosomal domains in Hi-C maps, stratified through their reciprocal physical insulation, which is a single and biologically relevant parameter. By applying CaTCH to published Hi-C data sets, we show that previously reported folding layers appear at different insulation levels. We demonstrate that although no structurally privileged folding level exists, TADs emerge as a functionally privileged scale defined by maximal boundary enrichment in CTCF and maximal cell-type conservation. By measuring transcriptional output in embryonic stem cells and neural precursor cells, we show that the likelihood that genes in a domain are coregulated during differentiation is also maximized at the scale of TADs. Finally, we observe that regulatory sequences occur at genomic locations corresponding to optimized mutual interactions at the same scale. Our analysis suggests that the architectural functionality of TADs arises from the interplay between their ability to partition interactions and the specific genomic position of regulatory sequences.

Biochemistry & Molecular Biology↗

Omniscopes: Large area telescope arrays with only NlogN computational cost

We show that the class of antenna layouts for telescope arrays allowing cheap analysis hardware (with correlator cost scaling as NlogN rather than N{sup 2} with the number of antennas N) is encouragingly large, including not only previously discussed rectangular grids but also arbitrary hierarchies of such grids, with arbitrary rotations and shears at each level. We show that all correlations for such a 2D array with an n-level hierarchy can be efficiently computed via a fast Fourier transform in not two but 2n dimensions. This can allow major correlator cost reductions for science applications requiring exquisite sensitivity at widely separated angular scales, for example, 21 cm tomography (where short baselines are needed to probe the cosmological signal and long baselines are needed for point source removal), helping enable future 21 cm experiments with thousands or millions of cheap dipolelike antennas. Such hierarchical grids combine the angular resolution advantage of traditional array layouts with the cost advantage of a rectangular fast Fourier transform telescope. We also describe an algorithm for how a subclass of hierarchical arrays can efficiently use rotation synthesis to produce global sky maps with minimal noise and a well-characterized synthesized beam.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Hardware acceleration for HPS algorithms in two and three dimensions

We provide a flexible, open-source framework for hardware acceleration, namely massively-parallel execution on general-purpose graphics processing units (GPUs), applied to the hierarchical Poincaré–Steklov (HPS) family of algorithms for building fast direct solvers for linear elliptic partial differential equations. To take full advantage of the power of hardware acceleration, we propose two variants of HPS algorithms to improve performance on two- and three-dimensional problems. In the two-dimensional setting, we introduce a novel recomputation strategy that minimizes costly data transfers to and from the GPU; in three dimensions, we modify and extend the adaptive discretization technique of Geldermans and Gillman [1] to greatly reduce peak memory usage. We provide an open-source implementation of these methods written in JAX, a high-level accelerated linear algebra package, which allows for the first integration of a high-order fast direct solver with automatic differentiation tools. We conclude with extensive numerical examples showing our methods are fast and accurate on two- and three-dimensional problems.

Fast direct solvers↗

Control algorithm implementation for a redundant degree of freedom manipulator

This project's purpose is to develop and implement control algorithms for a kinematically redundant robotic manipulator. The manipulator is being developed concurrently by Odetics Inc., under internal research and development funding. This SBIR contract supports algorithm conception, development, and simulation, as well as software implementation and integration with the manipulator hardware. The Odetics Dexterous Manipulator is a lightweight, high strength, modular manipulator being developed for space and commercial applications. It has seven fully active degrees of freedom, is electrically powered, and is fully operational in 1 G. The manipulator consists of five self-contained modules. These modules join via simple quick-disconnect couplings and self-mating connectors which allow rapid assembly/disassembly for reconfiguration, transport, or servicing. Each joint incorporates a unique drive train design which provides zero backlash operation, is insensitive to wear, and is single fault tolerant to motor or servo amplifier failure. The sensing system is also designed to be single fault tolerant. Although the initial prototype is not space qualified, the design is well-suited to meeting space qualification requirements. The control algorithm design approach is to develop a hierarchical system with well defined access and interfaces at each level. The high level endpoint/configuration control algorithm transforms manipulator endpoint position/orientation commands to joint angle commands, providing task space motion. At the same time, the kinematic redundancy is resolved by controlling the configuration (pose) of the manipulator, using several different optimizing criteria. The center level of the hierarchy servos the joints to their commanded trajectories using both linear feedback and model-based nonlinear control techniques. The lowest control level uses sensed joint torque to close torque servo loops, with the goal of improving the manipulator dynamic behavior. The control algorithms are subjected to a dynamic simulation before implementation.

Cohan, Steve↗

Accelerating multilevel Markov Chain Monte Carlo using machine learning models

Here, this work presents an efficient approach for accelerating multilevel Markov Chain Monte Carlo (MCMC) sampling for large-scale problems using low-fidelity machine learning models. While conventional techniques for large-scale Bayesian inference often substitute computationally expensive high-fidelity models with machine learning models, thereby introducing approximation errors, our approach offers a computationally efficient alternative by augmenting high-fidelity models with low-fidelity ones within a hierarchical framework. The multilevel approach utilizes the low-fidelity machine learning model (MLM) for inexpensive evaluation of proposed samples thereby improving the acceptance of samples by the high-fidelity model. The hierarchy in our multilevel algorithm is derived from geometric multigrid hierarchy. We utilize an MLM to accelerate the coarse level sampling. Training machine learning model for the coarsest level significantly reduces the computational cost associated with generating training data and training the model. We present an MCMC algorithm to accelerate the coarsest level sampling using MLM and account for the approximation error introduced. We provide theoretical proofs of detailed balance and demonstrate that our multilevel approach constitutes a consistent MCMC algorithm. Additionally, we derive the expression for cost reduction due to machine learning model to facilitate cost analysis of the hierarchical sampling algorithm. Our technique is demonstrated on a standard benchmark inference problem in groundwater flow, where we estimate the probability density of a quantity of interest using a four-level MCMC algorithm. Our proposed algorithm accelerates multilevel sampling by a factor of two while achieving similar accuracy compared to sampling using the standard multilevel algorithm.

97 MATHEMATICS AND COMPUTING↗

A Local Macroscopic Conservative (LoMaC) Low Rank Tensor Method for the Vlasov Dynamics

Abstract In this paper, we propose a novel Local Macroscopic Conservative (LoMaC) low rank tensor method for simulating the Vlasov-Poisson (VP) system. The LoMaC property refers to the exact local conservation of macroscopic mass, momentum and energy at the discrete level. This is a follow-up work of our previous development of a conservative low rank tensor approach for Vlasov dynamics ( arXiv:2201.10397 ). In that work, we applied a low rank tensor method with a conservative singular value decomposition to the high dimensional VP system to mitigate the curse of dimensionality, while maintaining the local conservation of mass and momentum. However, energy conservation is not guaranteed, which is a critical property to avoid unphysical plasma self-heating or cooling. The new ingredient in the LoMaC low rank tensor algorithm is that we simultaneously evolve the macroscopic conservation laws of mass, momentum and energy using a flux-difference form with kinetic flux vector splitting; then the LoMaC property is realized by projecting the low rank kinetic solution onto a subspace that shares the same macroscopic observables by a conservative orthogonal projection. The algorithm is extended to the high dimensional problems by hierarchical Tuck decomposition of solution tensors and a corresponding conservative projection algorithm. Extensive numerical tests on the VP system are showcased for the algorithm’s efficacy.

Guo, Wei↗

A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices

Summary In this article, we introduce a fast, memory efficient and robust sparse preconditioner that is based on a direct factorization scheme for sparse matrices arising from the finite‐element discretization of elliptic partial differential equations. We use a fast (but approximate) multifrontal approach as a preconditioner and use an iterative scheme to achieve a desired accuracy. This approach combines the advantages of direct and iterative schemes to arrive at a fast, robust, and accurate preconditioner. We will show that this approach is faster (∼2×) and more memory efficient (∼2–3×) than a conventional direct multifrontal approach. Furthermore, we will demonstrate that this preconditioner is both faster and more effective than other preconditioners such as the incomplete LU preconditioner. Specific speedups depend on the matrix size and improve as the size of the matrix increases. The preconditioner can be applied to both structured and unstructured meshes in a similar manner. We build on our previous work and utilize the fact that dense frontal and update matrices, in the multifrontal algorithm, can be represented as hierarchically off‐diagonal low‐rank matrices. Using this idea, we replace all large dense matrix operations in the multifrontal elimination process with O ( N ) hierarchically off‐diagonal low‐rank operations to arrive at a faster and more memory efficient factorization scheme. We then use this direct factorization method at low accuracies as a preconditioner and apply it to various real‐life engineering test cases. Copyright © 2016 John Wiley & Sons, Ltd.

Aminfar, AmirHossein↗

A New Global River Network Database for Macroscale Hydrologic modeling

Coarse resolution (upscaled) river networks are critical inputs for runoff routing in macroscale hydrologic models. Recently, Wu et al. (2011) developed a hierarchical Dominant River Tracing (DRT) algorithm for automated extraction and spatial upscaling of basin flow directions and river networks using fine-scale hydrography inputs (e.g., flow direction, river networks, and flow accumulation). The DRT was initially applied using HYDRO1K baseline fine-scale hydrography inputs and the resulting upscaled global hydrography maps were produced at several spatial scales, and verified against other available regional and global datasets. New baseline fine-scale hydrography data from HydroSHEDS are now available for many regions and provide superior scale and quality relative to HYDRO1K. However, HydroSHEDS does not cover regions above 60°N. In this study, we applied the DRT algorithms using combined HydroSHEDS and HYDRO1K global fine-scale hydrography inputs, and produced a new series of upscaled global river network data at multiple (1/16° to 2°) spatial resolutions in a consistent (WGS84) projection. The new upscaled river networks are internally consistent and congruent with the baseline fine-scale inputs. The DRT results preserve baseline fine-scale river networks independent of spatial scales, with consistency in river network, basin shape, basin area, river length, and basin internal drainage structure between upscaled and baseline fine-scale hydrography. These digital data are available online for public access (ftp://ftp.ntsg.umt.edu/pub/data/DRT/) and should facilitate improved regional to global scale hydrological simulations, including runoff routing and river discharge calculations.

macroscale hydrological modeling↗

Work Stealing and Persistence-based Load Balancers for Iterative Overdecomposed Applications

Applications often involve iterative execution of identical or slowly evolving calculations. Such applications require good initial load balance coupled with efficient periodic rebalancing. In this paper, we consider the design and evaluation of two distinct approaches to addressing this challenge: persistence-based load balancing and work stealing. The work to be performed is overdecomposed into tasks, enabling automatic rebalancing by the middleware. We present a hierarchical persistence-based rebalancing algorithm that performs localized incremental rebalancing. We also present an active-message-based retentive work stealing algorithm optimized for iterative applications on distributed memory machines. These are shown to incur low overheads and achieve over 90% efficiency on 76,800 cores.

persistence-based load balancing↗