Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “integer”

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

Two Methods for Efficient Solution of the Hitting-Set Problem

A paper addresses much of the same subject matter as that of Fast Algorithms for Model-Based Diagnosis (NPO-30582), which appears elsewhere in this issue of NASA Tech Briefs. However, in the paper, the emphasis is more on the hitting-set problem (also known as the transversal problem), which is well known among experts in combinatorics. The authors primary interest in the hitting-set problem lies in its connection to the diagnosis problem: it is a theorem of model-based diagnosis that in the set-theory representation of the components of a system, the minimal diagnoses of a system are the minimal hitting sets of the system. In the paper, the hitting-set problem (and, hence, the diagnosis problem) is translated from a combinatorial to a computational problem by mapping it onto the Boolean satisfiability and integer- programming problems. The paper goes on to describe developments nearly identical to those summarized in the cited companion NASA Tech Briefs article, including the utilization of Boolean-satisfiability and integer- programming techniques to reduce the computation time and/or memory needed to solve the hitting-set problem.

Vatan, Farrokh↗

Biased Randomized Algorithm for Fast Model-Based Diagnosis

A biased randomized algorithm has been developed to enable the rapid computational solution of a propositional- satisfiability (SAT) problem equivalent to a diagnosis problem. The closest competing methods of automated diagnosis are described in the preceding article "Fast Algorithms for Model-Based Diagnosis" and "Two Methods of Efficient Solution of the Hitting-Set Problem" (NPO-30584), which appears elsewhere in this issue. It is necessary to recapitulate some of the information from the cited articles as a prerequisite to a description of the present method. As used here, "diagnosis" signifies, more precisely, a type of model-based diagnosis in which one explores any logical inconsistencies between the observed and expected behaviors of an engineering system. The function of each component and the interconnections among all the components of the engineering system are represented as a logical system. Hence, the expected behavior of the engineering system is represented as a set of logical consequences. Faulty components lead to inconsistency between the observed and expected behaviors of the system, represented by logical inconsistencies. Diagnosis - the task of finding the faulty components - reduces to finding the components, the abnormalities of which could explain all the logical inconsistencies. One seeks a minimal set of faulty components (denoted a minimal diagnosis), because the trivial solution, in which all components are deemed to be faulty, always explains all inconsistencies. In the methods of the cited articles, the minimal-diagnosis problem is treated as equivalent to a minimal-hitting-set problem, which is translated from a combinatorial to a computational problem by mapping it onto the Boolean-satisfiability and integer-programming problems. The integer-programming approach taken in one of the prior methods is complete (in the sense that it is guaranteed to find a solution if one exists) and slow and yields a lower bound on the size of the minimal diagnosis. In contrast, the present approach is incomplete and fast and yields an upper bound on the size of the minimal diagnosis.

Williams, Colin↗

Improved Compression of Wavelet-Transformed Images

A recently developed data-compression method is an adaptive technique for coding quantized wavelet-transformed data, nominally as part of a complete image-data compressor. Unlike some other approaches, this method admits a simple implementation and does not rely on the use of large code tables. A common data compression approach, particularly for images, is to perform a wavelet transform on the input data, and then losslessly compress a quantized version of the wavelet-transformed data. Under this compression approach, it is common for the quantized data to include long sequences, or runs, of zeros. The new coding method uses prefixfree codes for the nonnegative integers as part of an adaptive algorithm for compressing the quantized wavelet-transformed data by run-length coding. In the form of run-length coding used here, the data sequence to be encoded is parsed into strings consisting of some number (possibly 0) of zeros, followed by a nonzero value. The nonzero value and the length of the run of zeros are encoded. For a data stream that contains a sufficiently high frequency of zeros, this method is known to be more effective than using a single variable length code to encode each symbol. The specific prefix-free codes used are from two classes of variable-length codes: a class known as Golomb codes, and a class known as exponential-Golomb codes. The codes within each class are indexed by a single integer parameter. The present method uses exponential-Golomb codes for the lengths of the runs of zeros, and Golomb codes for the nonzero values. The code parameters within each code class are determined adaptively on the fly as compression proceeds, on the basis of statistics from previously encoded values. In particular, a simple adaptive method has been devised to select the parameter identifying the particular exponential-Golomb code to use. The method tracks the average number of bits used to encode recent runlengths, and takes the difference between this average length and the code parameter. When this difference falls outside a fixed range, the code parameter is updated (increased or decreased). The Golomb code parameter is selected based on the average magnitude of recently encoded nonzero samples. The coding method requires no floating- point operations, and more readily adapts to local statistics than other methods. The method can also accommodate arbitrarily large input values and arbitrarily long runs of zeros. In practice, this means that changes in the dynamic range or size of the input data set would not require a change to the compressor. The algorithm has been tested in computational experiments on test images. A comparison with a previously developed algorithm that uses large code tables (generated via Huffman coding on training data) suggests that the data-compression effectiveness of the present algorithm is comparable to the best performance achievable by the previously developed algorithm.

Kiely, Aaron↗

Partitioning a Gridded Rectangle into Smaller Rectangles

A relatively simple algorithm, devised for use in an image-data-compression application, partitions a rectangular pixelated image (or any other rectangle on which a regular rectangular grid has already been superimposed) into a specified number of smaller rectangles, hereafter denoted segments. The algorithm has the following properties: No floating-point operations are needed. The segments tend to be nearly square (in the sense that their widths and heights in pixel units tend to be nearly equal). The segments tend to have nearly equal areas. The algorithm yields valid results (no zero-width or zero-height segments) as long as the specified number of segments, s, does not exceed the number of pixels (equivalently, the number of grid cells). The inputs to the algorithm are the positive integer s plus the positive integers h and w, denoting the height and width, respectively, of the rectangle in pixel units. The limit on s for a valid result is given by s less than or equal to wh.

Klimesh, Matthew↗

MSTAR: an absolute metrology system with submicrometer accuracy

Laser metrology systems are a key component of stellar interferometers, used to monitor path lengths and dimensions internal to the instrument. Most interferometers use ‘relative’ metrology, in which the integer number of wavelengths along the path is unknown, and the measurement of length is ambiguous. Changes in the path length can be measured relative to an initial calibration point, but interruption of the metrology beam at any time requires a re-calibration of the system. The MSTAR sensor (Modulation Sideband Technology for Absolute Ranging) is a new system for measuring absolute distance, capable of resolving the integer cycle ambiguity of standard interferometers, and making it possible to measure distance with sub-nanometer accuracy. We describe the design of the system, show results for target distances up to 1 meter, and demonstrate how the system can be scaled to kilometer-scale distances. In recent experiments, we have used white light interferometry to augment the ‘truth’ measurements and validate the zero-point of the system. MSTAR is a general-purpose tool for conveniently measuring length with much greater accuracy than was previously possible, and has a wide range of possible applications

Fetterman, Harrold R.↗

MSTAR: an absolute metrology system with submicrometer accuracy

Laser metrology systems are a key component of stellar interferometers, used to monitor path lengths and dimensions internal to the instrument. Most interferometers use ‘relative’ metrology, in which the integer number of wavelengths along the path is unknown, and the measurement of length is ambiguous. Changes in the path length can be measured relative to an initial calibration point, but interruption of the metrology beam at any time requires a re- calibration of the system. iThe MSTAR sensor (Modulation Sideband Technology for Absolute Ranging) is a new system for measuring absolute distance, capable of resolving the integer cycle ambiguity of standard interferometers, and making it possible to measure distance with sub-nanometer accuracy. We describe the design of the system, show results for target distances up to 1 meter, and demonstrate how the system can be scaled to kilometer-scale distances. In recent experiments, we have used white light interferometry to augment the ‘truth’ measurements and validate the zero-point of the system. MSTAR is a general-purpose tool for conveniently measuring length with much greater accuracy than was previously possible, and has a wide range of possible applications.

Lay, Oliver↗

Design considerations and validation of the MSTAR absolute metrology system

Absolute metrology measures the actual distance between two optical fiducials. A number of methods have been employed, including pulsed time-of-flight, intensity-modulated optical beam, and two-color interferometry. The rms accuracy is currently limited to -5 microns. Resolving the integer number of wavelengths requires a 1-sigma range accuracy of -0.1 microns. Closing this gap has a large pay-off the range (length measurement) accuracy can be increased substantially using the unambiguous optical phase. The MSTAR sensor (Modulation Sideband Technology for Absolute Ranging) is a new system for measuring absolute distance, capable of resolving the integer cycle ambiguity of standard interferometers, and making it possible to measure distance with sub-nanometer accuracy. In this paper, we present recent experiments that use dispersed white light interferometry to independently validate the zero-point of the system. We also describe progress towards reducing the size of optics, and stabilizing the laser wavelength for operation over larger target ranges. MSTAR is a general-purpose tool for conveniently measuring length with much greater accuracy than was previously possible, and has a wide range of possible applications.

Jeganathan, Muthu↗

Clockwork Axions in Cosmology. Is Chromonatural Inflation Chrononatural?

Many cosmological models rely on large couplings of axions to gauge fields. Examples include theories of magnetogenesis, inflation on a steep potential, chiral gravitational waves, and chromonatural inflation. Such theories require a mismatch between the axion field range and the mass scale appearing in the aFF~ coupling. This mismatch suggests an underlying monodromy, with the axion winding around its fundamental period a large number of times. We investigate the extent to which this integer can be explained as a product of smaller integers in a UV completion: in the parlance of our times, can the theory be “clockworked”? We argue that a clockwork construction producing a potential μ4cos(ajFa) for an axion of fundamental period Fa will obey the constraint μ < Fa. For a some applications, including chromonatural inflation with sub-Planckian field range, this constraint obstructs a clockwork UV completion. Alternative routes to a large coupling include fields of large charge (an approach limited by strong coupling) or kinetic mixing (requiring a lighter axion). Our results suggest that completions of axion cosmologies that explain the large parameter in the theory potentially alter the phenomenological predictions of the model.

Cosmology of Theories beyond the SM↗

New approaches for efficient solution of hitting set problem

A new method for solving the hitting set problem is proposed. This method is based on the mapping of the problem onto an integer programming optimization problem. this new approach provides an algorithm with much better performance compare to the algorithms for the hitting set problem that currently are used for solving the diagnosis problem.

integer programming↗

New high performance algorithmic solution for diagnosis problem

In this paper we address the problem of generating the minimal diagnosis from the conflicts. This problem can be formulated as the well-known Hitting Set Problem. Our approach starts by mapping the Hitting Set problem into the Integer Programming Problem that enables us, for the first time, a priori determination of the lower and upper bounds on the size for the solution. Based on these bounds, we introduce a new concept of solution window for the problem. We also propose a new branch-and-bound technique that not only is faster than the current techniques in terms of number of operations (by exploiting the structure of the problem) but also, using the concept of window, allows a massive reduction (pruning) in the number of branches. Furthermore, as the branch-and-bound proceeds, the solution window is dynamically updated and narrowed to enable further pruning.

diagnosis problems↗

An Approach to Reasoning Service Migration in Data and Reasoning Fabric (DRF) Implementation

In this paper we consider service migration problem for Data and Reasoning Fabric (DRF) enabled airspace operations assuming a fixed cloud/edge infrastructure with allocated computing, storage and power resources, where cloud/edge servers, and communication stations are in a wired connected network, while vehicles use a wireless network for communication. The objective is to automatically select the best location for the requested service execution, which achieves minimum cost while satisfying the user quality of service (QoS) and available resources constraints. To this end, estimates of the response time, consumed energy and total cost are defined for each potential compute location. A mixed-integer linear program is then formulated and solved to identify optimal compute locations given QoS constraints, network infrastructure limitations, with worst-case vehicle positioning. The approach is applied to trajectory re-planning use case to avoid a collision with an emergency vehicle in real time.

Air mobility↗

Delayed ripple counter simplifies square-root computation

Ripple subtract technique simplifies the logic circuitry required in a binary computing device to derive the square root of a number. Successively higher numbers are subtracted from a register containing the number out of which the square root is to be extracted. The last number subtracted will be the closest integer to the square root of the number.

Cliff, R.↗

Mathematical Optimization Techniques

The papers collected in this volume were presented at the Symposium on Mathematical Optimization Techniques held in the Santa Monica Civic Auditorium, Santa Monica, California, on October 18-20, 1960. The objective of the symposium was to bring together, for the purpose of mutual education, mathematicians, scientists, and engineers interested in modern optimization techniques. Some 250 persons attended. The techniques discussed included recent developments in linear, integer, convex, and dynamic programming as well as the variational processes surrounding optimal guidance, flight trajectories, statistical decisions, structural configurations, and adaptive control systems. The symposium was sponsored jointly by the University of California, with assistance from the National Science Foundation, the Office of Naval Research, the National Aeronautics and Space Administration, and The RAND Corporation, through Air Force Project RAND.

Bellman, R.↗

A conceptual, parallel operating data compression processor

Data compressor processor concept envisions a simplified system for telemetry communications. It is simultaneously a zero-order processor and a floating aperture, a variable aperture, and a binary integer aperture with a decoded buffet fullness counter.

Anderson, T. O.↗

Linear systems of equations solved using mathematical algorithms

New mathematical algorithm solves linear systems of equations, AX equals B, and preserves the integer properties of the coefficients. The algorithms presented can also be used for the efficient evaluation of determinates and their leading minors.

Bareiss, E. H.↗

Calibration-interval adjustment indicator - A concept

Circuit, when used with decision table, permits relatively unskilled personnel to maintain effective quality control. Design determines required changes in calibration intervals. Interval readings are recorded to nearest integer, making high precision unnecessary. Specific required performance-history information is discussed.

Hedene, P. S.↗