Digital Commons Network^™

An Efficient Multicomputer Algorithm For The Solution Of Chemical Process Flowsheeting Equations, Fikret Ercal, Neil L. Book, S. Pait, J. J. Fielding

Computer Science Faculty Research & Creative Works

This paper presents a parallel solution method of large sparse systems of linear equations arising in the context of a chemical process flowsheeting application on a message passing multicomputer. To maximize the performance, the algorithm uses a novel matrix decomposition and solution method, called parallel two-phased LU decomposition, which schedules the concurrent tasks in a maximally overlapping manner, and at the same time, tries to minimize the interprocessor data dependencies and obtain optimal load balancing. The forward elimination step is performed concurrently with the parallel two-phased LU decomposition step and backward substitution is parallelized in a piecewise manner. Implementation results …

Feasible Offset And Optimal Offset For General Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

This paper provides an efficient method to find all feasible offsets for a given separation in a very large-scale integration (VLSI) channel-routing problem in one layer. The previous literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from $\Theta ( n )$ to $\Omega ( n^2 )$, where n is the number of nets. But if the number of columns c is $O( n )$, the problem can be solved in time $O( n^{1.5} \lg n )$, which improves upon a “naive” $O( cn )$ approach. As a …

Relaxing Synchronization In Distributed Simulated Annealing, Bruce M. Mcmillin, Chul-Eui Hong

Computer Science Faculty Research & Creative Works

This paper presents a cost error measurement scheme and relaxed synchronization method, for simulated annealing on a distributed memory multicomputer, which predicts the amount of cost error that an algorithm will tolerate. An adaptive error control method is developed and implemented on an Intel iPSC/2

Automatic Pcb Inspection Systems, M. Moganti, Fikret Erçal

Computer Science Faculty Research & Creative Works

There are more than 50 process steps required to fabricate a printed circuit board (PCB). To ensure quality, human operators simply inspect the work visually against prescribed standards. The decisions made by this labor intensive, and therefore costly, procedure often also involve subjective judgements. Automatic inspection systems remove the subjective aspects and provide fast, quantitative dimensional assessments. Machine vision may answer the manufacturing industry's need to improve product quality and increase productivity. The major limitation of existing inspection systems is that all the algorithms need a special hardware platform to achieve the desired real-time speeds. This makes the systems extremely …

A Trainable, Single-Pass Algorithm For Column Segmentation, Son Sylwester, Sharad C. Seth

School of Computing: Conference and Workshop Papers

Column Segmentation logically precedes OCR in the document analysis process. The trainable algorithm described here, XYCUT, relies on horizontal and vertical binary profiles to produce an XY- tree representing the column structure of a page of a technical document in a single pass through the bit image. Training against ground truth adjusts a single, resolution independent, parameter using only local information and guided by an edit distance function. The algorithm correctly segments the page image for a (fairly) wide range of parameter values, although small, local and repairable errors may be made, an effect measured by a repair cost function.

Quantitative Object Motion Prediction By An Art2 And Madaline Combined Neural Network: Concepts And Experiments, Qiuming Zhu, Ahmed Y. Tawfik

Computer Science Faculty Publications

An ART2 and a Madaline combined neural network is applied to predicting object motions in dynamic environments. The ART2 network extracts a set of coherent patterns of the object motion by its self-organizing and unsupervised learning features. The identified patterns are directed to the Madaline network to generate a quantitative prediction of the future motion states. The method does not require any presumption of the mathematical models, and is applicable to a variety of situations.

Towards An Ontology Of Problems, Martin Zwick

Complex Systems Faculty Publications and Presentations

Systems theory offers a language in which one might formulate a metaphysics (or more specifically an ontology) of problems. This proposal is based upon a conception of systems theory shared by von Bertalanffy, Wiener, Boulding, Rapoport, Ashby, Klir, and others, and expressed succinctly by Bunge, who considered game theory, information theory, feedback control theory, and the like to be attempts to construct an "exact and scientific metaphysics." Our prevailing conceptions of "problems" are concretized yet also fragmented and in fact dissolved by the standard reductionist model of science, which cannot provide a general framework for analysis. The idea of a …

Interaction And Interdependency Of Software Engineering Methods And Visual Programming, Robert A. Touchton

UNF Graduate Theses and Dissertations

Visual Programming Languages and Visual Programming Tools incorporate non-procedural coding mechanisms that may duplicate, or perhaps even conflict with, the analysis and design mechanisms promulgated by the mainstream Software Engineering methodologies. By better understanding such duplication and conflict, software engineers can take proactive measures to accommodate and, ideally, eliminate them. Better still, there may be opportunities for synergy that can be exploited if one is looking for them.

This research explored, documented and classified the interactions and interdependencies, both positive (synergies) and negative (conflicts), between two closely related and rapidly evolving Computer Science subdisciplines: software engineering and visual programming. A …

A Study Of Voluntary Participation In Computer User Groups, Alan Engels

Electronic Theses & Dissertations

The purpose of this study was to determine ways to increase participation of members in Computer User Groups. The problem addressed was that a small select group, less than ten percent, in the Parsons Apple/Macintosh Users Group was doing ninety-five percent or more of the work. If this scenario does not change soon, the overworked and overburdened select few may suffer burnout and quit. Case in point, Joplin, MO, had a large Computer User Group, but about seven years ago, it vanished when the select few refused to serve anymore. The same process of decay and erosion has happened in …

Production Of Excited Beauty States In Z Decays, D. Buskulic, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

A data sample of about 3.0 million hadronic Z decays collected by the ALEPH experiment at LEP in the years 1991 through 1994, is used to make an inclusive selection of B hadron events.

Adaptive Resonance Associative Map, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

This article introduces a neural architecture termed Adaptive Resonance Associative Map (ARAM) that extends unsupervised Adaptive Resonance Theory (ART) systems for rapid, yet stable, heteroassociative learning. ARAM can be visualized as two overlapping ART networks sharing a single category field. Although ARAM is simpler in architecture than another class of supervised ART models known as ARTMAP, it produces classification performance equivalent to that of ARTMAP. As ARAM network structure and operations are symmetrical, associative recall can be performed in both directions. With maximal vigilance settings, ARAM encodes pattern pairs explicitly as cognitive chunks and thus guarantees perfect storage and recall …

Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This paper provides a new approach to labeling the connected components of an n x n image on a scan line array processor (comprised of n processing elements). Variations of this approach yield an algorithm guaranteed to complete in o(n lg n) time as well as algorithms likely to approach O(n) time for all or most images. The best previous solutions require using a more complicated architecture or require Omega(n lg n) time. We also show that on a restricted version of the architecture, any algorithm requires Omega(n lg n) time in the worst case.

A Proposal For A Development Platform For Microcontroller-Based Devices, Michael L. Wetton

Theses: Doctorates and Masters

This thesis is concerned with designing, implementing and testing a miniaturised temperature data logging device. Investigations demonstrated that a microcontroller could provide a low-cost single-chip solution to this problem and after a detailed review of 8-bit microcontrollers, the MC68HCll was chosen for this task. This document also includes discussion on an environment that was developed for creating and testing MC68HC11 software and the use of Motorola's evaluation boards. To ensure that the device was designed to software engineering standards an investigation into software engineering analysis techniques took place. This resulted in the Jackson Structured Programming (JSP) methodology being adapted to …

Rule Extraction: From Neural Architecture To Symbolic Representation, Gail A. Carpenter, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

This paper shows how knowledge, in the form of fuzzy rules, can be derived from a supervised learning neural network called fuzzy ARTMAP. Rule extraction proceeds in two stages: pruning, which simplifies the network structure by removing excessive recognition categories and weights; and quantization of continuous learned weights, which allows the final system state to be translated into a usable set of descriptive rules. Three benchmark studies illustrate the rule extraction methods: (1) Pima Indian diabetes diagnosis, (2) mushroom classification and (3) DNA promoter recognition. Fuzzy ARTMAP and ART-EMAP are compared with the ADAP algorithm, the k nearest neighbor system, …

First Measurement Of The Quark-To-Photon Fragmentation Function, D. Buskulic, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

Earlier measurements at LEP of isolated hard photons in hadronic Z decays, attributed to radiation from primary quark pairs, have been extended in the ALEPH experiment to include hard photon production inside hadron jets. Events are selected where all particles combine democratically to form hadron jets, one of which contains a photon with a fractional energy z 0:7. After statistical subtraction of non-prompt photons, the quark-to-photon fragmentation function, D(z), is extracted directly from the measured 2-jet rate. By taking into account the perturbative contributions to D(z) obtained from an O(S ) QCD calculation, the unknown non-perturbative component of D(z) is …

Inclusive Production Of Neutral Vector Mesons In Hadronic Z Decays, D. Buskulic, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

Data on the inclusive production of the neutral vector mesonsρ 0(770),ω(782), K*0(892), andφ(1020) in hadronic Z decays recorded with the ALEPH detector at LEP are presented and compared to Monte Carlo model predictions. Bose-Einstein effects are found to be important in extracting a reliable value for theρ 0 production rate. An averageρ 0 multiplicity of 1.45±0.21 per event is obtained. Theω is detected via its three pion decay modeω→π + π − π 0 and has a total rate of 1.07±0.14 per event. The multiplicity of the K*0 is 0.83±0.09, whilst that of theφ is 0.122±0.009, both measured using their …

Improved Tau Polarisation Measurement, D. Buskulic, M. Thulasidas

Research Collection School Of Computing and Information Systems

Using 22 pb−1 of data collected at LEP in 1992 on the peak of the Z resonance, the ALEPH collaboration has measured the polarisation of the tau leptons decaying intoevv¯,μvv¯evv¯,μvv¯,πν, ρν and a1 ν from their individual decay product distributions. The measurement of the tau polarisation as a function of the production polar angle yields the two parametersN τ andN e, where, in terms of the axial and vector couplingsg Al andg Vl,N l=2g Vl gAl/(g 2Vl+g2Al). This analysis follows to a large extent the methods devised for the 1990 and 1991 data but with improvements which bring a better …

Multiple Query Optimization With Depth-First Branch-And-Bound And Dynamic Query Ordering, Ee Peng Lim, Ahmet Cosar, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., usually a single query gets transformed into a set of closely related database queries. Also, great benefits can be obtained by executing a group of related queries all together in a single unified multi-plan instead of executing each query separately. In order to achieve this Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subexpressions, joins, etc.) among a set of query plans and creates a single unified plan (multi-plan) which can be executed to obtain the required outputs for all queries at once. …

Computing Χ² Values, John F. Dooley, Daniel C. St Clair, William E. Bond

Mathematics and Statistics Faculty Research & Creative Works

Textbooks and courses on numerical algorithms contain numerous examples which lead students to believe that the algorithm of choice for computing the zeros of a function f1994 is Newton's algorithm. In many of these courses little or no time is spent in providing students with "real world" experiences where Newton's method fails. The work presented in this paper describes a slow convergence problem encountered while trying to use Newton to estimate values for the 2 distributions. The problem occurred while the authors were trying to implement a well-known machine learning algorithm from the field of artificial intelligence. The function being …

Program Modeling And Control Synthesis For Robotic Manipulators, Ramiz N. Ballou, Arlan R. Dekock, David D. Ardayfio

Computer Science Technical Reports

The control and programming methodology of industrial robots is becoming increasingly important. The speed and accuracy of data generation, and the performance of the robot are considered the most important factors in robotics control. This paper presents and discusses algorithms that solve for the inverse solution for a given point in space at a very high speed based on the top down abstract method. The algorithms are independent of any specific type of manipulator configuration or programming language. The algorithms were implemented for the IBM-PC™ using the FORTRAN language to control the Armdroid™ robot. The program generates 500 sets of …

Topologies Invariant Under A Group Action, Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

We study links between faithful group actions on a set and topologies on that set. In one direction, a group action has its invariant topologies (so we may regard members of the action to be homeomorphisms relative to those topologies); in the other direction, a topology has its preserving group actions (i.e., the subgroups of the homeomorphism group of the topology). This two-way passage allows us to discuss topological features of group actions as well as symmetry features of topologies.

Analytic Performance Models For Parallel Discrete Event Battlefield Simulation With Conservative Synchronization, James B. Hiller

Theses and Dissertations

This study investigated the development and use of analytic models for performance analysis of parallel discrete event battlefield simulation using conservative synchronization. A simulation architecture with layered application, simulation, and host machine services provided the model development basis. Simulation entities were modeled with set-theoretic definitions. Deterministic performance models using these definitions were developed for event prediction, scheduling, and execution in sequential battlefield simulation. The sequential model was expanded to include relative bounds for overhead factors introduced when the simulation is spatially decomposed for a parallel distributed memory machine. Comparison of sequential and parallel models instantiated for a simulation with uniform …

Multiple Model Adaptive Estimation And Head Motion Tracking In A Virtual Environment: An Engineering Approach, James E. Russell

Theses and Dissertations

Software engineering tools and techniques were applied to design and implement an application that reduces lag typically present in virtual environment displays. The application was a Multiple Model Adaptive Estimator (MMAE), composed of three Kalman filters, that predicted head orientation one sample period into the future. The environment rendering software used these predictions to generate the environment display. Each of the filters in the MMAE was designed for a different assumed head motion type (benign, moderate, or heavy), which allowed the MMAE to adapt to changes in head movement characteristics. The use of Ada 9X as an implementation language for …

Factors In Human-Computer Interface Design (A Pilot Study), Susan Stewart

Theses and Dissertations

The DoD has budgeted over $9.8 billion for 1995 for information technology, yet many government office workers let their existing systems sit idle. This thesis explores why these computers are sitting idle. This researcher's initial hypothesis was that certain features of the human-computer interface can positively or negatively affect efficiency, retention, and satisfaction level of workers. Although some research is being done in this area, interfaces continue to be of poor quality, especially in the DoD, where long procurement cycles, forced purchases, and limited budgets result in out-of-date software. Intuitively most programmers know the human-computer interface impacts on a person's …

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This paper shows that a fat-pyramid of area Θ(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more and more …

Knowledge-Based Safety Training System (Kbsts): A Prototype Implementation, Venky Shankararaman, B. S. Lee

Research Collection School Of Computing and Information Systems

A computer-based safety training system for process operators must be able to make effective presentation of textual material, test the trainee's understanding through quizzes and facilitate plant simulation. The general framework of such a system is presented in an earlier paper (Computers in Industry, Vol. 17, 1991, pp. 349–358). In this paper, we discuss the development and implementation of a prototype Knowledge-Based Safety Training System based on the framework. The design philosophy, system architecture and the plant modelling methodology are described.

Semantics Vs. Syntax Vs. Computations Machine Models For Type-2 Polynomial-Time Bounded Functionals (Preliminary Draft), James S. Royer

Electrical Engineering and Computer Science - Technical Reports

This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theorem in the context of the type-2 basic feasible functionals, a.k.a. the Mehlhorn-Cook class of type-2 polynomial-time functionals. We develop a direct, polynomial-time analog of effective operation, where the time bound on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that (i) if P = NP, these polynomial-time effective operations are strictly more powerful on R (the class of recursive functions) than the basic feasible functions, and (ii) there is an oracle relative to which these polynomial-time effective operations and the basic feasible functionals have the …

1.1, Yolanda Jones

E-lert

No abstract provided.

Disk-Directed I/O For Mimd Multiprocessors, David Kotz

Computer Science Technical Reports

Many scientific applications that run on today's multiprocessors are bottlenecked by their file I/O needs. Even if the multiprocessor is configured with sufficient I/O hardware, the file-system software often fails to provide the available bandwidth to the application. Although libraries and improved file-system interfaces can make a significant improvement, we believe that fundamental changes are needed in the file-server software. We propose a new technique, disk-directed I/O, that flips the usual relationship between server and client to allow the disks (actually, disk servers) to determine the flow of data for maximum performance. Our simulations show that tremendous performance gains are …

Multimedia Authoring, Development Environments, And Digital Video Editing, Fillia Makedon, James W. Matthews, Charles B. Owen, Samuel A. Rebelsky

Dartmouth Scholarship

Multimedia systems integrate text, audio, video, graphics, and other media and allow them to be utilized in a combined and interactive manner. Using this exciting and rapidly developing technology, multimedia applications can provide extensive benefits in a variety of arenas, including research, education, medicine, and commerce. While there are many commercial multimedia development packages, the easy and fast creation of a useful, full-featured multimedia document is not yet a straightforward task.

This paper addresses issues in the development of multimedia documents, ranging from user-interface tools that manipulate multimedia documents to multimedia communication technologies such as compression, digital video editing and …