Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “lower bounding”

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 145 records · Page 8

Thermal studies of Martian channels and valleys using Termoskan data: New results

The Termoskan instrument onboard the Phobos '88 spacecraft acquired the highest-spatial-resolution thermal data ever obtained for Mars. Included in the thermal images are 2 km/pixel midday observations of several major channel and valley systems, including significant portions of Shalbatana Vallis, Ravi Vallis, Al-Qahira Vallis, Ma'adim Vallis, the channel connecting Valles Marineris with Hydraotes Chaos, and channel material in Eos Chasma. Termoskan also observed small portions of the southern beginnings of Simud, Tiu, and Ares Valles and some channel material in Gangis Chasma. Simultaneous broad band visible data were obtained for all but Ma'adim Vallis. We find that most of the channels and valleys have higher inertias than their surroundings, consistent with Viking IRTM-based thermal studies of Martian channels. We see for the first time that thermal inertia boundaries closely match all flat channel floor boundaries. Combining Termoskan thermal data, relative observations from Termoskan visible channel data, Viking absolute bolometric albedos, and a thermal model of the Mars surface, we have derived lower bounds on channel thermal inertias. Lower bounds on typical channel thermal inertias range from 8.4 to 12.5 (10(exp -3) cal cm(exp -2) s(exp -1/2)K(exp -1)) (352 to 523 in SI units). Lower bounds on inertia differences with the surrounding heavily cratered plains range from 1.1 to 3.5 (46 to 147 in SI units). Atmospheric and geometric effects are not sufficient to cause the inertia enhancements. We agree with previous researchers that localized, dark, high inertia areas within channels are likely eolian in nature. However, the Temloskan data show that eolian deposits do not fill the channels, nor are they responsible for the overall thermal inertia enhancement. Thermal homogeneity and strong correlation of thermal boundaries with the channel floor boundaries lead us to favor noneolian overall explanations.

Betts, B. H.↗

Quantum Time-Space Tradeoffs for Matrix Problems

We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices 𝐴, including the discrete Fourier transform matrix, we prove that quantum circuits with at most 𝑇 input queries and 𝑆 qubits of memory require 𝑇 = Ω⁢(𝑛 2 /𝑆) to compute matrix-vector product 𝐴⁢𝑥 for 𝑥 ∈{0,1 𝑛 . We similarly prove that matrix multiplication for 𝑛 ×𝑛 binary matrices requires 𝑇 = Ω⁢(𝑛 3 /$\sqrt{𝑆}$). Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for 𝑛 × 𝑛 Boolean matrix multiplication to 𝑇 = Ω⁢(𝑛 2.5 /𝑆 1/4 ) from 𝑇 = Ω⁢(𝑛 2.5 /𝑆 1/2 ). Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.

lower bounds↗

DEGAS: Dynamic Exascale Global Address Space Programming Environments

The Dynamic, Exascale Global Address Space programming environment (DEGAS) project will develop the next generation of programming models and runtime systems to meet the challenges of Exascale computing. The Berkeley part of the project concentrated on communication-optimal code generation to optimize speed and energy efficiency by reducing data movement. Our work developed communication lower bounds, and/or communication avoiding algorithms (that either meet the lower bound, or do much less communication than their conventional counterparts) for a variety of algorithms, including linear algebra, machine learning and genomics. The Berkeley part of the project concentrated on communication-optimal code generation to optimize speed and energy efficiency by reducing data movement. Our work developed communication lower bounds, and/or communication avoiding algorithms (that either meet the lower bound, or do much less communication than their conventional counterparts) for a variety of algorithms, including linear algebra, machine learning and genomics.

97 MATHEMATICS AND COMPUTING↗

The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian

We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical circuits; it uses clique embeddings to produce lower bounds on lambda(sub 2) and star embeddings to produce lower bounds on the smallest Rayleigh quotient when there is a zero Dirichlet boundary condition. The method assigns priorities to the paths in the embedding; we show that, for an unweighted tree T, using uniform priorities for a clique embedding produces a lower bound on lambda(sub 2) that is off by at most an 0(log diameter(T)) factor. We show that the best bounds this method can produce for clique embeddings are the same as for a related method that uses clique embeddings and edge lengths to produce bounds.

Guattery, Stephen↗

Software Synthesis for High Productivity Exascale Computing

Over the three years of our project, we accomplished three key milestones: We demonstrated how ideas from generative programming and software synthesis can help support the development of bulk-synchronous distributed memory kernels. These ideas are realized in a new language called MSL, a C-like language that combines synthesis features with high level notations for array manipulation and bulk-synchronous parallelism to simplify the semantic analysis required for synthesis. We also demonstrated that these high level notations map easily to low level C code and show that the performance of this generated code matches that of handwritten Fortran. Second, we introduced the idea of solver-aided domain-specific languages (SDSLs), which are an emerging class of computer-aided programming systems. SDSLs ease the construction of programs by automating tasks such as verification, debugging, synthesis, and non-deterministic execution. SDSLs are implemented by translating the DSL program into logical constraints. Next, we developed a symbolic virtual machine called Rosette, which simplifies the construction of such SDSLs and their compilers. We have used Rosette to build SynthCL, a subset of OpenCL that supports synthesis. Third, we developed novel numeric algorithms that move as little data as possible, either between levels of a memory hierarchy or between parallel processors over a network. We achieved progress in three aspects of this problem. First we determined lower bounds on communication. Second, we compared these lower bounds to widely used versions of these algorithms, and noted that these widely used algorithms usually communicate asymptotically more than is necessary. Third, we identified or invented new algorithms for most linear algebra problems that do attain these lower bounds, and demonstrated large speed-ups in theory and practice.

97 MATHEMATICS AND COMPUTING↗

The price of privately releasing contingency tables, and the spectra of random matrices with correlated rows

Contingency tables are the method of choice of government agencies for releasing statistical summaries of categorical data. In this paper, we consider lower bounds on how much distortion (noise) is necessary in these tables to provide privacy guarantees when the data being summarized is sensitive. We extend a line of recent work on lower bounds on noise for private data analysis [10, 13. 14, 15] to a natural and important class of functionalities. Our investigation also leads to new results on the spectra of random matrices with correlated rows. Consider a database D consisting of n rows (one per individual), each row comprising d binary attributes. For any subset of T attributes of size |T| = k, the marginal table for T has 2{sup k} entries; each entry counts how many times in the database a particular setting of these attributes occurs. Imagine an agency that wishes to release all (d/k) contingency tables for a given database. For constant k, previous work showed that distortion {tilde {Omicron}}(min{l_brace}n, (n{sup 2}d){sup 1/3}, {radical}d{sup k}{r_brace}) is sufficient for satisfying differential privacy, a rigorous definition of privacy that has received extensive recent study. Our main contributions are: (1) For {epsilon}- and ({epsilon}, {delta})-differential privacy (with {epsilon} constant and {delta} = 1/poly(n)), we give a lower bound of {tilde {Omega}}(min{l_brace}{radical}n, {radical}d{sup k}{r_brace}), which is tight for n = {tilde {Omega}}(d{sup k}). Moreover, for a natural and popular class of mechanisms based on additive noise, our bound can be strengthened to {Omega}({radical}d{sup k}), which is tight for all n. Our bounds extend even to non-constant k, losing roughly a factor of {radical}2{sup k} compared to the best known upper bounds for large n. (2) We give efficient polynomial time attacks which allow an adversary to reconstruct sensitive infonnation given insufficiently perturbed contingency table releases. For constant k, we obtain a lower bound of {tilde {Omega}}(min{l_brace}{radical}n, {radical}d{sup k}{r_brace}) that applies to a large class of privacy notions, including K-anonymity (along with its variants) and differential privacy. In contrast to our bounds for differential privacy, this bound (a) is shown only for constant k, but (b) is tight for all values of n when k is constant. (3) Our reconstruction-based attacks require a new lower bound on the least singular values of random matrices with correlated rows. For a constant k, consider a matrix M with (d/k) rows which are formed by taking all possible k-way entry-wise products of an underlying set of d random vectors. We show that even for nearly square matrices with d{sup k}/log d columns, the least singular value is {Omega}({radical}d{sup k}) with high probability - asymptotically, the same bound as one gets for a matrix with independent rows. The proof requires several new ideas for analyzing random matrices and could be of independent interest.

97 MATHEMATICS AND COMPUTING↗

A multitree approach for global solution of ACOPF problems using piecewise outer approximations

Electricity markets rely on the rapid solution of the optimal power flow (OPF) problem to determine generator power levels and set nodal prices. Traditionally, the OPF problem has been formulated using linearized, approximate models, ignoring nonlinear alternating current (AC) physics. These approaches do not guarantee global optimality or even feasibility in the real ACOPF problem. We introduce an outer-approximation approach to solve the ACOPF problem to global optimality based on alternating solution of upper- and lower-bounding problems. The lower-bounding problem is a piecewise relaxation based on strong second-order cone relaxations of the ACOPF, and these piecewise relaxations are selectively refined at each major iteration through increased variable domain partitioning. Our approach is able to efficiently solve all but one of the test cases considered to an optimality gap below 0.1%. This approach opens the door for global solution of MINLP problems with AC power flow equations.

42 ENGINEERING↗

Constraining dark matter late-time energy injection: decays and p-wave annihilations

We use the latest cosmic microwave background (CMB) observations to provide updated constraints on the dark matter lifetime as well as on p-wave suppressed annihilation cross sections in the 1 MeV to 1 TeV mass range. In contrast to scenarios with an s-wave dominated annihilation cross section, which mainly affect the CMB close to the last scattering surface, signatures associated with these scenarios essentially appear at low redshifts (z∼<50) when structure began to form, and thus manifest at lower multipoles in the CMB power spectrum. We use data from Planck, WMAP9, SPT and ACT, as well as Lyman–α measurements of the matter temperature at z ∼ 4 to set a 95% confidence level lower bound on the dark matter lifetime of ∼ 4 × 10{sup 25} s for m{sub χ} = 100 MeV. This bound becomes lower by an order of magnitude at m{sub χ} = 1 TeV due to inefficient energy deposition into the intergalactic medium. We also show that structure formation can enhance the effect of p-wave suppressed annihilation cross sections by many orders of magnitude with respect to the background cosmological rate, although even with this enhancement, CMB constraints are not yet strong enough to reach the thermal relic value of the cross section.

79 ASTRONOMY AND ASTROPHYSICS↗

How Accurately Does the Free Complement Wave Function of a Helium Atom Satisfy the Schroedinger Equation?

The local energy defined by H{psi}/{psi} must be equal to the exact energy E at any coordinate of an atom or molecule, as long as the {psi} under consideration is exact. The discrepancy from E of this quantity is a stringent test of the accuracy of the calculated wave function. The H-square error for a normalized {psi}, defined by {sigma}{sup 2}{identical_to}<{psi}|(H-E){sup 2}|{psi}>, is also a severe test of the accuracy. Using these quantities, we have examined the accuracy of our wave function of a helium atom calculated using the free complement method that was developed to solve the Schroedinger equation. Together with the variational upper bound, the lower bound of the exact energy calculated using a modified Temple's formula ensured the definitely correct value of the helium fixed-nucleus ground state energy to be -2.903 724 377 034 119 598 311 159 245 194 4 a.u., which is correct to 32 digits.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

The effect of bandlimiting of a PCM/NRZ signal on the bit-error probability.

The explicit expressions for the intersymbol interference as a function of bandwidth-bit duration product and bit positions for PCM/NRZ systems operating in the presence of Gaussian noise and in a bandlimited channel are determined. Two types of linear bit detectors are considered, integrate and dump, and bandlimit and sample. Restriction of bandwidth results in a performance degradation. The degradation of signal-to-noise ratio is presented as a function of bandwidth-bit duration product and bit patterns. The average probability of bit errors is computed for various bandwidths. The calculations of the upper bound and lower bound on the error probability are also presented.

Tu, K.↗

Adaptive Fuzzy Control of a Direct Drive Motor: Experimental Aspects

This paper presents a state feedback adaptive control method for position and velocity control of a direct drive motor. The proposed control scheme allows for integrating heuristic knowledge with mathematical knowledge of a system. It performs well even when mathematical model of the system is poorly understood. The controller consists of an adaptive fuzzy controller and a supervisory controller. The supervisory controller requires only knowledge of the upper bound and lower bound of the system parameters. The fuzzy controller is based on fuzzy basis functions and states of the system. The adaptation law is derived based on the Lyapunov function which ensures that the state of the system asymptotically approaches zero. The proposed controller is applied to a direct drive motor with payload and parameter uncertainty, and the effectiveness is experimentally verified. The real-time performance is compared with simulation results.

Medina, E.↗

Adaptive Fuzzy Control of a Direct Drive Motor

This paper presents a state feedback adaptive control method for position and velocity control of a direct drive motor. The proposed control scheme allows for integrating heuristic knowledge with mathematical knowledge of a system. It performs well even when mathematical model of the system is poorly understood. The controller consists of an adaptive fuzzy controller and a supervisory controller. The supervisory controller requires only knowledge of the upper bound and lower bound of the system parameters. The fuzzy controller is based on fuzzy basis functions and states of the system. The adaptation law is derived based on the Lyapunov function which ensures that the state of the system asymptotically approaches zero. The proposed controller is applied to a direct drive motor with payload and parameter uncertainty, and the effectiveness is verified by simulation results.

Medina, E.↗

Model-Independent Characterization of Charge Diffusion in Thick Fully Depleted CCDs

We present a new method to measure charge diffusion in charge-coupled devices (CCDs). The method is based on a statistical characterization of the shapes of charge clouds produced by low-energy X-rays using known properties of the two-dimensional Gaussian point-spread function (PSF). The algorithm produces reliable upper and lower bounds on the size of the PSF for photons converting near the entrance window of a device. It is optimally suited to the case of thick back-illuminated CCDs where the X-ray absorption length is smaller than the silicon thickness and the diffusion scale is of the same order as the pixel size. The only assumptions are that the charge cloud width is a monotonically increasing function of distance from the conversion point to the buried channel, and that the conversion probability is peaked at the surface. Otherwise, no physical models of carrier transport or knowledge of the electric field profile in the CCD are needed. In suboptimal conditions, the upper bound increases and the lower bound is unaffected, so confidence in the correctness of results is retained. The new method has been benchmarked against Monte Carlo simulations and tested on X-ray images measured on thick high-resistivity prototype CCDs for the Large Synoptic Survey Telescope. In Monte Carlo simulations of noiseless images having the optimal diffusion scale, the upper bound approximated the true PSF within 5%, increasing to 10% in simulations with added noise. Even with severely undersampled or truncated PSFs, the method brackets the true value to within 25%. Our method is accurate and computationally efficient and offers a fast and simple experimental setup.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Quantifying Behavior Driven Energy Savings for Hotels

Hotel facilities present abundant opportunities for energy savings. In the United States, there are around 25,000 hotels that spend on an average of $2,196 on energy costs per room each year. This amounts to about 6% of the total annual hotel operating cost. However, unlike offices, there are limited studies on establishing appropriate baselines and quantifying hotel energy savings given the variety of services and amenities, unpredictable customer behaviors, and the around-the-clock operation hours. In this study, we investigate behavior driven energy savings for three medium-size (around 90,000 sf2) hotels that offer similar services in different climate zones. We first used Department of Energy Asset Scoring Tool to establish baseline models. We then conducted energy saving analysis in EnergyPlus based on a behavior model that defines the upper bound and lower bound of customer and hotel staff behavior. Lastly, we presented a probabilistic energy savings outlook for each hotel. The analysis shows behavior driven energy savings up to 25%. We believe this is the first study to incorporate behavioral factors into energy analysis for hotels. It also demonstrates a procedure to quickly create tailored baselines and identify improvement opportunities for hotels.

Dong, Bing↗

A Hybrid Gradient Method to Designing Bayesian Experiments for Implicit Models

Bayesian experimental design (BED) aims at designing an experiment to maximize the information gathering from the collected data. The optimal design is usually achieved by maximizing the mutual information (MI) between the data and the model parameters. When the analytical expression of the MI is unavailable, e.g.,having implicit models with intractable data distributions, a neural network-based lower bound of the MI was recently proposed and a gradient ascent method was used to maximize the lower bound [1]. However, the approach in [1] requires a pathwise sampling path to compute the gradient of the MI lower bound with respect to the design variables, and such a pathwise sampling path is usually inaccessible for implicit models. In this work, we propose a hybrid gradient approach that leverages recent advances in variational MI estimator and evolution strategies (ES)combined with black-box stochastic gradient ascent (SGA) to maximize the MI lower bound. This allows the design process to be achieved through a unified scalable procedure for implicit models without sampling path gradients. Several experiments demonstrate that our approach significantly improves the scalability of BED for implicit models in high-dimensional design space.

Zhang, Jiaxin↗

Testing Classical Properties from Quantum Data

Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of ƒ instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |ƒ⟩ ∝ ∑ x |x, ƒ(x)⟩ or the phase state |(-1) ƒ ⟩ ∝ ∑ x (-1) ƒ(x) |x⟩. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query -based testers in each case. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2 Ω(n) for any tester relying exclusively on Fourier and classical samples. Our passive quantum testers are competitive with classical query -based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2 n/2 ) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.

Boolean Functions↗

Order reduction in linear state estimation under performance constraints

The design and analysis of minimal-order state estimators for possibly time-varying linear systems, under constraints on the maximal allowable mean-square error, are considered. A global lower bound on the optimal error is derived, along with a lower bound on the minimal estimator order, needed for meeting the performance constraint. The ideal reduced-order estimator which satisfies the lower bound is derived, along with conditions for its realizability. When the ideal estimator is not realizable, its structure forms a suboptimal estimator, which maintains, in some sense, a local optimality property and is called the pseudoideal estimator. The mean-square error of the pseudoideal estimator defines upper bounds on the optimal error and on the estimator order needed for meeting the performance constraint. The lower and the upper bounds on the order define a reduced search set for the design problem. When the distance between the ideal and the pseudoideal estimators is sufficiently small in a certain numerical sense, the pseudoideal estimator may be considered optimal for practical purposes.

Baram, Yoram↗