Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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 721 records · Page 40

Blazing Signature Filter: a library for fast pairwise similarity comparisons

Identifying similarities between datasets is a fundamental task in data mining and has become an integral part of modern scientific investigation. Whether the task is to identify co-expressed genes in large-scale expression surveys or to predict combinations of gene knockouts which would elicit a similar phenotype, the underlying computational task is often a multi-dimensional similarity test. As datasets continue to grow, improvements to the efficiency, sensitivity or specificity of such computation will have broad impacts as it allows scientists to more completely explore the wealth of scientific data. A significant practical drawback of large-scale data mining is the vast majority of pairwise comparisons are unlikely to be relevant, meaning that they do not share a signature of interest. It is therefore essential to efficiently identify these unproductive comparisons as rapidly as possible and exclude them from more time-intensive similarity calculations. The Blazing Signature Filter (BSF) is a highly efficient pairwise similarity algorithm which enables extensive data mining within a reasonable amount of time. The algorithm transforms datasets into binary metrics, allowing it to utilize the computationally efficient bit operators and provide a coarse measure of similarity. As a result, the BSF can scale to high dimensionality and rapidly filter unproductive pairwise comparison. Furthermore, two bioinformatics applications of the tool are presented to demonstrate the ability to scale to billions of pairwise comparisons and the usefulness of this approach.

59 BASIC BIOLOGICAL SCIENCES↗

A robust and efficient stepwise regression method for building sparse polynomial chaos expansions

Polynomial Chaos (PC) expansions are widely used in various engineering fields for quantifying uncertainties arising from uncertain parameters. The computational cost of classical PC solution schemes is unaffordable as the number of deterministic simulations to be calculated grows dramatically with the number of stochastic dimension. This considerably restricts the practical use of PC at the industrial level. A common approach to address such problems is to make use of sparse PC expansions. This paper presents a non-intrusive regression-based method for building sparse PC expansions. The most important PC contributions are detected sequentially through an automatic search procedure. The variable selection criterion is based on efficient tools relevant to probabilistic method. Two benchmark analytical functions are used to validate the proposed algorithm. The computational efficiency of the method is then illustrated by a more realistic CFD application, consisting of the non-deterministic flow around a transonic airfoil subject to geometrical uncertainties. To assess the performance of the developed methodology, a detailed comparison is made with the well established LAR-based selection technique. The results show that the developed sparse regression technique is able to identify the most significant PC contributions describing the problem. Moreover, the most important stochastic features are captured at a reduced computational cost compared to the LAR method. The results also demonstrate the superior robustness of the method by repeating the analyses using random experimental designs.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Performance of the rigorous renormalization group for first-order phase transitions and topological phases

Expanding and improving the repertoire of numerical methods for studying quantum lattice models is an ongoing focus in many-body physics. While the density matrix renormalization group (DMRG) has been established as a practically useful algorithm for finding the ground state in one-dimensional systems, a provably efficient and accurate algorithm remained elusive until the introduction of the rigorous renormalization group (RRG) by Landau [Nat. Phys. 11, 566 (2015)1745-247310.1038/nphys3345]. In this paper, we study the accuracy and performance of a numerical implementation of RRG at first-order phase transitions and in symmetry-protected topological phases. Our study is motivated by the question of when RRG might provide a useful complement to the more established DMRG technique. In particular, despite its general utility, DMRG can give unreliable results near first-order phase transitions and in topological phases, since its local update procedure can fail to adequately explore (near-)degenerate manifolds. Furthermore, the rigorous theoretical underpinnings of RRG, meanwhile, suggest that it should not suffer from the same difficulties. We show this optimism is justified, and that RRG indeed determines well-ordered, accurate energies even when DMRG does not. Moreover, our performance analysis indicates that in certain circumstances seeding DMRG with states determined by coarse runs of RRG may provide an advantage over simply performing DMRG.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

The FADE mass-stat: A technique for inserting or deleting particles in molecular dynamics simulations

The emergence of new applications of molecular dynamics (MD) simulation calls for the development of mass-statting procedures that insert or delete particles on-the-fly. In this paper we present a new mass-stat which we term FADE, because it gradually “fades-in” (inserts) or “fades-out” (deletes) molecules over a short relaxation period within a MD simulation. FADE applies a time-weighted relaxation to the intermolecular pair forces between the inserting/deleting molecule and any neighbouring molecules. The weighting function we propose in this paper is a piece-wise polynomial that can be described entirely by two parameters: the relaxation time scale and the order of the polynomial. FADE inherently conserves overall system momentum independent of the form of the weighting function. We demonstrate various simulations of insertions of atomic argon, polyatomic TIP4P water, polymer strands, and C{sub 60} Buckminsterfullerene molecules. We propose FADE parameters and a maximum density variation per insertion-instance that restricts spurious potential energy changes entering the system within desired tolerances. We also demonstrate in this paper that FADE compares very well to an existing insertion algorithm called USHER, in terms of accuracy, insertion rate (in dense fluids), and computational efficiency. The USHER algorithm is applicable to monatomic and water molecules only, but we demonstrate that FADE can be generally applied to various forms and sizes of molecules, such as polymeric molecules of long aspect ratio, and spherical carbon fullerenes with hollow interiors.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

An h-adaptive mesh method for Boltzmann-BGK/hydrodynamics coupling

We introduce a coupled method for hydrodynamic and kinetic equations on 2-dimensional h-adaptive meshes. We adopt the Euler equations with a fast kinetic solver in the region near thermodynamical equilibrium, while use the Boltzmann-BGK equation in kinetic regions where fluids are far from equilibrium. A buffer zone is created around the kinetic regions, on which a gradually varying numerical flux is adopted. Based on the property of a continuously discretized cut-off function which describes how the flux varies, the coupling will be conservative. In order for the conservative 2-dimensional specularly reflective boundary condition to be implemented conveniently, the discrete Maxwellian is approximated by a high order continuous formula with improved accuracy on a disc instead of on a square domain. The h-adaptive method can work smoothly with a time-split numerical scheme. Through h-adaptation, the cell number is greatly reduced. This method is particularly suitable for problems with hydrodynamics breakdown on only a small part of the whole domain, so that the total efficiency of the algorithm can be greatly improved. Three numerical examples are presented to validate the proposed method and demonstrate its efficiency.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Comparison of Planning Quality and Efficiency Between Conventional and Knowledge-based Algorithms in Nasopharyngeal Cancer Patients Using Intensity Modulated Radiation Therapy

Purpose: Intensity modulated radiation therapy (IMRT) is widely used to achieve a highly conformal dose and improve treatment outcome. However, plan quality and planning time are institute and planner dependent, and no standardized tool exists to recognize an optimal plan. RapidPlan, a knowledge-based algorithm, can generate constraints to assist optimization and produce high-quality IMRT plans. This report evaluated the quality and efficiency of using RapidPlan in nasopharyngeal carcinoma (NPC) IMRT planning. Methods and Materials: RapidPlan was configured using 79 radical IMRT plans for NPC; 20 consecutive NPC patients indicated for radical radiation therapy between October 2014 and May 2015 were then recruited to assess its performance. The ability of RapidPlan to produce acceptable plans was evaluated. For plans that could not achieve clinical acceptance, manual touch-up was performed. The IMRT plans produced without RapidPlan (manual plans) and with RapidPlan (RP-2 plans, including those with manual touch-up) were compared in terms of dosimetric quality and planning efficiency. Results: RapidPlan by itself could produce clinically acceptable plans for 9 of the 20 patients; manual touch-up increased the number of acceptable plans (RP-2 plans) to 19. The target dose coverage and conformity were very similar. No difference was found in the maximum dose to the brainstem and optic chiasm. RP-2 plans delivered a higher maximum dose to the spinal cord (46.4 Gy vs 43.9 Gy, P=.002) but a lower dose to the parotid (mean dose to right parotid, 37.3 Gy vs 45.4 Gy; left, 34.4 Gy vs 43.1 Gy; P<.001) and the right cochlea (mean dose, 48.6 Gy vs 52.6 Gy; P=.02). The total planning time for RP-2 plans was significantly less than that for manual plans (64 minutes vs 295 minutes, P<.001). Conclusions: This study shows that RapidPlan can significantly improve planning efficiency and produce quality IMRT plans for NPC patients.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

DyG-DPCD: A Distributed Parallel Community Detection Algorithm for Large-Scale Dynamic Graphs

Dynamic (Temporal) graphs capture the valuable evolution of real-world systems, from the continuously evolving patterns of social interactions and genetic pathways to the dynamic fluctuations of economic forces. Detecting communities for such evolving networks poses unique challenges. Detecting and analyzing the evolution of communities within dynamic graphs unlocks valuable insights into the underlying structural and temporal patterns of real-world systems. However, the sheer volume of modern graph data and the inherent complexity of the temporal dimension pose significant challenges to scalable community detection algorithms. Addressing this gap, our work explores the limited landscape of scalable distributed-memory parallel methods specifically designed for dynamic network community detection. We propose a novel parallel algorithm, DyG-DPCD (Dynamic Graph Distributed Parallel Community Detection), to detect communities in dynamic networks using the Message Passing Interface (MPI) framework. We present a vertex-centric approach, allowing us to detect communities through local optimization. Furthermore, we enhance our baseline algorithm by incorporating three heuristics, which improve the algorithm’s performance significantly while maintaining the quality of the solutions. We demonstrate the efficiency of our algorithm by experimenting on several real-world large-scale networks with hundreds of millions of edges spanning diverse domains. Notably, DyG-DPCD achieves speedups between 25× and 30× for large networks that we experimented on using NERSC compute nodes. In conclusion, our algorithm outperforms the STINGER parallel re-agglomeration algorithm by 30×.

97 MATHEMATICS AND COMPUTING↗

Two-Level Least Squares Methods in Krylov Subspaces

Two-level least squares acceleration approaches are applied to the Chebyshev acceleration method and the restarted conjugate residual method in solving systems of linear algebraic equations with sparse unsymmetric coefficient matrices arising from finite volume or finite element approximations of boundary-value problems on irregular grids. Application of the proposed idea to other iterative restarted processes also is considered. The efficiency of the algorithms suggested is investigated numerically on a set of model Dirichlet problems for the convection-diffusion equation.

97 MATHEMATICS AND COMPUTING↗

PERIOD ERROR ESTIMATION FOR THE KEPLER ECLIPSING BINARY CATALOG

The Kepler Eclipsing Binary Catalog (KEBC) describes 2165 eclipsing binaries identified in the 115 deg{sup 2} Kepler Field based on observations from Kepler quarters Q0, Q1, and Q2. The periods in the KEBC are given in units of days out to six decimal places but no period errors are provided. We present the PEC (Period Error Calculator) algorithm, which can be used to estimate the period errors of strictly periodic variables observed by the Kepler Mission. The PEC algorithm is based on propagation of error theory and assumes that observation of every light curve peak/minimum in a long time-series observation can be unambiguously identified. The PEC algorithm can be efficiently programmed using just a few lines of C computer language code. The PEC algorithm was used to develop a simple model that provides period error estimates for eclipsing binaries in the KEBC with periods less than 62.5 days: log {sigma}{sub P} Almost-Equal-To - 5.8908 + 1.4425(1 + log P), where P is the period of an eclipsing binary in the KEBC in units of days. KEBC systems with periods {>=}62.5 days have KEBC period errors of {approx}0.0144 days. Periods and period errors of seven eclipsing binary systems in the KEBC were measured using the NASA Exoplanet Archive Periodogram Service and compared to period errors estimated using the PEC algorithm.

79 ASTRONOMY AND ASTROPHYSICS↗

Quantifying the magic of quantum channels

Abstract To achieve universal quantum computation via general fault-tolerant schemes, stabilizer operations must be supplemented with other non-stabilizer quantum resources. Motivated by this necessity, we develop a resource theory for magic quantum channels to characterize and quantify the quantum ‘magic’ or non-stabilizerness of noisy quantum circuits. For qudit quantum computing with odd dimension d , it is known that quantum states with non-negative Wigner function can be efficiently simulated classically. First, inspired by this observation, we introduce a resource theory based on completely positive-Wigner-preserving quantum operations as free operations, and we show that they can be efficiently simulated via a classical algorithm. Second, we introduce two efficiently computable magic measures for quantum channels, called the mana and thauma of a quantum channel. As applications, we show that these measures not only provide fundamental limits on the distillable magic of quantum channels, but they also lead to lower bounds for the task of synthesizing non-Clifford gates. Third, we propose a classical algorithm for simulating noisy quantum circuits, whose sample complexity can be quantified by the mana of a quantum channel. We further show that this algorithm can outperform another approach for simulating noisy quantum circuits, based on channel robustness. Finally, we explore the threshold of non-stabilizerness for basic quantum circuits under depolarizing noise.

Wang, Xin (ORCID:0000000206413186)↗

Fast correlation function calculator: A high-performance pair-counting toolkit

A novel high-performance exact pair-counting toolkit called fast correlation function calculator (FCFC) is presented. With the rapid growth of modern cosmological datasets, the evaluation of correlation functions with observational and simulation catalogues has become a challenge. High-efficiency pair-counting codes are thus in great demand. We introduce different data structures and algorithms that can be used for pair-counting problems, and perform comprehensive benchmarks to identify the most efficient algorithms for real-world cosmological applications. We then describe the three levels of parallelisms used by FCFC, SIMD, OpenMP, and MPI, and run extensive tests to investigate the scalabilities. Finally, we compare the efficiency of FCFC with alternative pair-counting codes. The data structures and histogram update algorithms implemented in FCFC are shown to outperform alternative methods. FCFC does not benefit greatly from SIMD because the bottleneck of our histogram update algorithm is mainly cache latency. Nevertheless, the efficiency of FCFC scales well with the numbers of OpenMP threads and MPI processes, even though speedups may be degraded with over a few thousand threads in total. FCFC is found to be faster than most (if not all) other public pair-counting codes for modern cosmological pair-counting applications.

79 ASTRONOMY AND ASTROPHYSICS↗

Real-time signal detection for Cyclotron Radiation Emission Spectroscopy measurements using antenna arrays

Cyclotron Radiation Emission Spectroscopy (CRES) is a technique for precision measurement of the energies of charged particles, which is being developed by the Project 8 Collaboration to measure the neutrino mass using tritium beta-decay spectroscopy. Project 8 seeks to use the CRES technique to measure the neutrino mass with a sensitivity of 40 meV, requiring a large supply of tritium atoms stored in a multi-cubic meter detector volume. Antenna arrays are one potential technology compatible with an experiment of this scale, but the capability of an antenna-based CRES experiment to measure the neutrino mass depends on the efficiency of the signal detection algorithms. Here, in this paper, we develop efficiency models for three signal detection algorithms and compare them using simulations from a prototype antenna-based CRES experiment as a case-study. The algorithms include a power threshold, a matched filter template bank, and a neural network based machine learning approach, which are analyzed in terms of their average detection efficiency and relative computational cost. It is found that significant improvements in detection efficiency and, therefore, neutrino mass sensitivity are achievable, with only a moderate increase in computation cost, by utilizing either the matched filter or machine learning approach in place of a power threshold, which is the baseline signal detection algorithm used in previous CRES experiments by Project 8.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Multiscale/Multiphysics Modeling of Biomass Thermochemical Processes

Computational problems in simulating biomass thermochemical processes involve coupling processes that span several orders of magnitude in space and time. Computational difficulties arise from the multitude of the problem governing equations, each typically applying over a narrow range of spatiotemporal scales, thus making it necessary to represent the processes as the result of the interaction of multiple physics modules, termed here as multiscale/multiphysics (MSMP) coupling. Predictive simulations for such processes require algorithms that can efficiently integrate the underlying MSMP methods across the scales in order to achieve prescribed accuracy and control the computational cost. In addition, MSMP algorithms must scale to one hundred thousand processors or more in order to effectively harness the new computational resources and accelerate the scientific advances. In this chapter, we discuss the state-of-the-art in modeling the macro-scale phenomena in a biomass pyrolysis reactor along with details of the shortcomings and prospects in improving predictability. We also introduce the various multiphysics modules needed to model thermochemical conversion at lower spatiotemporal scales. Furthermore, we illustrate the need for MSMP coupling for thermochemical processes in biomass and provide an overview of the wavelet-based coupling techniques we have developed recently. In particular, we provide details about the compound wavelet matrix (CWM) and the dynamic CWM (dCWM) methods and show they are highly efficient in transferring information among multiphysics models across multiple temporal and spatial scales. The algorithmic gain is in addition to the parallel spatial scalability from traditional domain decomposition methods. The CWM algorithms are serial in time and limited by the smallest-system time-scales. In order to relax this algorithmic constraint, we have recently coupled time parallel (TP) algorithms to CWM, thus yielding a novel approach termed tpCWM. We present preliminary results from the tpCWM technique, indicating that we can accelerate time-to-solution by 2 to 3-orders of magnitude even on 20-processors and this can potentially constitute a new paradigm for MSMP simulations. If such improvements in simulation capability can be generalized, the tpCWM approach can lead the way to predictive simulations of biomass thermochemical processes.

09 BIOMASS FUELS↗

A Model-Free No-arbitrage Price Bound for Variance Options

We suggest a numerical approximation for an optimization problem, motivated by its applications in finance to find the model-free no-arbitrage bound of variance options given the marginal distributions of the underlying asset. A first approximation restricts the computation to a bounded domain. Then we propose a gradient projection algorithm together with the finite difference scheme to solve the optimization problem. We prove the general convergence, and derive some convergence rate estimates. Finally, we give some numerical examples to test the efficiency of the algorithm.

97 MATHEMATICS AND COMPUTING↗

Improving the Numerical Stability of Fast Matrix Multiplication

Fast algorithms for matrix multiplication, namely those that perform asymptotically fewer scalar operations than the classical algorithm, have been considered primarily of theoretical interest. Apart from Strassen's original algorithm, few fast algorithms have been efficiently implemented or used in practical applications. However, there exist many practical alternatives to Strassen's algorithm with varying performance and numerical properties. Fast algorithms are known to be numerically stable, but because their error bounds are slightly weaker than the classical algorithm, they are not used even in cases where they provide a performance benefit. We argue in this study that the numerical sacrifice of fast algorithms, particularly for the typical use cases of practical algorithms, is not prohibitive, and we explore ways to improve the accuracy both theoretically and empirically. The numerical accuracy of fast matrix multiplication depends on properties of the algorithm and of the input matrices, and we consider both contributions independently. We generalize and tighten previous error analyses of fast algorithms and compare their properties. We discuss algorithmic techniques for improving the error guarantees from two perspectives: manipulating the algorithms, and reducing input anomalies by various forms of diagonal scaling. In conclusion, we benchmark performance and demonstrate our improved numerical accuracy.

97 MATHEMATICS AND COMPUTING↗

THE SDSS-III BARYON OSCILLATION SPECTROSCOPIC SURVEY: QUASAR TARGET SELECTION FOR DATA RELEASE NINE

The SDSS-III Baryon Oscillation Spectroscopic Survey (BOSS), a five-year spectroscopic survey of 10,000 deg{sup 2}, achieved first light in late 2009. One of the key goals of BOSS is to measure the signature of baryon acoustic oscillations (BAOs) in the distribution of Ly{alpha} absorption from the spectra of a sample of {approx}150,000 z > 2.2 quasars. Along with measuring the angular diameter distance at z Almost-Equal-To 2.5, BOSS will provide the first direct measurement of the expansion rate of the universe at z > 2. One of the biggest challenges in achieving this goal is an efficient target selection algorithm for quasars in the redshift range 2.2 < z < 3.5, where their colors tend to overlap those of the far more numerous stars. During the first year of the BOSS survey, quasar target selection (QTS) methods were developed and tested to meet the requirement of delivering at least 15 quasars deg{sup -2} in this redshift range, with a goal of 20 out of 40 targets deg{sup -2} allocated to the quasar survey. To achieve these surface densities, the magnitude limit of the quasar targets was set at g {<=} 22.0 or r {<=} 21.85. While detection of the BAO signature in the distribution of Ly{alpha} absorption in quasar spectra does not require a uniform target selection algorithm, many other astrophysical studies do. We have therefore defined a uniformly selected subsample of 20 targets deg{sup -2}, for which the selection efficiency is just over 50% ({approx}10 z > 2.20 quasars deg{sup -2}). This 'CORE' subsample will be fixed for Years Two through Five of the survey. For the remaining 20 targets deg{sup -2}, we will continue to develop improved selection techniques, including the use of additional data sets beyond the Sloan Digital Sky Survey (SDSS) imaging data. In this paper, we describe the evolution and implementation of the BOSS QTS algorithms during the first two years of BOSS operations (through 2011 July), in support of the science investigations based on these data, and we analyze the spectra obtained during the first year. During this year, 11,263 new z > 2.20 quasars were spectroscopically confirmed by BOSS, roughly double the number of previously known quasars with z > 2.20. Our current algorithms select an average of 15 z > 2.20 quasars deg{sup -2} from 40 targets deg{sup -2} using single-epoch SDSS imaging. Multi-epoch optical data and data at other wavelengths can further improve the efficiency and completeness of BOSS QTS.

79 ASTRONOMY AND ASTROPHYSICS↗