Search NASASearch

SEARCH · Search NASA

Results for “integer programming”

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 163 records · Page 9

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 solving 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 a large space structure and is expressed as a mixed/integer linear programming problem with more than 1500 design variables.

Padula, S. L.

A Fortran-90 Based Multiprecision System

The author has developed a new version of his Fortran multiprecision computation system that is based on the Fortran-90 language. With this new approach, a translator program is not required - translation of Fortran code for multiprecision is accomplished by merely utilizing advanced features of Fortran-90, such as derived data types and operator extensions. This approach results in more reliable translation and also permits programmers of multiprecision applications to utilize the full power of the Fortran-90 language. Three multiprecision datatypes are supported in this system: multiprecision integer. real and complex. All the usual Fortran conventions for mixed mode operations are supported, and many of the Fortran intrinsics, such as SIN, EXP and MOD, are supported with multiprecision arguments. This paper also briefly describes an interesting application of this software, wherein new number-theoretic identities have been discovered by means of multiprecision computations.

Bailey, David H.

Proceedings of the Second NASA Formal Methods Symposium

This publication contains the proceedings of the Second NASA Formal Methods Symposium sponsored by the National Aeronautics and Space Administration and held in Washington D.C. April 13-15, 2010. Topics covered include: Decision Engines for Software Analysis using Satisfiability Modulo Theories Solvers; Verification and Validation of Flight-Critical Systems; Formal Methods at Intel -- An Overview; Automatic Review of Abstract State Machines by Meta Property Verification; Hardware-independent Proofs of Numerical Programs; Slice-based Formal Specification Measures -- Mapping Coupling and Cohesion Measures to Formal Z; How Formal Methods Impels Discovery: A Short History of an Air Traffic Management Project; A Machine-Checked Proof of A State-Space Construction Algorithm; Automated Assume-Guarantee Reasoning for Omega-Regular Systems and Specifications; Modeling Regular Replacement for String Constraint Solving; Using Integer Clocks to Verify the Timing-Sync Sensor Network Protocol; Can Regulatory Bodies Expect Efficient Help from Formal Methods?; Synthesis of Greedy Algorithms Using Dominance Relations; A New Method for Incremental Testing of Finite State Machines; Verification of Faulty Message Passing Systems with Continuous State Space in PVS; Phase Two Feasibility Study for Software Safety Requirements Analysis Using Model Checking; A Prototype Embedding of Bluespec System Verilog in the PVS Theorem Prover; SimCheck: An Expressive Type System for Simulink; Coverage Metrics for Requirements-Based Testing: Evaluation of Effectiveness; Software Model Checking of ARINC-653 Flight Code with MCP; Evaluation of a Guideline by Formal Modelling of Cruise Control System in Event-B; Formal Verification of Large Software Systems; Symbolic Computation of Strongly Connected Components Using Saturation; Towards the Formal Verification of a Distributed Real-Time Automotive System; Slicing AADL Specifications for Model Checking; Model Checking with Edge-valued Decision Diagrams; and Data-flow based Model Analysis.

Munoz, Cesar

Proposed data compression schemes for the Galileo S-band contingency mission

The Galileo spacecraft is currently on its way to Jupiter and its moons. In April 1991, the high gain antenna (HGA) failed to deploy as commanded. In case the current efforts to deploy the HGA fails, communications during the Jupiter encounters will be through one of two low gain antenna (LGA) on an S-band (2.3 GHz) carrier. A lot of effort has been and will be conducted to attempt to open the HGA. Also various options for improving Galileo's telemetry downlink performance are being evaluated in the event that the HGA will not open at Jupiter arrival. Among all viable options the most promising and powerful one is to perform image and non-image data compression in software onboard the spacecraft. This involves in-flight re-programming of the existing flight software of Galileo's Command and Data Subsystem processors and Attitude and Articulation Control System (AACS) processor, which have very limited computational and memory resources. In this article we describe the proposed data compression algorithms and give their respective compression performance. The planned image compression algorithm is a 4 x 4 or an 8 x 8 multiplication-free integer cosine transform (ICT) scheme, which can be viewed as an integer approximation of the popular discrete cosine transform (DCT) scheme. The implementation complexity of the ICT schemes is much lower than the DCT-based schemes, yet the performances of the two algorithms are indistinguishable. The proposed non-image compression algorith is a Lempel-Ziv-Welch (LZW) variant, which is a lossless universal compression algorithm based on a dynamic dictionary lookup table. We developed a simple and efficient hashing function to perform the string search.

Cheung, Kar-Ming

Ground control system for the midcourse space experiment UTC clock

One goal of the Midcourse Space Experiment (MSX) spacecraft Operations Planning Center is to maintain the onboard satellite UTC clock (UTC(MSX)) to within 1 millisecond of UTC(APL) (the program requirement is 10 msec). The UTC(MSX) clock employs as its time base an APL built 5 MHz quartz oscillator, which is expected to have frequency instabilities (aging rate + drift rate + frequency offset) that will cause the clock to drift approximately two to ten milliseconds per day. The UTC(MSX) clock can be advanced or retarded by the APL MSX satellite ground control center by integer multiples of 1 millisecond. The MSX Operations Planning Center is developing software which records the drift of UTC(MSX) relative to UTC(APL) and which schedules the time of day and magnitude of UTC(MSX) clock updates up to 48 hours in advance. Because of the manner in which MSX spacecraft activities are scheduled, MSX clock updates are planned 24 to 48 hours in advance, and stored in the satellite's computer controller for later execution. Data will be collected on the drift of UTC(MSX) relative to UTC(APL) over a three to five day period. Approximately six times per day, the time offset between UTC(MSX) and UTC(APL) will be measured by APL with a resolution of less than 100 microseconds. From this data a second order analytical model of the clock's drift will be derived. This model will be used to extrapolate the offset of the MSX clock in time from the present to 48 hours in the future. MSX clock updates will be placed on the spacecraft's daily schedule whenever the predicted clock offset exceeds 0.5 milliseconds. The paper includes a discussion of how the empirical model of the MSX clock is derived from satellite telemetry data, as well as the algorithm used to schedule MSX clock updates based on the model.

Dragonette, Richard

Conservative Patch Algorithm and Mesh Sequencing for PAB3D

A mesh-sequencing algorithm and a conservative patched-grid-interface algorithm (hereafter Patch Algorithm ) have been incorporated into the PAB3D code, which is a computer program that solves the Navier-Stokes equations for the simulation of subsonic, transonic, or supersonic flows surrounding an aircraft or other complex aerodynamic shapes. These algorithms are efficient, flexible, and have added tremendously to the capabilities of PAB3D. The mesh-sequencing algorithm makes it possible to perform preliminary computations using only a fraction of the grid cells (provided the original cell count is divisible by an integer) along any grid coordinate axis, independently of the other axes. The patch algorithm addresses another critical need in multi-block grid situation where the cell faces of adjacent grid blocks may not coincide, leading to errors in calculating fluxes of conserved physical quantities across interfaces between the blocks. The patch algorithm, based on the Stokes integral formulation of the applicable conservation laws, effectively matches each of the interfacial cells on one side of the block interface to the corresponding fractional cell area pieces on the other side. This approach is comprehensive and unified such that all interface topology is automatically processed without user intervention. This algorithm is implemented in a preprocessing code that creates a cell-by-cell database that will maintain flux conservation at any level of full or reduced grid density as the user may choose by way of the mesh-sequencing algorithm. These two algorithms have enhanced the numerical accuracy of the code, reduced the time and effort for grid preprocessing, and provided users with the flexibility of performing computations at any desired full or reduced grid resolution to suit their specific computational requirements.

Pao, S. P.

Investigation of correlation classification techniques

A two-step classification algorithm for processing multispectral scanner data was developed and tested. The first step is a single pass clustering algorithm that assigns each pixel, based on its spectral signature, to a particular cluster. The output of that step is a cluster tape in which a single integer is associated with each pixel. The cluster tape is used as the input to the second step, where ground truth information is used to classify each cluster using an iterative method of potentials. Once the clusters have been assigned to classes the cluster tape is read pixel-by-pixel and an output tape is produced in which each pixel is assigned to its proper class. In addition to the digital classification programs, a method of using correlation clustering to process multispectral scanner data in real time by means of an interactive color video display is also described.

Haskell, R. E.

A digital algorithm for spectral deconvolution with noise filtering and peak picking: NOFIPP-DECON

Noise-filtering, peak-picking deconvolution software incorporates multiple convoluted convolute integers and multiparameter optimization pattern search. The two theories are described and three aspects of the software package are discussed in detail. Noise-filtering deconvolution was applied to a number of experimental cases ranging from noisy, nondispersive X-ray analyzer data to very noisy photoelectric polarimeter data. Comparisons were made with published infrared data, and a man-machine interactive language has evolved for assisting in very difficult cases. A modified version of the program is being used for routine preprocessing of mass spectral and gas chromatographic data.

Edwards, T. R.

Subroutines For Image Processing

Image Processing Library computer program, IPLIB, is collection of subroutines facilitating use of COMTAL image-processing system driven by HP 1000 computer. Functions include addition or subtraction of two images with or without scaling, display of color or monochrome images, digitization of image from television camera, display of test pattern, manipulation of bits, and clearing of screen. Provides capability to read or write points, lines, and pixels from image; read or write at location of cursor; and read or write array of integers into COMTAL memory. Written in FORTRAN 77.

Faulcon, Nettie D.

A Hierarchical Approach to Fracture Mechanics

Recent research conducted under NASA LaRC's Creativity and Innovation Program has led to the development of an initial approach for a hierarchical fracture mechanics. This methodology unites failure mechanisms occurring at different length scales and provides a framework for a physics-based theory of fracture. At the nanoscale, parametric molecular dynamic simulations are used to compute the energy associated with atomic level failure mechanisms. This information is used in a mesoscale percolation model of defect coalescence to obtain statistics of fracture paths and energies through Monte Carlo simulations. The mathematical structure of predicted crack paths is described using concepts of fractal geometry. The non-integer fractal dimension relates geometric and energy measures between meso- and macroscales. For illustration, a fractal-based continuum strain energy release rate is derived for inter- and transgranular fracture in polycrystalline metals.

Saether, Erik

Virtual Machine Language 2.1

VML (Virtual Machine Language) is an advanced computing environment that allows spacecraft to operate using mechanisms ranging from simple, time-oriented sequencing to advanced, multicomponent reactive systems. VML has developed in four evolutionary stages. VML 0 is a core execution capability providing multi-threaded command execution, integer data types, and rudimentary branching. VML 1 added named parameterized procedures, extensive polymorphism, data typing, branching, looping issuance of commands using run-time parameters, and named global variables. VML 2 added for loops, data verification, telemetry reaction, and an open flight adaptation architecture. VML 2.1 contains major advances in control flow capabilities for executable state machines. On the resource requirements front, VML 2.1 features a reduced memory footprint in order to fit more capability into modestly sized flight processors, and endian-neutral data access for compatibility with Intel little-endian processors. Sequence packaging has been improved with object-oriented programming constructs and the use of implicit (rather than explicit) time tags on statements. Sequence event detection has been significantly enhanced with multi-variable waiting, which allows a sequence to detect and react to conditions defined by complex expressions with multiple global variables. This multi-variable waiting serves as the basis for implementing parallel rule checking, which in turn, makes possible executable state machines. The new state machine feature in VML 2.1 allows the creation of sophisticated autonomous reactive systems without the need to develop expensive flight software. Users specify named states and transitions, along with the truth conditions required, before taking transitions. Transitions with the same signal name allow separate state machines to coordinate actions: the conditions distributed across all state machines necessary to arm a particular signal are evaluated, and once found true, that signal is raised. The selected signal then causes all identically named transitions in all present state machines to be taken simultaneously. VML 2.1 has relevance to all potential space missions, both manned and unmanned. It was under consideration for use on Orion.

Riedel, Joseph E.

An empirical study of FORTRAN programs for parallelizing compilers

Some results are reported from an empirical study of program characteristics that are important in parallelizing compiler writers, especially in the area of data dependence analysis and program transformations. The state of the art in data dependence analysis and some parallel execution techniques are examined. The major findings are included. Many subscripts contain symbolic terms with unknown values. A few methods of determining their values at compile time are evaluated. Array references with coupled subscripts appear quite frequently; these subscripts must be handled simultaneously in a dependence test, rather than being handled separately as in current test algorithms. Nonzero coefficients of loop indexes in most subscripts are found to be simple: they are either 1 or -1. This allows an exact real-valued test to be as accurate as an exact integer-valued test for one-dimensional or two-dimensional arrays. Dependencies with uncertain distance are found to be rather common, and one of the main reasons is the frequent appearance of symbolic terms with unknown values.

Shen, Zhiyu

PCIPS 2.0: Powerful multiprofile image processing implemented on PCs

Over the years, the processing power of personal computers has steadily increased. Now, 386- and 486-based PC's are fast enough for many image processing applications, and inexpensive enough even for amateur astronomers. PCIPS is an image processing system based on these platforms that was designed to satisfy a broad range of data analysis needs, while requiring minimum hardware and providing maximum expandability. It will run (albeit at a slow pace) even on a 80286 with 640K memory, but will take full advantage of bigger memory and faster CPU's. Because the actual image processing is performed by external modules, the system can be easily upgraded by the user for all sorts of scientific data analysis. PCIPS supports large format lD and 2D images in any numeric type from 8-bit integer to 64-bit floating point. The images can be displayed, overlaid, printed and any part of the data examined via an intuitive graphical user interface that employs buttons, pop-up menus, and a mouse. PCIPS automatically converts images between different types and sizes to satisfy the requirements of various applications. PCIPS features an API that lets users develop custom applications in C or FORTRAN. While doing so, a programmer can concentrate on the actual data processing, because PCIPS assumes responsibility for accessing images and interacting with the user. This also ensures that all applications, even custom ones, have a consistent and user-friendly interface. The API is compatible with factory programming, a metaphor for constructing image processing procedures that will be implemented in future versions of the system. Several application packages were created under PCIPS. The basic package includes elementary arithmetics and statistics, geometric transformations and import/export in various formats (FITS, binary, ASCII, and GIF). The CCD processing package and the spectral analysis package were successfully used to reduce spectra from the Nordic Telescope at La Palma. A photometry package is also available, and other packages are being developed. A multitasking version of PCIPS that utilizes the factory programming concept is currently under development. This version will remain compatible (on the source code level) with existing application packages and custom applications.

Smirnov, O. M.

SMEX-Lite Modular Solar Array Architecture

For the most part, Goddard solar arrays have been custom designs that are unique to each mission. The solar panel design has been frozen prior to issuing an RFP for their procurement. There has typically been 6-9 months between RFP release and contract award, followed by an additional 24 months for performance of the contract. For Small Explorer (SMEX) missions, with three years between mission definition and launch, this has been a significant problem. The SMEX solar panels have been sufficiently small that the contract performance period has been reduced to 12-15 months. The bulk of this time is used up in the final design definition and fabrication of flight solar cell assemblies. Even so, it has been virtually impossible to have the spacecraft design at a level of maturity sufficient to freeze the solar panel geometry and release the RFP in time to avoid schedule problems with integrating the solar panels to the spacecraft. With that in mind, the SMEX-Lite project team developed a modular architecture for the assembly of solar arrays to greatly reduce the cost and schedule associated with the development of a mission- specific solar array. In the modular architecture, solar cells are fabricated onto small substrate panels. This modular panel (approximately 8.5" x 17" in this case) becomes the building block for constructing solar arrays for multiple missions with varying power requirements and geometrical arrangements. The mechanical framework that holds these modules together as a solar array is the only mission-unique design, changing in size and shape as required for each mission. There are several advantages to this approach. First, the typical solar array development cycle requires a mission unique design, procurement, and qualification including a custom qualification panel. With the modular architecture, a single qualification of the SMEX-Lite modules and the associated mechanical framework in a typical configuration provided a qualification by similarity to multiple missions. It then becomes possible to procure solar array modules in advance of mission definition and respond quickly and inexpensively to a selected mission's unique requirements. The solar array modular architecture allows the procurement of solar array modules before the array geometry has been frozen. This reduces the effect of procurement lead-time on the mission integration and test flow by as much as 50%. Second, by spreading the non-recurring costs over multiple missions, the cost per unit area is also reduced. In the case of the SMEX-Lite procurement, this reduction was by about one third of the cost per unit area compared to previous SMEX mission-unique procurements. Third, the modular architecture greatly facilitates the infusion of new solar cell technologies into flight programs as these technologies become available. New solar cell technologies need only be fabricated onto a standard-sized module to be incorporated into the next available mission. The modular solar array can be flown in a mixed configuration with some new and some standard cell technologies. Since each module has its own wiring terminals, the array can be arranged as desired electrically with little impact to cost and schedule. The solar array modular architecture does impose some additional constraints on systems and subsystem engineers. First, they must work with discrete solar array modules rather than size the array to fit exactly within an available envelope. The array area is constrained to an integer multiple of the module area. Second, the modular design is optimized for space radiation and thermal environments not greatly different from a typical SMEX LEO environment. For example, a mission with a highly elliptical orbit (e.g., Polar, SMEX/FAST) would require thicker coverglasses to protect the solar cells from the more intense radiation environment.

Lyons, John

Optimal Compression of Floating-Point Astronomical Images Without Significant Loss of Information

We describe a compression method for floating-point astronomical images that gives compression ratios of 6 - 10 while still preserving the scientifically important information in the image. The pixel values are first preprocessed by quantizing them into scaled integer intensity levels, which removes some of the uncompressible noise in the image. The integers are then losslessly compressed using the fast and efficient Rice algorithm and stored in a portable FITS format file. Quantizing an image more coarsely gives greater image compression, but it also increases the noise and degrades the precision of the photometric and astrometric measurements in the quantized image. Dithering the pixel values during the quantization process greatly improves the precision of measurements in the more coarsely quantized images. We perform a series of experiments on both synthetic and real astronomical CCD images to quantitatively demonstrate that the magnitudes and positions of stars in the quantized images can be measured with the predicted amount of precision. In order to encourage wider use of these image compression methods, we have made available a pair of general-purpose image compression programs, called fpack and funpack, which can be used to compress any FITS format image.

Pence, William D.

Constitutive modeling for isotropic materials (HOST)

This report presents the results of the second year of work on a problem which is part of the NASA HOST Program. Its goals are: (1) to develop and validate unified constitutive models for isotropic materials, and (2) to demonstrate their usefulness for structural analyses of hot section components of gas turbine engines. The unified models selected for development and evaluation are that of Bodner-Partom and Walker. For model evaluation purposes, a large constitutive data base is generated for a B1900 + Hf alloy by performing uniaxial tensile, creep, cyclic, stress relation, and thermomechanical fatigue (TMF) tests as well as biaxial (tension/torsion) tests under proportional and nonproportional loading over a wide range of strain rates and temperatures. Systematic approaches for evaluating material constants from a small subset of the data base are developed. Correlations of the uniaxial and biaxial tests data with the theories of Bodner-Partom and Walker are performed to establish the accuracy, range of applicability, and integability of the models. Both models are implemented in the MARC finite element computer code and used for TMF analyses. Benchmark notch round experiments are conducted and the results compared with finite-element analyses using the MARC code and the Walker model.

Lindholm, U. S.

Characterization of Deficiencies in the Frequency Domain Forced Response Analysis Technique for Supersonic Turbine Bladed Disks

Turbine blades in rocket and jet engine turbomachinery experience enormous harmonic loading conditions. These loads result from the integer number of upstream and downstream stator vanes as well as the other turbine stages. Assessing the blade structural integrity is a complex task requiring an initial characterization of whether resonance is possible and then performing a forced response analysis if that condition is met. The standard technique for forced response analysis in rocket engine turbines is to decompose a computational fluid dynamics (CFD).generated flow field into its harmonic components, and to then perform a frequency response analysis at the problematic natural frequencies using cyclically symmetric structural dynamic models. Recent CFD analysis and water-flow testing at NASA/MSFC, though, indicates that this technique may miss substantial harmonic and non ]harmonic excitation sources that become present in complex flows. This complex content can only be captured by a CFD flow field encompassing at least an entire revolution. A substantial development effort to create a series of software programs to enable application of the 360 degree forcing function in a frequency response analysis on cyclic symmetric models has been completed (to be described in a future paper), but the question still remains whether the frequency response analysis itself is capable of capturing the excitation content sufficiently. Two studies comparing frequency response analysis with transient response analysis, therefore, of bladed-disks undergoing this complex flow environment have been performed. The first is of a bladed disk with each blade modeled by simple beam elements and the disk modeled with plates (using the finite element code MSC/NASTRAN). The focus of this model is to be representative of response of realistic bladed disks, and so the dimensions are roughly equivalent to the new J2X rocket engine 1st stage fuel pump turbine. The simplicity of the model allows the CFD load to be able to be readily applied, along with analytical and experimental variations in both the temporal and spatial fourier components of the excitation. In addition, this model is a first step in identifying response differences between transient and frequency forced response analysis techniques. The second phase assesses this difference for a much more realistic solid model of a bladed-disk in order to evaluate the effect of the spatial variation in loading on blade dominated modes. Neither research on the accuracy of the frequency response method when used in this context or a comprehensive study of the effect of test-observed variation on blade forced response have been found in the literature, so this research is a new contribution to practical structural dynamic analysis of gas turbines. The primary excitation of the upstream nozzles interacts with the blades on fuel pump of the J2X causes the 5th Nodal diameter modes to be excited, as explained by Tyler and Sofrin1, so a modal analysis was first performed on the beam/plate model and the 5ND bladed-disk mode at 40167 hz was identified and chosen to be the one excited at resonance (see figure 1). The first forced response analysis with this model focuses on identifying differences between frequency and transient response analyses. A hypothesis going into the analysis was that perhaps the frequency response was enforcing a temporal periodicity that did not really exist, and so therefore it would overestimate the response. As high dynamic response was a considerable source of stress in the J2X, examining this concept could potentially be beneficial for the program.

Brown, Andrew M.

Optimization of rotor blades for combined structural, dynamic, and aerodynamic properties

Optimal helicopter blade design with computer-based mathematical programming has received more and more attention in recent years. Most of the research has focused on optimum dynamic characteristics of rotor blades to reduce vehicle vibration. There is also work on optimization of aerodynamic performance and on composite structural design. This research has greatly increased our understanding of helicopter optimum design in each of these aspects. Helicopter design is an inherently multidisciplinary process involving strong interactions among various disciplines which can appropriately include aerodynamics; dynamics, both flight dynamics and structural dynamics; aeroelasticity: vibrations and stability; and even acoustics. Therefore, the helicopter design process must satisfy manifold requirements related to the aforementioned diverse disciplines. In our present work, we attempt to combine several of these important effects in a unified manner. First, we design a blade with optimum aerodynamic performance by proper layout of blade planform and spanwise twist. Second, the blade is designed to have natural frequencies that are placed away from integer multiples of the rotor speed for a good dynamic characteristics. Third, the structure is made as light as possible with sufficient rotational inertia to allow for autorotational landing, with safe stress margins and flight fatigue life at each cross-section, and with aeroelastical stability and low vibrations. Finally, a unified optimization refines the solution.

He, Cheng-Jian