Search NASA⌕ Search

SEARCH · Search NASA

Results for “error bound”

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 91 records · Page 5

Verifying the error bound of numerical computation implemented in computer systems

A verification tool receives a finite precision definition for an approximation of an infinite precision numerical function implemented in a processor in the form of a polynomial of bounded functions. The verification tool receives a domain for verifying outputs of segments associated with the infinite precision numerical function. The verification tool splits the domain into at least two segments, wherein each segment is non-overlapping with any other segment and converts, for each segment, a polynomial of bounded functions for the segment to a simplified formula comprising a polynomial, an inequality, and a constant for a selected segment. The verification tool calculates upper bounds of the polynomial for the at least two segments, beginning with the selected segment and reports the segments that violate a bounding condition.

97 MATHEMATICS AND COMPUTING↗

High gain feedback and telerobotic tracking

Asymptotically stable linear time invariant systems are capable of tracking arbitrary reference signals with a bounded error proportional to the magnitude of the reference signal (and its derivatives). It is shown that a similar property holds for a general class of nonlinear dynamical systems which includes all robots. As in the linear case, the error bound may be made arbitrarily small by increasing the magnitude of the feedback gains which stabilize the system.

Koditschek, D. E.↗

Error-Rate Bounds for Coded PPM on a Poisson Channel

Equations for computing tight bounds on error rates for coded pulse-position modulation (PPM) on a Poisson channel at high signal-to-noise ratio have been derived. These equations and elements of the underlying theory are expected to be especially useful in designing codes for PPM optical communication systems. The equations and the underlying theory apply, more specifically, to a case in which a) At the transmitter, a linear outer code is concatenated with an inner code that includes an accumulator and a bit-to-PPM-symbol mapping (see figure) [this concatenation is known in the art as "accumulate-PPM" (abbreviated "APPM")]; b) The transmitted signal propagates on a memoryless binary-input Poisson channel; and c) At the receiver, near-maximum-likelihood (ML) decoding is effected through an iterative process. Such a coding/modulation/decoding scheme is a variation on the concept of turbo codes, which have complex structures, such that an exact analytical expression for the performance of a particular code is intractable. However, techniques for accurately estimating the performances of turbo codes have been developed. The performance of a typical turbo code includes (1) a "waterfall" region consisting of a steep decrease of error rate with increasing signal-to-noise ratio (SNR) at low to moderate SNR, and (2) an "error floor" region with a less steep decrease of error rate with increasing SNR at moderate to high SNR. The techniques used heretofore for estimating performance in the waterfall region have differed from those used for estimating performance in the error-floor region. For coded PPM, prior to the present derivations, equations for accurate prediction of the performance of coded PPM at high SNR did not exist, so that it was necessary to resort to time-consuming simulations in order to make such predictions. The present derivation makes it unnecessary to perform such time-consuming simulations.

Moision, Bruce↗

Numerical Homogenization on Approach for Stokesian Suspensions

In this technical report we investigate efficient methods for numerical simulation of active suspensions. The prototypical system is a suspension of swimming bacteria in a Newtonian fluid. Rheological and other macroscopic properties of such suspensions can differ dramatically from the same properties of the suspending fluid alone or of suspensions of similar but inactive particles. Elongated bacteria, such as E. coli or B. subtilis, swim along their principal axis, propelling themselves with the help of flagella, attached at the anterior of the organism and pushing it forward in the manner of a propeller. They interact hydrodynamically with the surrounding fluid and, because of their asymmetrical shape, have the propensity to align with the local flow. This, along with the dipolar nature of bacteria (the two forces a bacterium exerts on a fluid - one due to self-propulsion and the other opposing drag - have equal magnitude and point in opposite directions), causes nearby bacteria to tend to align, resulting in a intermittent local ordering on the mesoscopic scale, which is between the microscopic scale of an individual bacterium and the macroscopic scale of the suspension (e.g., its container). The local ordering is sometimes called a collective mode or collective swimming. Thanks to self-propulsion, collective modes inject momentum into the fluid in a coherent way. This enhances the local strain rate without changing the macroscopic stress applied at the boundary of the container. The macroscopic effective viscosity of the suspension is defined roughly as the ratio of the applied stress to the bulk strain rate. If local alignment and therefore local strain-rate enhancement, are significant, the effective viscosity can be appreciably lower than that of the corresponding passive suspension or even of the surrounding fluid alone. Indeed, a sevenfold decrease in the effective viscosity was observed in experiments with B. subtilis. More generally, local collective swimming resulting from bacterial alignment can significantly alter other macroscopic properties of the suspension, such as the oxygen diffusivity and mixing rates. In order to understand the unique macroscopic properties of active suspensions the connection between microscopic swimming and alignment dynamics and the mesoscopic pattern formation must be clarified. This is difficult to do analytically in the fully general setting of moderately dense suspensions, because of the large number of bacteria involved (approx. 10 10 cm -3 in experiments) and the complex, time-dependent geometry of the system. Many reduced analytical models of bacterial have been proposed, but all of them require validation. While comparison with experiment is the ultimate test of a model's fidelity, it is difficult to conduct experiments matched to these models assumptions. Numerical simulation of the microscopic dynamics is an acceptable substitute, but it runs into the problem of having to discretize the fluid domain with a fine-grained boundary (the bacteria) and update the discretization as the domain evolves (bacteria move). This leads to a prohibitively high number of degrees of freedom and prohibitively high setup costs per timestep of simulation. In this technical report we propose numerical methods designed to alleviate these two difficulties. We indicate how to (1) construct an optimal discretization in terms of the number of degrees of freedom per digit of accuracy and (2) optimally update the discretization as the simulation evolves. The technical tool here is the derivation of rigorous error bounds on the error in the numerical solution when using our proposed discretization at the initial time as well as after a given elapsed simulation time. These error bounds should guide the construction of practical discretization schemes and update strategies. Our initial construction is carried out by using a theoretically convenient, but practically prohibitive spectral basis, which is a Galerkin basis of functions with global support. At the end of this report we propose localization techniques while maintaining acceptable error bounds. No numerical experiments were conducted as part of this study, but we envision that we may undertake such studies and further development of the method, jointly or individually.

60 APPLIED LIFE SCIENCES↗

Optimising the processing and storage of visibilities using lossy compression

The next-generation radio astronomy instruments are providing a massive increase in sensitivity and coverage, largely through increasing the number of stations in the array and the frequency span sampled. The two primary problems encountered when processing the resultant avalanche of data are the need for abundant storage and the constraints imposed by I/O, as I/O bandwidths drop significantly on cold storage. An example of this is the data deluge expected from the SKA Telescopes of more than 60 PB per day, all to be stored on the buffer filesystem. While compressing the data is an obvious solution, the impacts on the final data products are hard to predict. In this paper, we chose an error-controlled compressor – MGARD – and applied it to simulated SKA-Mid and real pathfinder visibility data, in noise-free and noise-dominated regimes. As the data have an implicit error level in the system temperature, using an error bound in compression provides a natural metric for compression. MGARD ensures the compression incurred errors adhere to the user-prescribed tolerance. To measure the degradation of images reconstructed using the lossy compressed data, we proposed a list of diagnostic measures, exploring the trade-off between these error bounds and the corresponding compression ratios, as well as the impact on science quality derived from the lossy compressed data products through a series of experiments. We studied the global and local impacts on the output images for continuum and spectral line examples. We found relative error bounds of as much as 10%, which provide compression ratios of about 20, have a limited impact on the continuum imaging as the increased noise is less than the image RMS, whereas a 1% error bound (compression ratio of 8) introduces an increase in noise of about an order of magnitude less than the image RMS. For extremely sensitive observations and for very precious data, we would recommend a 0.1% error bound with compression ratios of about 4. These have noise impacts two orders of magnitude less than the image RMS levels. At these levels, the limits are due to instabilities in the deconvolution methods. We compared the results to the alternative compression tool DYSCO, in both the impacts on the images and in the relative flexibility. MGARD provides better compression for similar error bounds and has a host of potentially powerful additional features.

Techniques: interferometric↗

Upper bounds to error probabilities of coded systems beyond the cutoff rate

A family of upper bounds to error probabilities of coded systems was recently proposed by Divsalar. These bounds are valid for transmission over the additive white Gaussian noise channel, and require only the knowledge of the weight spectrum of the code words. After illustrating these bounds, we extend them to fading channels. Contrary to the union bound, our bounds maintain their effectiveness below the signal-to-noise ratio (SNR)at which the cutoff rate of the channel equals the rate of the code. Some applications are shown. First, we derive upper bounds to the minimum SNR necessary to achieve zero error probability as the code block length increases to infinity. Next, we use our bounds to predict the performance of turbo codes and low-density parity-check codes.

Biglieri, Ezio↗

Region-adaptive, Error-controlled Scientific Data Compression using Multilevel Decomposition

The increase of computer processing speed is significantly outpacing improvements in network and storage bandwidth, leading to the big data challenge in modern science, where scientific applications can quickly generate much more data than that can be transferred and stored. As a result, big scientific data must be reduced by a few orders of magnitude while the accuracy of the reduced data needs to be guaranteed for further scientific explorations. Moreover, scientists are often interested in some specific spatial/temporal regions in their data, where higher accuracy is required. The locations of the regions requiring high accuracy can sometimes be prescribed based on application knowledge, while other times they must be estimated based on general spatial/temporal variation. In this paper, we develop a novel multilevel approach which allows users to impose region-wise compression error bounds. Our method utilizes the byproduct of a multilevel compressor to detect regions where details are rich and we provide the theoretical underpinning for region-wise error control. With spatially varying precision preservation, our approach can achieve significantly higher compression ratios than single-error bounded compression approaches and control errors in the regions of interest.We conduct the evaluations on two climate use cases – one targeting small-scale, node features and the other focusing on long, areal features. For both use cases, the locations of the features were unknown ahead of the compression. By selecting approximately 16% of the data based on multi-scale spatial variations and compressing those regions with smaller error tolerances than the rest, our approach improves the accuracy of post-analysis by approximately 2 × compared to single-error-bounded compression at the same compression ratio. Using the same error bound for the region of interest, our approach can achieve an increase of more than 50% in overall compression ratio.

Gong, Qian↗

Gleipnir: toward practical error analysis for Quantum programs

Practical error analysis is essential for the design, optimization, and evaluation of Noisy Intermediate-Scale Quantum(NISQ) computing. However, bounding errors in quantum programs is a grand challenge, because the effects of quantum errors depend on exponentially large quantum states. In this work, we present Gleipnir, a novel methodology toward practically computing verified error bounds in quantum programs. Gleipnir introduces the (ρ,δ)-diamond norm, an error metric constrained by a quantum predicate consisting of the approximate state ρ and its distance δ to the ideal state ρ. This predicate (ρ,δ) can be computed adaptively using tensor networks based on the Matrix Product States. Gleipnir features a lightweight logic for reasoning about error bounds in noisy quantum programs, based on the (ρ,δ)-diamond norm metric. Furthermore, our experimental results show that Gleipnir is able to efficiently generate tight error bounds for real-world quantum programs with 10 to 100 qubits, and can be used to evaluate the error mitigation performance of quantum compiler transformations.

Tao, Runzhou↗

Notions of analytic vs numerical stability as applied to the numerical calculation of orbits

This paper deals with the implications of 'stability' as applied to the numerical calculation of orbits. The study was motivated by the recent appearance of several proposed transformations of the classical Newtonian equations of motion which 'analytically stabilize' Cowell's method. This report analyzes the basic properties of such stabilizing transformations and shows the removal of the period as a parameter is the key to these transformations and, that although such transformations do not yield global numerical error bounds, the error propagation properties are more favorable - linear vs quadratic growth.

Velez, C. E.↗

Analysis of subpixel registration

The area of subpixel accuracy in image registration and edge detection was studied. Two main directions of research were pursued, edge detection and matching based on the digital geometry of edges, and random field models for probablistic analysis of registration error. In the edge detection approach, error bounds and error probabilities were computed using theoretical models. Algorithms were developed and tests on simulated imagery. The methods appear promising for high accuracy edge position estimation and registration, though further refinement of the procedures is required. Using random field models, a statistical measure of the quality of the cross correlation peak as an estimate of the offset between a sensed and a reference image was developed. Simulations were performed to determine the validity of this estimte with real imagery and to study the results of interpolating digital correlation functions to estimate the translation offset to subpixel accuracy.

Berenstein, C. A.↗

Upper bounds to error probabilities of coded systems over AWGN and fading channels

A family of upper bounds to error probabilities of coded systems on the additive white Gaussian noise channel was recently proposed by Divsalar. Their calculation depends only on the weight spectrum of the code words. We first elaborate upon these bounds to show how they can be further tightened by using numerical integration instead of a Chernoff bound, and by reducing the number of code words to be included in the bound. Next, we extend them to finding channels.

coded systems↗

The Aharonov-Bohm effect and Tonomura et al. experiments: Rigorous results

The Aharonov-Bohm effect is a fundamental issue in physics. It describes the physically important electromagnetic quantities in quantum mechanics. Its experimental verification constitutes a test of the theory of quantum mechanics itself. The remarkable experiments of Tonomura et al. ['Observation of Aharonov-Bohm effect by electron holography', Phys. Rev. Lett 48, 1443 (1982) and 'Evidence for Aharonov-Bohm effect with magnetic field completely shielded from electron wave', Phys. Rev. Lett 56, 792 (1986)] are widely considered as the only experimental evidence of the physical existence of the Aharonov-Bohm effect. Here we give the first rigorous proof that the classical ansatz of Aharonov and Bohm of 1959 ['Significance of electromagnetic potentials in the quantum theory', Phys. Rev. 115, 485 (1959)], that was tested by Tonomura et al., is a good approximation to the exact solution to the Schroedinger equation. This also proves that the electron, that is, represented by the exact solution, is not accelerated, in agreement with the recent experiment of Caprez et al. in 2007 ['Macroscopic test of the Aharonov-Bohm effect', Phys. Rev. Lett. 99, 210401 (2007)], that shows that the results of the Tonomura et al. experiments can not be explained by the action of a force. Under the assumption that the incoming free electron is a Gaussian wave packet, we estimate the exact solution to the Schroedinger equation for all times. We provide a rigorous, quantitative error bound for the difference in norm between the exact solution and the Aharonov-Bohm Ansatz. Our bound is uniform in time. We also prove that on the Gaussian asymptotic state the scattering operator is given by a constant phase shift, up to a quantitative error bound that we provide. Our results show that for intermediate size electron wave packets, smaller than the ones used in the Tonomura et al. experiments, quantum mechanics predicts the results observed by Tonomura et al. with an error bound smaller than 10{sup -99}. It would be quite interesting to perform experiments with electron wave packets of intermediate size. Furthermore, we provide a physical interpretation of our error bound.

97 MATHEMATICS AND COMPUTING↗