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 73 records · Page 4

Mixed Integer Programming and Heuristic Scheduling for Space Communication Networks

In this paper, we propose to solve the constrained optimization problem in two phases. The first phase uses heuristic methods such as the ant colony method, particle swarming optimization, and genetic algorithm to seek a near optimal solution among a list of feasible initial populations. The final optimal solution can be found by using the solution of the first phase as the initial condition to the SQP algorithm. We demonstrate the above problem formulation and optimization schemes with a large-scale network that includes the DSN ground stations and a number of spacecraft of deep space missions.

Communication Network Scheduling↗

Techniques for computing the discrete Fourier transform using the quadratic residue Fermat number systems

The complex integer multiplier and adder over the direct sum of two copies of finite field developed by Cozzens and Finkelstein (1985) is specialized to the direct sum of the rings of integers modulo Fermat numbers. Such multiplication over the rings of integers modulo Fermat numbers can be performed by means of two integer multiplications, whereas the complex integer multiplication requires three integer multiplications. Such multiplications and additions can be used in the implementation of a discrete Fourier transform (DFT) of a sequence of complex numbers. The advantage of the present approach is that the number of multiplications needed to compute a systolic array of the DFT can be reduced substantially. The architectural designs using this approach are regular, simple, expandable and, therefore, naturally suitable for VLSI implementation.

Truong, T. K.↗

System and method for generating attitude determinations using GPS

A GPS attitude receiver for determining the attitude of a moving vehicle in conjunction with a first, a second, a third, and a fourth antenna mounted to the moving vehicle. Each of the antennas receives a plurality of GPS signals that each include a carrier component. For each of the carrier components of the received GPS signals there is an integer ambiguity associated with the first and fourth antennas, an integer ambiguity associated with second and fourth antennas, and an integer ambiguity associated with the third and fourth antennas. The GPS attitude receiver measures phase values for the carrier components of the GPS signals received from each of the antennas at a plurality of measurement epochs during an initialization period and at a measurement epoch after the initialization period. In response to the phase values measured at the measurement epochs during the initialization period, the GPS attitude receiver computes integer ambiguity resolution values representing resolution of the integer ambiguities. Then, in response to the computed integer ambiguity resolution values and the phase value measured at the measurement epoch after the initialization period, it computes values defining the attitude of the moving vehicle at the measurement epoch after the initialization period.

Cohen, Clark E.↗

Variable length data formats

The purpose of this paper is to discuss a number of variable length floating point and integer formats and to give the various advantages and disadvantages of their use. Often it is known in advance that a given integer will not exceed a certain magnitude or that a particular floating point number is accurate to only 'n' places of accuracy. Faced with this, it is good engineering to choose variable length floating point and integer formats which require the least amount of hardware or the minimum amount of software or which have some other dominant advantage. The formats discussed have the advantage that length change algorithms are invariant with respect to data types (unsigned, signed, floating point, integers, and complex numbers). The STARAN associative array processor, which uses a completely variable fixed point and floating point formats, is described.

Brakefield, J. C.↗

Digital numerically controlled oscillator

The frequency and phase of an output signal from an oscillator circuit are controlled with accuracy by a digital input word. Positive and negative alterations in output frequency are both provided for by translating all values of input words so that they are positive. The oscillator reference frequency is corrected only in one direction, by adding phase to the output frequency of the oscillator. The input control word is translated to a single algebraic sign and the digital 1 is added thereto. The translated input control word is then accumulated. A reference clock signal having a frequency at an integer multiple of the desired frequency of the output signal is generated. The accumulated control word is then compared with a threshold level. The output signal is adjusted in a single direction by dividing the frequency of the reference clock signal by a first integer or by an integer different from the first integer.

Cellier, A.↗

A new second-order integration algorithm for simulating mechanical dynamic systems

A new integration algorithm which has the simplicity of Euler integration but exhibits second-order accuracy is described. In fixed-step numerical integration of differential equations for mechanical dynamic systems the method represents displacement and acceleration variables at integer step times and velocity variables at half-integer step times. Asymptotic accuracy of the algorithm is twice that of trapezoidal integration and ten times that of second-order Adams-Bashforth integration. The algorithm is also compatible with real-time inputs when used for a real-time simulation. It can be used to produce simulation outputs at double the integration frame rate, i.e., at both half-integer and integer frame times, even though it requires only one evaluation of state-variable derivatives per integration step. The new algorithm is shown to be especially effective in the simulation of lightly-damped structural modes. Both time-domain and frequency-domain accuracy comparisons with traditional integration methods are presented. Stability of the new algorithm is also examined.

Howe, R. M.↗

Maximum-entropy probability distributions under Lp-norm constraints

Continuous probability density functions and discrete probability mass functions are tabulated which maximize the differential entropy or absolute entropy, respectively, among all probability distributions with a given L sub p norm (i.e., a given pth absolute moment when p is a finite integer) and unconstrained or constrained value set. Expressions for the maximum entropy are evaluated as functions of the L sub p norm. The most interesting results are obtained and plotted for unconstrained (real valued) continuous random variables and for integer valued discrete random variables. The maximum entropy expressions are obtained in closed form for unconstrained continuous random variables, and in this case there is a simple straight line relationship between the maximum differential entropy and the logarithm of the L sub p norm. Corresponding expressions for arbitrary discrete and constrained continuous random variables are given parametrically; closed form expressions are available only for special cases. However, simpler alternative bounds on the maximum entropy of integer valued discrete random variables are obtained by applying the differential entropy results to continuous random variables which approximate the integer valued random variables in a natural manner. All the results are presented in an integrated framework that includes continuous and discrete random variables, constraints on the permissible value set, and all possible values of p. Understanding such as this is useful in evaluating the performance of data compression schemes.

Dolinar, S.↗

ALPS: A Linear Program Solver

ALPS is a computer program which can be used to solve general linear program (optimization) problems. ALPS was designed for those who have minimal linear programming (LP) knowledge and features a menu-driven scheme to guide the user through the process of creating and solving LP formulations. Once created, the problems can be edited and stored in standard DOS ASCII files to provide portability to various word processors or even other linear programming packages. Unlike many math-oriented LP solvers, ALPS contains an LP parser that reads through the LP formulation and reports several types of errors to the user. ALPS provides a large amount of solution data which is often useful in problem solving. In addition to pure linear programs, ALPS can solve for integer, mixed integer, and binary type problems. Pure linear programs are solved with the revised simplex method. Integer or mixed integer programs are solved initially with the revised simplex, and the completed using the branch-and-bound technique. Binary programs are solved with the method of implicit enumeration. This manual describes how to use ALPS to create, edit, and solve linear programming problems. Instructions for installing ALPS on a PC compatible computer are included in the appendices along with a general introduction to linear programming. A programmers guide is also included for assistance in modifying and maintaining the program.

Ferencz, Donald C.↗

Alternative regularizations for Outer-Approximation algorithms for convex MINLP

In this work, we extend the regularization framework from Kronqvist et al. (Math Program 180(1):285–310, 2020) by incorporating several new regularization functions and develop a regularized single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance metrics and Lagrangean approximations, used in the projection problem for finding new integer combinations to be used within the Outer-Approximation (OA) method. The new approach, called Regularized Outer-Approximation (ROA), has been implemented as part of the open-source Mixed-integer nonlinear decomposition toolbox for Pyomo—MindtPy. We compare the OA method with seven regularization function alternatives for ROA. Moreover, we extend the LP/NLP Branch and Bound method proposed by Quesada and Grossmann (Comput Chem Eng 16(10–11):937–947, 1992) to include regularization in an algorithm denoted RLP/NLP. We provide convergence guarantees for both ROA and RLP/NLP. Finally, we perform an extensive computational experiment considering all convex MINLP problems in the benchmark library MINLPLib. The computational results show clear advantages of using regularization combined with the OA method.

Convex Mixed-integer nonlinear programming↗

The fast decoding of Reed-Solomon codes using number theoretic transforms

It is shown that Reed-Solomon (RS) codes can be encoded and decoded by using a fast Fourier transform (FFT) algorithm over finite fields. The arithmetic utilized to perform these transforms requires only integer additions, circular shifts and a minimum number of integer multiplications. The computing time of this transform encoder-decoder for RS codes is less than the time of the standard method for RS codes. More generally, the field GF(q) is also considered, where q is a prime of the form K x 2 to the nth power + 1 and K and n are integers. GF(q) can be used to decode very long RS codes by an efficient FFT algorithm with an improvement in the number of symbols. It is shown that a radix-8 FFT algorithm over GF(q squared) can be utilized to encode and decode very long RS codes with a large number of symbols. For eight symbols in GF(q squared), this transform over GF(q squared) can be made simpler than any other known number theoretic transform with a similar capability. Of special interest is the decoding of a 16-tuple RS code with four errors.

Reed, I. S.↗

Interactive Data-Collection And Display Program With Debugging

INFORM program designed to aid assembly language programers of SEL 810B computers in working with scaled-integer applications. INFORM was developed to meet needs of engineers designing real-time digital controls using SEL 810B where time and hardware constraints make use of integer arithmetic and scaled integers necessary. Package includes auxiliary routines that add dynamic data acquisition and high-speed dynamic display to INFORM capabilities.

Cwynar, D. S.↗

Implementing direct, spatially isolated problems on transputer networks

Parametric studies were performed on transputer networks of up to 40 processors to determine how to implement and maximize the performance of the solution of problems where no processor-to-processor data transfer is required for the problem solution (spatially isolated). Two types of problems are investigated a computationally intensive problem where the solution required the transmission of 160 bytes of data through the parallel network, and a communication intensive example that required the transmission of 3 Mbytes of data through the network. This data consists of solutions being sent back to the host processor and not intermediate results for another processor to work on. Studies were performed on both integer and floating-point transputers. The latter features an on-chip floating-point math unit and offers approximately an order of magnitude performance increase over the integer transputer on real valued computations. The results indicate that a minimum amount of work is required on each node per communication to achieve high network speedups (efficiencies). The floating-point processor requires approximately an order of magnitude more work per communication than the integer processor because of the floating-point unit's increased computing capacity.

Ellis, Graham K.↗

Boron-containing organosilane polymers and ceramic materials thereof

The present invention relates to a polyorgano borosilane ceramic precursor polymer comprising a plurality of repeating units of the formula: (R(sup 1) single bond B)(sub p) being linked together at B by second units of the formula: single bond (R sup 2) single bond (Si single bond R sup 3) single bond (sub q), where R(sup 1) is a lower alkyl, cycloalkyl, phenyl, or (R(sup 2)R(sup 3) single bond Si single bond B single bond)(sub n) and R(sup 2) and R(sup 3) are each independently selected from hydrogen, lower alkyl, vinyl, cycloalkyl, or aryl, n is an integer between 1 and 100; p is an integer between 1 and 100; and q is an integer between 1 and 100. These materials are prepared by combining an organo borohalide of the formula R(sup 4) single bond B single bond (X sup 1) (sub 2) where R(sup 4) is selected from halogen, lower alkyl, cycloalkyl, or aryl, and an organo halosilane of the formula: R(sup 2)(R sup 3)Si(X sup 2)(sub 2) where R(sup 2) and R (sup 3) are each independently selected from lower alkyl, cycloalkyl, or aryl, and X(sup 1) and X(sup 2) are each independently selected from halogen, in an anhydrous aprotic solvent having a boiling point at ambient pressure of not greater than 160 C with in excess of four equivalents of an alkali metal, heating the reaction mixture and recovering the polyorgano borosilane. These silicon boron polymers are useful to generate high-temperature ceramic materials, such as SiC, SiB4, and B4C, upon thermal degradation above 600 C.

Riccitiello, Salvatore R.↗

Transform coding for space applications

Data compression coding requirements for aerospace applications differ somewhat from the compression requirements for entertainment systems. On the one hand, entertainment applications are bit rate driven with the goal of getting the best quality possible with a given bandwidth. Science applications are quality driven with the goal of getting the lowest bit rate for a given level of reconstruction quality. In the past, the required quality level has been nothing less than perfect allowing only the use of lossless compression methods (if that). With the advent of better, faster, cheaper missions, an opportunity has arisen for lossy data compression methods to find a use in science applications as requirements for perfect quality reconstruction runs into cost constraints. This paper presents a review of the data compression problem from the space application perspective. Transform coding techniques are described and some simple, integer transforms are presented. The application of these transforms to space-based data compression problems is discussed. Integer transforms have an advantage over conventional transforms in computational complexity. Space applications are different from broadcast or entertainment in that it is desirable to have a simple encoder (in space) and tolerate a more complicated decoder (on the ground) rather than vice versa. Energy compaction with new transforms are compared with the Walsh-Hadamard (WHT), Discrete Cosine (DCT), and Integer Cosine (ICT) transforms.

Glover, Daniel↗

Dynamic Flow Management Problems in Air Transportation

In 1995, over six hundred thousand licensed pilots flew nearly thirty-five million flights into over eighteen thousand U.S. airports, logging more than 519 billion passenger miles. Since demand for air travel has increased by more than 50% in the last decade while capacity has stagnated, congestion is a problem of undeniable practical significance. In this thesis, we will develop optimization techniques that reduce the impact of congestion on the national airspace. We start by determining the optimal release times for flights into the airspace and the optimal speed adjustment while airborne taking into account the capacitated airspace. This is called the Air Traffic Flow Management Problem (TFMP). We address the complexity, showing that it is NP-hard. We build an integer programming formulation that is quite strong as some of the proposed inequalities are facet defining for the convex hull of solutions. For practical problems, the solutions of the LP relaxation of the TFMP are very often integral. In essence, we reduce the problem to efficiently solving large scale linear programming problems. Thus, the computation times are reasonably small for large scale, practical problems involving thousands of flights. Next, we address the problem of determining how to reroute aircraft in the airspace system when faced with dynamically changing weather conditions. This is called the Air Traffic Flow Management Rerouting Problem (TFMRP) We present an integrated mathematical programming approach for the TFMRP, which utilizes several methodologies, in order to minimize delay costs. In order to address the high dimensionality, we present an aggregate model, in which we formulate the TFMRP as a multicommodity, integer, dynamic network flow problem with certain side constraints. Using Lagrangian relaxation, we generate aggregate flows that are decomposed into a collection of flight paths using a randomized rounding heuristic. This collection of paths is used in a packing integer programming formulation, the solution of which generates feasible and near-optimal routes for individual flights. The algorithm, termed the Lagrangian Generation Algorithm, is used to solve practical problems in the southwestern portion of United States in which the solutions are within 1% of the corresponding lower bounds.

Patterson, Sarah Stock↗