Physical Sciences and Mathematics Commons^™

Upper Bounds To The Clique Width Of Graphs, Bruno Courcelle, Stephan Olariu

Computer Science Faculty Publications

Hierarchical decompositions of graphs are interesting for algorithmic purposes. Many NP complete problems have linear complexity on graphs with tree-decompositions of bounded width. We investigate alternate hierarchical decompositions that apply to wider classes of graphs and still enjoy good algorithmic properties. These decompositions are motivated and inspired by the study of vertex-replacement context-free graph grammars. The complexity measure of graphs associated with these decompositions is called clique width. In this paper we bound the clique width of a graph in terms of its tree width on the one hand, and of the clique width of its edge complement on …

Validation Of Algorithms For Remote Sensing Of Aerosols Over Land From The Eos Moderate Resolution Imaging Spectroradiometer (Modis), Anatoly Gitelson

Conservation and Survey Division: Faculty and Staff Publications

No abstract provided.

An Efficient Gps Position Determination Algorithm, Carlos R. Colon

Theses and Dissertations

The use of detect, or closed-form solutions of the trilateration equations used to obtain the position fix in GPS receivers is investigated. The paper is concerned with the development of an efficient new position determination algorithm that uses the closed-form solution of the trilateration equations and works in the presence of pseudorange measurement noise and for an arbitrary number of satellites. in addition, an initial position guess is not required and good estimation performance is achieved even under high GDOP conditions. A two step GPS position determination algorithm which 1) entails the solution of a linear regression problem and, 2) …

Some Studies On Shape Of Dot Patterns., Anirban Ray Chaudhuri Dr.

Doctoral Theses

The important visual characteristics of an object are shape, size, color, brightness, contrast and texture. Of them, shape is a multidimensional concept that is difficult to define. It takes different meanings in different contexts. We try to explain it in terms of their attributes like elongation, roundness, and symmetry: although these terms do not capture the complete notion of shape.Perhaps Gestalt theory Koffka 351 is the first attempt to study the principles of visual perception in a systematic manner. The central concept of this theory is Gestalt' which means form or configuration. In this theory form is examined from physical. …

Muyltivariate And Regression Analysis Based On The Geometry Of Data Clouds., Biman Chakraborty Dr.

Doctoral Theses

Median is a natural estimate of location of a data set, and there are several versions of inultivariate median studied in the literature, each of which is an interesting descriptive statistic for multivariate data and provides some nice geometric insights into the data cloud. One would expect that multidimensional median will be a natural estimate for the center of symmetry of a multivariate distribution. However, there is no unique concept of symmetry in multivariate problems. The center of symmetry can be defined in several ways there. For example, the d-dimensional random variable X is spherically symmetric about e €Rd if …

Neural Computation Of All Eigenpairs Of A Matrix With Real Eigenvalues, Serafim Theodore Perlepes

Theses Digitization Project

No abstract provided.

Even Subgraphs Of A Graph, Hong-Jian Lai, Zhi-Hong Chen

Scholarship and Professional Work - LAS

No abstract provided.

Nonlinear Constrained Optimizer And Parallel Processing For Golden Block Line Search, Duc T. Nguyen, Wilson H. Tang, Yeou K. Tung, Hakizumwami B. Runesha

Civil & Environmental Engineering Faculty Publications

Generalized exponential penalty functions are constructed for the multiplier methods in solving nonlinear programming problems. The non-smooth extreme constraint Gext is replaced by a single smooth constraint Gs by using the generalized exponential function (base a>1). The well-known K.S. function is found to be a special case of our proposed formulation. Parallel processing for Golden block line search algorithm is then summarized, which can also be integrated into our formulation. Both small and large-scale nonlinear programming problems (up to 2000 variables and 2000 nonlinear constraints) have been solved to validate the proposed algorithms.

Automatic Target Cueing Of Hyperspectral Image Data, Terry A. Wilson

Theses and Dissertations

Modern imaging sensors produce vast amounts data, overwhelming human analysts. One such sensor is the Airborne Visible and Infrared Imaging Spectrometer (AVIRIS) hyperspectral sensor. The AVIRIS sensor simultaneously collects data in 224 spectral bands that range from 0.4µm to 2.5µm in approximately 10nm increments, producing 224 images, each representing a single spectral band. Autonomous systems are required that can fuse "important" spectral bands and then classify regions of interest if all of this data is to be exploited. This dissertation presents a comprehensive solution that consists of a new physiologically motivated fusion algorithm and a novel Bayes optimal self-architecting classifier …

On The Developement Of An Optical Character Recognition(Ocr) System For Printed Bangla Script., Umapada Pal Dr.

Doctoral Theses

This thesis concerns OCR development of machine printed text in an Indian lan- guage, Bangla (Bengali) which is the fourthmost popular language in the world and the secondmost popular language in India.1.1 Optical Character Recognition Optical Character Recognition (OCR) is a process of automatic computer recog- nition of characters in optically scanned and digitized pages of text. OCR is ene of the most fascinating and challenging areas of pattern recognition with various practical applications. It can contribute tremendously to the advancement of an automation process and can improve the interface between man and machine in many applications, including office automation …

Representations, Approximations, And Algorithms For Mathematical Speech Processing, Laura R. Suzuki

Theses and Dissertations

Representing speech signals such that specific characteristics of speech are included is essential in many Air Force and DoD signal processing applications. A mathematical construct called a frame is presented which captures the important time-varying characteristic of speech. Roughly speaking, frames generalize the idea of an orthogonal basis in a Hilbert space, Specific spaces applicable to speech are L₂(R) and the Hardy spaces H_p(D) for p> 1 where D is the unit disk in the complex plane. Results are given for representations in the Hardy spaces involving Carleson's inequalities (and its extensions), …

New Algorithms For Moving-Bank Multiple Model Adaptive Estimation, Juan R. Vasquez

Theses and Dissertations

The focus of this research is to provide methods for generating precise parameter estimates in the face of potentially significant parameter variations such as system component failures. The standard Multiple Model Adaptive Estimation (MMAE) algorithm uses a bank of Kalman filters, each based on a different model of the system. A new moving-bank MMAE algorithm is developed based on exploitation of the density data available from the MMAE. The methods used to exploit this information include various measures of the density data and a decision-making logic used to move, expand, and contract the MMAE bank of filters. Parameter discretization within …

Analyzing Horizontal Distances Between Wsr-88d Thunderstorm Centroids And Cloud-To-Ground Lightning Strikes, Steve L. Renner

Theses and Dissertations

On April 29, 1996, lightning struck the airfield at Hurlburt Field, FL, killing one Airmen and injuring ten others. This cloud to ground lightning strike hit eight minutes after a lightning advisory was canceled. At the time of the strike, thunderstorms were observed 7 to 10 miles north and south of the airfield. The incident raised questions about Air Force Weather Agency's lightning criteria. Soon after the incident, a Lightning Safety Review Panel was assembled to determine the adequacy of lightning advisories. One of the questions posed to the panel was could an incident like Hurlburt happen again? The review …

A Validation Study Of The Air Force Weather Agency (Afwa) Jetrax Contrail Forecast Algorithm, Jeffrey D. Shull

Theses and Dissertations

Accurate contrail forecasts allow pilots to avoid levels of the atmosphere which are conducive to contrail formation, reducing their likelihood of being visually detected by enemy forces. The primary objective of this thesis is to evaluate the performance of the JETRAX contrail forecast algorithm currently used by the Air Force Weather Agency to support military air operations. A total of 397 ground-based contrail observations were collected at Wright-Patterson Air Force Base on 27 different days. Observations were collected with the aid of air traffic control radar, which greatly facilitated the positive identification of overflying aircraft and provided necessary information such …

Evaluation Of Satellite Microwave Derived Surface Temperature Algorithms For The Period August 1996 To February 1997, Charles H. Harris

Theses and Dissertations

The Air Force Weather Agency (AFWA) has two operational algorithms that derive surface temperatures from microwave observations taken by the Special Sensor Microwave Imager (SSM/I) which rides aboard space platforms of the Defense Meteorological Satellite Program (DMSP). The algorithm called Temperature from Satellite Microwave Imager (TS) is used to analyze global cloud coverage. The second algorithm is fittingly called Calibration and Validation (CV), as it was the algorithm used to calibrate and validate the first SSM/I in 1987. Multiple linear regression defined the algorithms from empirically gathered brightness temperatures and simultaneous surface temperatures. The key questions were how much data …

Azimuth And Range Optimization Of The Velocity Azimuth Display (Vad) Algorithm In The Wsr-88d, David L. Craft

Theses and Dissertations

The Velocity Azimuth Display (VAD) algorithm occasionally produces inaccurate wind estimates for the VAD Wind Profile (VWP) product of the Weather Surveillance Radar 1988 Doppler (WSR-88D) System. Weather forecasters have observed differences between the radar's wind profiles and wind profiles produced by rawinsondes and vertical wind profilers, when radiation and subsidence inversions in the atmosphere caused the radar beam to super refract. This thesis sought to improve the operational use of the VWP product for the WSR-88D near Denver, CO, by finding the optimal VAD algorithm Azimuth and Range parameter settings to overcome data contamination by hills located at the …

Improved Mathematical Modeling For Gps Based Navigation, Salvatore Nardi

Theses and Dissertations

This thesis is concerned with the development of new closed form GPS position determination algorithms that work in the presence of pseudorange measurement noise. The mathematical derivation of two closed form algorithms, based on stochastic modeling and estimation techniques, is presented. The algorithms provide an estimate of the GPS solution parameters (viz., the user position and the user clock bias) as well as the estimation error covariance. The experimental results are analyzed by comparison to the baseline results from the conventional Iterative Least Squares (ILS) algorithm. In typical GPS scenarios, the closed form algorithms are extremely sensitive to noise, making …

On Lipschitzian, And Connected Matrices In: Linear Complementarity Problem., Sriparna Bandyopadhyay Dr.

Doctoral Theses

This dissertation deals with a number of questions related to the linear complementarity problem (LCP). Given A ∈ Rn*n and q ∈ Rnthe LCP is to find a vector z ∈ R" such that Az+q ≥0,≥ and 2'(Az + 9) = 0. There is a vast literature on LCP developed during the last four decades. LCP plays a crucial role in the study of Mathematical Progranming from the point of view of algorithms as well as applications. The questions on existence and multiplicity of solutions in LCP has led researchers to introduce and study a variety of matrix classes. Most …

Optimal Contention-Free Unicast-Based Multicasting In Switch-Based Networks Of Workstations, Ran Libeskind-Hadas, Dominic Mazzoni '99, Ranjith Rajagopalan '99

All HMC Faculty Publications and Research

A unicast-based multicasting algorithm is presented for arbitrary interconnection networks arising in switch-based networks of workstations. The algorithm is optimal with respect tot he number of startups incurred and is provably free from depth contention. Specifically, no two constituent unicasts for the same multicast contend for a common channel, even if some unicasts are delayed due to unpredictable variations in latencies. The algorithm uses an underlying partially adaptive deadlock-free unicast routing algorithm. Simulation results indicate that the algorithm behaves as predicted by its theoretical properties and provides a promising approach to unicast-based multicasting.

Sorting In Parallel, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

In 1842, L.F. Menabrea anticipated the benefits of parallel computing in an article that appeared in the Swiss Journal Bibliotheque universelle de Geneve:

When a long series of identical computations is to be performed, such as those required for the formation of numerical tables, the machine can be brought into play so as to give several results at the same time, which will greatly abridge the whole amount of the processes.

Although more than a century passed before Menabrea's vision became a reality, today parallel computers with hundreds and even thousands of processors are used in a broad range …

Tree-Based Multicasting In Wormhole-Routed Irregular Topologies, Ran Libeskind-Hadas, Dominic Mazzoni '99, Ranjith Rajagopalan '99

All HMC Faculty Publications and Research

A deadlock-free tree-based multicast routing algorithm is presented for all direct networks, regardless of interconnection topology. The algorithm delivers a message to any number of destinations using only a single startup phase. In contrast to existing tree-based schemes, this algorithm applies to all interconnection topologies, requires only fixed-sized input buffers that are independent of maximum message length, and uses a single asynchronous flit replication mechanism. The theoretical basis of the technique used here is sufficiently general to develop other tree-based multicasting algorithms for regular and irregular topologies. Simulation results demonstrate that this tree-based algorithm provides a very promising means of …

Cell Size Dependence Of Transport Coefficients In Stochastic Particle Algorithms, Alejandro Garcia, F. Alexander, B. Alder

Faculty Publications

Using the Green–Kubo theory, the dependence of the viscosity and thermal conductivity on cell size is obtained explicitly for stochastic particle methods such as direct simulation Monte Carlo (DSMC) and its generalization, the consistent Boltzmann algorithm (CBA). These analytical results confirm empirical observations that significant errors occur when the cell dimensions are larger than a mean free path.

New Topologies And Parallel Algorithms For Static Interconnection Networks., Srabani Sen Gupta Dr.

Doctoral Theses

Many real-life applications in the areas of signal processing, image processing, etc., require a large amount of fast computations to be performed. Although high speed powerful processors are currently available due to the phenomenal advances in VLSI technology, the increasing demand for massive real-time computations can not be met just by a uniprocessor system. One way of achieving the goal of fast computation is through parallel processing. In parallel processing, a problem is broken into several subproblems, which are distributed among different processors so that each of the processors can perform its task simultaneously. Main areas of recent research in …

Concept Vectors: A Synthesis Of Concept Mapping And Matrices For Knowledge Representation In Intelligent Tutoring Systems, Mark L. Dyson

Theses and Dissertations

A review of the literature relating to intelligent tutoring systems (ITS) reveals that the bulk of research to date is focused on the student, and on methods for representing the knowledge itself. From student models to learning schemas to presentation methods, comparatively little attention has been paid to the problem of educators attempting to build viable lesson plans for use in an ITS environment--yet when this problem is addressed in the literature, it is recognized as a potentially daunting one. This thesis addresses the problem of ITS lesson plan development by proposing a practical, computable approach for knowledge engineering that …

Atmospheric Turbulence Scintillation Effects On Wavefront Tilt Estimation, James A. Louthain

Theses and Dissertations

A new atmospheric turbulence screen generator is developed for use in performance calculations of adaptive optics systems valid over a wide range of atmospheric turbulence parameters. The screen generator accounts for diffraction effects caused by weak turbulence and incorporates the phase, amplitude, and cross statistics of the perturbed optical field. The wavefront's phase and amplitude perturbations are taken from the correlation functions developed by Lee and Harp and the cross correlation of the phase and amplitude derived in this thesis. The screen generator uses a modal representation to perform a Fourier series expansion of the wavefront phase and amplitude over …

Displacement Of The Earth's Bow Shock And Magnetopause Due To An Impinging Interplanetary Shock Wave, William A. Olson

Theses and Dissertations

Interplanetary shock waves (ISWs) propagating through the solar wind can collide with the earth's bow shock, resulting in a series of new shocks, contact discontinuities, and rarefaction waves which interact to effectively move the bow shock and magnetopause toward the earth. A one dimensional MacCormack predictor corrector algorithm with Flux Corrected Transport (FCT) was developed to model the ISW bow shock and magnetopause interactions, and to numerically predict their propagation speeds after collision. Analytic relationships for the Mach numbers and propagation speeds of the generated shock waves and contact discontinuities were used to validate the model and to compare numerical …

Modeling And Simulation Support For Parallel Algorithms In A High-Speed Network, Dustin E. Yates

Theses and Dissertations

This thesis investigates the ability of a simulation model to compare and contrast parallel processing algorithms in a high-speed network. The model extends existing modeling, analysis, and comparison of parallel algorithms by providing graphics based components that facilitate the measurement of system resources. Simulation components are based on the Myrinet local area network standard. The models provide seven different topologies to contrast the performance of five variations of Fast Fourier Transform (FFT) algorithms. Furthermore, the models were implemented using a commercially developed product that facilitates the testing of additional topologies and the investigation of hardware variations. Accurate comparisons are statistically …

Applications Of Unsupervised Clustering Algorithms To Aircraft Identification Using High Range Resolution Radar, Dzung Tri Pham

Theses and Dissertations

Identification of aircraft from high range resolution (HRR) radar range profiles requires a database of information capturing the variability of the individual range profiles as a function of viewing aspect. This database can be a collection of individual signatures or a collection of average signatures distributed over the region of viewing aspect of interest. An efficient database is one which captures the intrinsic variability of the HRR signatures without either excessive redundancy typical of single-signature databases, or without the loss of information common when averaging arbitrary groups of signatures. The identification of 'natural' clustering of similar HRR signatures provides a …

A Single Chip Low Power Implementation Of An Asynchronous Fft Algorithm For Space Applications, Bruce W. Hunt

Theses and Dissertations

A fully asynchronous fixed point FFT processor is introduced for low power space applications. The architecture is based on an algorithm developed by Suter and Stevens specifically for a low power implementation. The novelty of this architecture lies in its high localization of components and pipelining with no need to share a global memory. High throughput is attained using large numbers of small, local components working in parallel. A derivation of the algorithm from the discrete Fourier transform is presented followed by a discussion of circuit design parameters specifically, those relevant to space applications. The generic architecture is explained with …

On Cvt Minimization In Single Machine Scheduling., D. K. Manna Dr.

Doctoral Theses

Scheduling problens are quite common in real life. They arise whenever there is a need to plan execution of various tasks over time and therefore they play very important roles in commercial set-ups concerning manufacturing or service in the optimal use of resources and/or customers satisfaction. The theory of scheduling deals with the construction of suitable models and their analyses. Researchersattention was drawn to the study of scheduling problems using mathematical modeling, probably for the first time when Johnson (1954] published his famous work on flowshop problem. Since then, the study of scheduling problem and its context has gradually attracted …