A Complexity Theoretic Perspective on Robustness Analysis
The purpose of the paper is to present the steps that have been taken towards an algorithm theory of stability and robustness.
Algorithm Stability Robustness↗
SEARCH · Engineering Papers
Results for “algorithm complexity analysis”
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.
Discrete Fourier Transform Analysis in a Complex Vector Space
Alternative computational strategies for the Discrete Fourier Transform (DFT) have been developed using analysis of geometric manifolds. This approach provides a general framework for performing DFT calculations, and suggests a more efficient implementation of the DFT for applications using iterative transform methods, particularly phase retrieval. The DFT can thus be implemented using fewer operations when compared to the usual DFT counterpart. The software decreases the run time of the DFT in certain applications such as phase retrieval that iteratively call the DFT function. The algorithm exploits a special computational approach based on analysis of the DFT as a transformation in a complex vector space. As such, this approach has the potential to realize a DFT computation that approaches N operations versus Nlog(N) operations for the equivalent Fast Fourier Transform (FFT) calculation.
Dean, Bruce H.↗
Data recording and processing for speckle image reconstruction
Image reconstruction from astronomical speckle data using the Knox-Thompson algorithm has now been extensively demonstrated as feasible through analysis and computer simulations. Experimental verification of the technique and its implementation for astronomy places stringent constraints on the recording system and requires complex processing algorithms to handle the many experimental details. In this paper we describe a video recording system specifically designed for the requirements of speckle imaging. This system has been built and tested, yielding high quality image reconstructions from a laboratory-atmospheric simulator for a wide range of input light levels and test objects.
Nisenson, P.↗
On the equivalence of Gaussian elimination and Gauss-Jordan reduction in solving linear equations
A novel general approach to round-off error analysis using the error complexity concepts is described. This is applied to the analysis of the Gaussian Elimination and Gauss-Jordan scheme for solving linear equations. The results show that the two algorithms are equivalent in terms of our error complexity measures. Thus the inherently parallel Gauss-Jordan scheme can be implemented with confidence if parallel computers are available.
Tsao, Nai-Kuan↗
Parallel algorithms for placement and routing in VLSI design
The computational requirements for high quality synthesis, analysis, and verification of very large scale integration (VLSI) designs have rapidly increased with the fast growing complexity of these designs. Research in the past has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. Two new parallel algorithms are proposed for two VLSI synthesis tasks, standard cell placement and global routing. The first algorithm, a parallel algorithm for global routing, uses hierarchical techniques to decompose the routing problem into independent routing subproblems that are solved in parallel. Results are then presented which compare the routing quality to the results of other published global routers and which evaluate the speedups attained. The second algorithm, a parallel algorithm for cell placement and global routing, hierarchically integrates a quadrisection placement algorithm, a bisection placement algorithm, and the previous global routing algorithm. Unique partitioning techniques are used to decompose the various stages of the algorithm into independent tasks which can be evaluated in parallel. Finally, results are presented which evaluate the various algorithm alternatives and compare the algorithm performance to other placement programs. Measurements are presented on the parallel speedups available.
Brouwer, Randall Jay↗
Monitoring and Acquisition Real-time System (MARS)
MARS is a graphical user interface (GUI) written in MATLAB and Java, allowing the user to configure and control the Scalable Parallel Architecture for Real-Time Acquisition and Analysis (SPARTAA) data acquisition system. SPARTAA not only acquires data, but also allows for complex algorithms to be applied to the acquired data in real time. The MARS client allows the user to set up and configure all settings regarding the data channels attached to the system, as well as have complete control over starting and stopping data acquisition. It provides a unique "Test" programming environment, allowing the user to create tests consisting of a series of alarms, each of which contains any number of data channels. Each alarm is configured with a particular algorithm, determining the type of processing that will be applied on each data channel and tested against a defined threshold. Tests can be uploaded to SPARTAA, thereby teaching it how to process the data. The uniqueness of MARS is in its capability to be adaptable easily to many test configurations. MARS sends and receives protocols via TCP/IP, which allows for quick integration into almost any test environment. The use of MATLAB and Java as the programming languages allows for developers to integrate the software across multiple operating platforms.
Holland, Corbin↗
Implementation and operation of three fractal measurement algorithms for analysis of remote-sensing data
Fractal geometry is increasingly becoming a useful tool for modeling natural phenomena. As an alternative to Euclidean concepts, fractals allow for a more accurate representation of the nature of complexity in natural boundaries and surfaces. The purpose of this paper is to introduce and implement three algorithms in C code for deriving fractal measurement from remotely sensed data. These three methods are: the line-divider method, the variogram method, and the triangular prism method. Remote-sensing data acquired by NASA's Calibrated Airborne Multispectral Scanner (CAMS) are used to compute the fractal dimension using each of the three methods. These data were obtained as a 30 m pixel spatial resolution over a portion of western Puerto Rico in January 1990. A description of the three methods, their implementation in PC-compatible environment, and some results of applying these algorithms to remotely sensed image data are presented.
Jaggi, S.↗
Review of LMIs, Interior Point Methods, Complexity Theory, and Robustness Analysis
From end of intro: ...We would like to show that for certain problems in systems and control theory, there exist algorithms for which corresponding (xi) can be viewed as a certain measure of robustness, e.g., stability margin.
control systems control system analysis↗
Algorithmic complexity
Quantitative measurements for algorithmic complexity of discrete function
DISCRETE FUNCTION↗
FLUT - A program for aeroelastic stability analysis
A computer program (FLUT) that can be used to evaluate the aeroelastic stability of aircraft structures in subsonic flow is described. The algorithm synthesizes data from a structural vibration analysis with an unsteady aerodynamics analysis and then performs a complex eigenvalue analysis to assess the system stability. The theoretical basis of the program is discussed with special emphasis placed on some innovative techniques which improve the efficiency of the analysis. User information needed to efficiently and successfully utilize the program is provided. In addition to identifying the required input, the flow of the program execution and some possible sources of difficulty are included. The use of the program is demonstrated with a listing of the input and output for a simple example.
Johnson, E. H.↗
Grasping with mechanical intelligence
Many robotic hands have been designed and a number have been built. Because of the difficulty of controlling and using complex hands, which usually have nine or more degrees of freedom, the simple one- or two-degree-of-freedom gripper is still the most common robotic end effector. A new category of device is presented: a medium-complexity end effector. With three to five degrees of freedom, such a tool is much easier to control and use, as well as more economical, compact and lightweight than complex hands. In order to increase the versatility, it was necessary to identify grasping primitives and to implement them in the mechanism. In addition, power and enveloping grasps are stressed over fingertip and precision grasps. The design is based upon analysis of object apprehension types, requisite characteristics for active sensing, and a determination of necessary environmental interactions. Contained are the general concepts necessary to the design of a medium-complexity end effector, an analysis of typical performance, and a computer simulation of a grasp planning algorithm specific to this type of mechanism. Finally, some details concerning the UPenn Hand-a tool designed for the research laboratory-are presented.
Ulrich, Nathan Thatcher↗
Overview of Sensitivity Analysis and Shape Optimization for Complex Aerodynamic Configurations
This paper presents a brief overview of some of the more recent advances in steady aerodynamic shape-design sensitivity analysis and optimization, based on advanced computational fluid dynamics (CFD). The focus here is on those methods particularly well-suited to the study of geometrically complex configurations and their potentially complex associated flow physics. When nonlinear state equations are considered in the optimization process, difficulties are found in the application of sensitivity analysis. Some techniques for circumventing such difficulties are currently being explored and are included here. Attention is directed to methods that utilize automatic differentiation to obtain aerodynamic sensitivity derivatives for both complex configurations and complex flow physics. Various examples of shape-design sensitivity analysis for unstructured-grid CFD algorithms are demonstrated for different formulations of the sensitivity equations. Finally, the use of advanced, unstructured-grid CFDs in multidisciplinary analyses and multidisciplinary sensitivity analyses within future optimization processes is recommended and encouraged.
Newman, James C., III↗
Electromagnetic Field Effects in Semiconductor Crystal Growth
This proposed two-year research project was to involve development of an analytical model, a numerical algorithm for its integration, and a software for the analysis of a solidification process under the influence of electric and magnetic fields in microgravity. Due to the complexity of the analytical model that was developed and its boundary conditions, only a preliminary version of the numerical algorithm was developed while the development of the software package was not completed.
Dulikravich, George S.↗
Spectral Range Within Global aCDOM(440) Algorithms for Oceanic, Coastal, and Inland Waters with Application to Airborne Measurements
The optically active component of dissolved organic material in aquatic ecosystems, or colored dissolved organic matter (CDOM), is represented by the coefficient of absorption due to the dissolved aquatic constituents at 440 nm, aCDOM(440). Remote sensing of aCDOM(440) enables characterization of ecosystem processes and aids in retrieval of chlorophyll a, a proxy for phytoplankton biomass. Spectrally adjacent band-ratio domains, e.g., blue to green, have previously been applied for remote sensing of aCDOM(440) in coastal and oceanic waters with similar results compared to more complex semi-analytical algorithms. Estimation of aCDOM(440) from ratios of the most spectrally separated ocean color wavebands (end members), e.g., ultraviolet (UV) to near-infrared (NIR), termed end-member analysis (EMA), has previously been shown to increase the accuracy of global aCDOM(440) retrievals from in-water observations of diffuse attenuation and to enable a unified algorithmic perspective without requiring regional adjustment of internal bio-optical parameters. EMA of above-water observations is evaluated herein, with a focus on coastal and inland waters in which increasing optical complexity and likelihood of bottom reflectance challenge the oceanic algorithms developed for deep and optically simple (case-1) waters. Analysis herein of three independent, in situ, bio-optical datasets indicates significant correlation between aCDOM(440) and end-member band ratios (next-generation 320 and 780 nm or legacy 412 and 670 nm ratios) with a coefficient of determination, R2, of 0.87 (log-scale) or higher based on a dataset spanning the dynamic range of global, conservative water bodies. For applicable wavelengths, EMA algorithms are shown to agree with case-1 relationships and to produce consistent log-scale uncertainties across more than three orders of magnitude in aCDOM(440) values (0.001–2.305 m1). EMA using UV and NIR wavelengths (320 and 780 nm) is applied to low-altitude airborne observations and satisfies 25% uncertainty based on unbiased percent differences (UPDs) within each of three dissimilar match-up sites ranging in aCDOM(440) from 0.02–0.57 m1. Results demonstrate that EMA is a useful and robust approach for the remote sensing of aCDOM(440) in coastal and inland waters, which are generally shallower, contain more optically complex environments, and span a greater range in aCDOM(440) than oceanic waters.
CDOM↗
Time Dependence of Collision Probabilities During Satellite Conjunctions
The NASA Conjunction Assessment Risk Analysis (CARA) team has recently implemented updated software to calculate the probability of collision (P (sub c)) for Earth-orbiting satellites. The algorithm can employ complex dynamical models for orbital motion, and account for the effects of non-linear trajectories as well as both position and velocity uncertainties. This “3D P (sub c)” method entails computing a 3-dimensional numerical integral for each estimated probability. Our analysis indicates that the 3D method provides several new insights over the traditional “2D P (sub c)” method, even when approximating the orbital motion using the relatively simple Keplerian two-body dynamical model. First, the formulation provides the means to estimate variations in the time derivative of the collision probability, or the probability rate, R (sub c). For close-proximity satellites, such as those orbiting in formations or clusters, R (sub c) variations can show multiple peaks that repeat or blend with one another, providing insight into the ongoing temporal distribution of risk. For single, isolated conjunctions, R (sub c) analysis provides the means to identify and bound the times of peak collision risk. Additionally, analysis of multiple actual archived conjunctions demonstrates that the commonly used “2D P (sub c)” approximation can occasionally provide inaccurate estimates. These include cases in which the 2D method yields negligibly small probabilities (e.g., P (sub c)) is greater than 10 (sup -10)), but the 3D estimates are sufficiently large to prompt increased monitoring or collision mitigation (e.g., P (sub c) is greater than or equal to 10 (sup -5)). Finally, the archive analysis indicates that a relatively efficient calculation can be used to identify which conjunctions will have negligibly small probabilities. This small-P (sub c) screening test can significantly speed the overall risk analysis computation for large numbers of conjunctions.
Hall, Doyle T.↗
MISR - A multiangle imaging spectroradiometer for geophysical and climatological research from EOS
The scientific objectives, instrument concept, and data plan for the multiangle imaging spectroradiometer (MISR), an experiment proposed for the EOS (Earth Observing System) mission, are described. MISR is a pushbroom imaging system designed to obtain continuous imagery of the sunlit Earth at four different view angles (25.8, 45.6, 60.0, and 72.5 deg relative to the vertical at the earth's surface), in both the forward and aftward directions relative to nadir, using eight separate cameras. Observations will be acquired in four spectral bands, centered at 440, 550, 670, and 860 nm. Data analysis algorithms will be applied to MISR imagery to retrieve the optical, geometric, and radiative properties of complex, three-dimensional scenes, such as aerosol-laden atmospheres above a heterogeneously reflecting surface, nonstratified cloud systems, and vegetation canopies. The MISR investigation will address a number of scientific questions concerning the climatic and ecological consequences of many natural and anthropogenic processes, and will furnish aerosol information necessary for atmospheric corrections of surface images.
Diner, David J.↗
Some easily analyzable convolutional codes
Convolutional codes have played and will play a key role in the downlink telemetry systems on many NASA deep-space probes, including Voyager, Magellan, and Galileo. One of the chief difficulties associated with the use of convolutional codes, however, is the notorious difficulty of analyzing them. Given a convolutional code as specified, say, by its generator polynomials, it is no easy matter to say how well that code will perform on a given noisy channel. The usual first step in such an analysis is to computer the code's free distance; this can be done with an algorithm whose complexity is exponential in the code's constraint length. The second step is often to calculate the transfer function in one, two, or three variables, or at least a few terms in its power series expansion. This step is quite hard, and for many codes of relatively short constraint lengths, it can be intractable. However, a large class of convolutional codes were discovered for which the free distance can be computed by inspection, and for which there is a closed-form expression for the three-variable transfer function. Although for large constraint lengths, these codes have relatively low rates, they are nevertheless interesting and potentially useful. Furthermore, the ideas developed here to analyze these specialized codes may well extend to a much larger class.
Mceliece, R.↗
Automatic Data Distribution for CFD Applications on Structured Grids
Data distribution is an important step in implementation of any parallel algorithm. The data distribution determines data traffic, utilization of the interconnection network and affects the overall code efficiency. In recent years a number data distribution methods have been developed and used in real programs for improving data traffic. We use some of the methods for translating data dependence and affinity relations into data distribution directives. We describe an automatic data alignment and placement tool (ADAPT) which implements these methods and show it results for some CFD codes (NPB and ARC3D). Algorithms for program analysis and derivation of data distribution implemented in ADAPT are efficient three pass algorithms. Most algorithms have linear complexity with the exception of some graph algorithms having complexity O(n(sup 4)) in the worst case.
Frumkin, Michael↗