Search NASA⌕ Search

SEARCH · Search NASA

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 181 records · Page 10

Optimal source codes for geometrically distributed integer alphabets

An approach is shown for using the Huffman algorithm indirectly to prove the optimality of a code for an infinite alphabet if an estimate concerning the nature of the code can be made. Attention is given to nonnegative integers with a geometric probability assignment. The particular distribution considered arises in run-length coding and in encoding protocol information in data networks. Questions of redundancy of the optimal code are also investigated.

Gallager, R. G.↗

A fast DFT algorithm using complex integer transforms

Winograd's algorithm for computing the discrete Fourier transform is extended considerably for certain large transform lengths. This is accomplished by performing the cyclic convolution, required by Winograd's method, by a fast transform over certain complex integer fields. This algorithm requires fewer multiplications than either the standard fast Fourier transform or Winograd's more conventional algorithms.

Reed, I. S.↗

A fast complex integer convolution using a hybrid transform

It is shown that the Winograd transform can be combined with a complex integer transform over the Galois field GF(q-squared) to yield a new algorithm for computing the discrete cyclic convolution of complex number points. By this means a fast method for accurately computing the cyclic convolution of a sequence of complex numbers for long convolution lengths can be obtained. This new hybrid algorithm requires fewer multiplications than previous algorithms.

Reed, I. S.↗

Selection of actuator locations for static shape control of large space structures by heuristic integer programing

Orbiting spacecraft such as large space antennas have to maintain a highly accurate space to operate satisfactorily. Such structures require active and passive controls to mantain an accurate shape under a variety of disturbances. Methods for the optimum placement of control actuators for correcting static deformations are described. In particular, attention is focused on the case were control locations have to be selected from a large set of available sites, so that integer programing methods are called for. The effectiveness of three heuristic techniques for obtaining a near-optimal site selection is compared. In addition, efficient reanalysis techniques for the rapid assessment of control effectiveness are presented. Two examples are used to demonstrate the methods: a simple beam structure and a 55m space-truss-parabolic antenna.

Haftka, R. T.↗

VLSI Architectures for the Multiplication of Integers Modulo a Fermat Number

Multiplication is central in the implementation of Fermat number transforms and other residue number algorithms. There is need for a good multiplication algorithm that can be realized easily on a very large scale integration (VLSI) chip. The Leibowitz multiplier is modified to realize multiplication in the ring of integers modulo a Fermat number. This new algorithm requires only a sequence of cyclic shifts and additions. The designs developed for this new multiplier are regular, simple, expandable, and, therefore, suitable for VLSI implementation.

Chang, J. J.↗

Selection of actuator locations for static shape control of large space structures by heuristic integer programing

Orbiting spacecraft such as large space antennas have to maintain a highly accurate shape to operate satisfactorily. Such structures require active and passive controls to maintain an accurate shape under a variety of disturbances. Methods for the optimum placement of control actuators for correcting static deformations are described. In particular, attention is focused on the case were control locations have to be selected from a large set of available sites, so that integer programing methods are called for. The effectiveness of three heuristic techniques for obtaining a near-optimal site selection is compared. In addition, efficient reanalysis techniques for the rapid assessment of control effectiveness are presented. Two examples are used to demonstrate the methods: a simple beam structure and a 55m space-truss-parabolic antenna.

Haftka, R. T.↗

Explicit-explicit subcycling with non-integer time step ratios for structural dynamic systems

An explicit-explicit subcycling procedure for the finite element analysis of structural dynamics is developed. This procedure has relaxed the usual constraint of requiring integer time step ratios for adjacent nodal groups. This allows for greater advantage to be taken of local stability criteria, and thus improves the efficiency of the explicit time integrator. Example problems are included to demonstrate the accuracy and stability of the method.

Neal, Mark O.↗

RSM 1.0 user's guide: A resupply scheduler using integer optimization

The Resupply Scheduling Model (RSM) is a PC based, fully menu-driven computer program. It uses integer programming techniques to determine an optimum schedule to replace components on or before a fixed replacement period, subject to user defined constraints such as transportation mass and volume limits or available repair crew time. Principal input for RSJ includes properties such as mass and volume and an assembly sequence. Resource constraints are entered for each period corresponding to the component properties. Though written to analyze the electrical power system on the Space Station Freedom, RSM is quite general and can be used to model the resupply of almost any system subject to user defined resource constraints. Presented here is a step by step procedure for preparing the input, performing the analysis, and interpreting the results. Instructions for installing the program and information on the algorithms are given.

Viterna, Larry A.↗

Resupply Scheduler Program Using Integer Optimization

Resupply Scheduling Modeler (RSM) fully menu-driven computer program using integer programming techniques to determine optimum schedule for replacing components on or before ends of fixed replacement periods. Written to analyze electrical power system on Space Station Freedom, also used to model resupply of almost any system subject to user-defined constraints on resources. Lifetimes of components, assembly schedules, and other constraints taken into account. Written in APL2(R).

Viterna, L. A.↗

Integer cosine transform compression for Galileo at Jupiter: A preliminary look

The Galileo low-gain antenna mission has a severely rate-constrained channel over which we wish to send large amounts of information. Because of this link pressure, compression techniques for image and other data are being selected. The compression technique that will be used for images is the integer cosine transform (ICT). This article investigates the compression performance of Galileo's ICT algorithm as applied to Galileo images taken during the early portion of the mission and to images that simulate those expected from the encounter at Jupiter.

Ekroot, L.↗

Subjective evaluations of integer cosine transform compressed Galileo solid state imagery

This paper describes a study conducted for the Jet Propulsion Laboratory, Pasadena, California, using 15 evaluators from 12 institutions involved in the Galileo Solid State Imaging (SSI) experiment. The objective of the study was to determine the impact of integer cosine transform (ICT) compression using specially formulated quantization (q) tables and compression ratios on acceptability of the 800 x 800 x 8 monochromatic astronomical images as evaluated visually by Galileo SSI mission scientists. Fourteen different images in seven image groups were evaluated. Each evaluator viewed two versions of the same image side by side on a high-resolution monitor; each was compressed using a different q level. First the evaluators selected the image with the highest overall quality to support them in their visual evaluations of image content. Next they rated each image using a scale from one to five indicating its judged degree of usefulness. Up to four preselected types of images with and without noise were presented to each evaluator.

Haines, Richard F.↗

Parallel integer sorting with medium and fine-scale parallelism

Two new parallel integer sorting algorithms, queue-sort and barrel-sort, are presented and analyzed in detail. These algorithms do not have optimal parallel complexity, yet they show very good performance in practice. Queue-sort designed for fine-scale parallel architectures which allow the queueing of multiple messages to the same destination. Barrel-sort is designed for medium-scale parallel architectures with a high message passing overhead. The performance results from the implementation of queue-sort on a Connection Machine CM-2 and barrel-sort on a 128 processor iPSC/860 are given. The two implementations are found to be comparable in performance but not as good as a fully vectorized bucket sort on the Cray YMP.

Dagum, Leonardo↗

Aerospace applications on integer and combinatorial optimization

Research supported by NASA Langley Research Center includes many applications of aerospace design optimization and is conducted by teams of applied mathematicians and aerospace engineers. This paper investigates the benefits from this combined expertise in formulating and solving integer and combinatorial optimization problems. Applications range from the design of large space antennas to interior noise control. A typical problem. for example, seeks the optimal locations for vibration-damping devices on an orbiting platform and is expressed as a mixed/integer linear programming problem with more than 1500 design variables.

Padula, S. L.↗

Aerospace Applications of Integer and Combinatorial Optimization

Research supported by NASA Langley Research Center includes many applications of aerospace design optimization and is conducted by teams of applied mathematicians and aerospace engineers. This paper investigates the benefits from this combined expertise in formulating and solving integer and combinatorial optimization problems. Applications range from the design of large space antennas to interior noise control. A typical problem, for example, seeks the optimal locations for vibration-damping devices on an orbiting platform and is expressed as a mixed/integer linear programming problem with more than 1500 design variables.

Padula, S. L.↗

A Mixed Integer Linear Program for Airport Departure Scheduling

Aircraft departing from an airport are subject to numerous constraints while scheduling departure times. These constraints include wake-separation constraints for successive departures, miles-in-trail separation for aircraft bound for the same departure fixes, and time-window or prioritization constraints for individual flights. Besides these, emissions as well as increased fuel consumption due to inefficient scheduling need to be included. Addressing all the above constraints in a single framework while allowing for resequencing of the aircraft using runway queues is critical to the implementation of the Next Generation Air Transport System (NextGen) concepts. Prior work on airport departure scheduling has addressed some of the above. However, existing methods use pre-determined runway queues, and schedule aircraft from these departure queues. The source of such pre-determined queues is not explicit, and could potentially be a subjective controller input. Determining runway queues and scheduling within the same framework would potentially result in better scheduling. This paper presents a mixed integer linear program (MILP) for the departure-scheduling problem. The program takes as input the incoming sequence of aircraft for departure from a runway, along with their earliest departure times and an optional prioritization scheme based on time-window of departure for each aircraft. The program then assigns these aircraft to the available departure queues and schedules departure times, explicitly considering wake separation and departure fix restrictions to minimize total delay for all aircraft. The approach is generalized and can be used in a variety of situations, and allows for aircraft prioritization based on operational as well as environmental considerations. We present the MILP in the paper, along with benefits over the first-come-first-serve (FCFS) scheme for numerous randomized problems based on real-world settings. The MILP results in substantially reduced delays as compared to FCFS, and the magnitude of the savings depends on the queue and departure fix structure. The MILP assumes deterministic aircraft arrival times at the runway queues. However, due to taxi time uncertainty, aircraft might arrive either earlier or later than these deterministic times. Thus, to incorporate this uncertainty, we present a method for using the MILP with "overlap discounted rolling planning horizon". The approach is based on valuing near-term decision results more than future ones. We develop a model of taxitime uncertainty based on real-world data, and then compare the baseline FCFS delays with delays using the above MILP in a simple rolling-horizon method and in the overlap discounted scheme.

Gupta, Gautam↗

A Mixed Integer Linear Program for Solving a Multiple Route Taxi Scheduling Problem

Aircraft movements on taxiways at busy airports often create bottlenecks. This paper introduces a mixed integer linear program to solve a Multiple Route Aircraft Taxi Scheduling Problem. The outputs of the model are in the form of optimal taxi schedules, which include routing decisions for taxiing aircraft. The model extends an existing single route formulation to include routing decisions. An efficient comparison framework compares the multi-route formulation and the single route formulation. The multi-route model is exercised for east side airport surface traffic at Dallas/Fort Worth International Airport to determine if any arrival taxi time savings can be achieved by allowing arrivals to have two taxi routes: a route that crosses an active departure runway and a perimeter route that avoids the crossing. Results indicate that the multi-route formulation yields reduced arrival taxi times over the single route formulation only when a perimeter taxiway is used. In conditions where the departure aircraft are given an optimal and fixed takeoff sequence, accumulative arrival taxi time savings in the multi-route formulation can be as high as 3.6 hours more than the single route formulation. If the departure sequence is not optimal, the multi-route formulation results in less taxi time savings made over the single route formulation, but the average arrival taxi time is significantly decreased.

Montoya, Justin Vincent↗

Mixed Integer Linear Programming in Planning

This project, Activity Planning with Resources for the Exploration of Space (APRES), uses a mixed-integer linear program (MILP) to solve planning problems. This work enables APRES to interpret a model file and output a solution with improved human readability. A plan model is optimized using a MILP solver and the best solution is taken. Once a plan is generated, it is parsed allowing it to retain only desired information and modified for swift human readability.

Christina Erwin↗