Mathematics, Computer Science and Statistics.

Chair: Andrew Harrell, CEWES-GM

THURSDAY MORNING

Magnolia A

8:45 Divisional Poster Session

THE SATELLITE LIST AND K-LEVEL SATELLITE TREE: NEW DATA STRUCTURES USEFUL FOR FINDING HAMIL TONIAN CYCLES

Colin Osterman* and Cesar Rego, University of Mississippi, University, MS 38677

We propose new data structures--the Satellite List and k-Level Satellite Tree--for representing paths and cycles with a discussion of properties in the framework of general graph operations. We show that the k-Level Satellite Tree is far more efficient than its predecessors.

Oral presentations begin

9:20 GENERATING MOLECULAR GRAPHS FOR PREDICTIVE CHEMISTRY

Laura Sheppardson, University of Mississippi, University, MS 38677

Graph theoretical methods have long been used to enumerate the isomers of organic compounds. There are few practical tools, however, for generating a listing of all isomers with a specific chemical formula. This talk will discuss a current project to develop such a generator. The graphs produced may be considered potential reaction products, and used to guide searches for novel chemical reactions. We first examine the difficulties of exhaustive, non-redundant graph generation, and then discuss several methods which have been successfully applied to overcome these difficulties. Most generators developed to date have imposed specific limitations on graph properties (e.g., planarity, regularity) to control the number of graphs considered. We address the general case, and describe an algebraic method which can be employed to avoid redundancies.

10:00 Break

10:20 A NEW RAMP ALGORITHM FOR THE CAPACITATED MINIMUM SPANNING TREE PROBLEM

Frank Mathew (1*), Cesar Rego (1), and Fred Glover (2), (1) University of Mississippi, University, MS 38677 and (2) University of Colorado, Boulder, CO 80309

The capacitated minimum spanning tree (CMST) problem is fundamental to the design of communication networks, and has been widely studied for its importance in practical applications. Nevertheless, the best methods to date still have difficulty finding solutions of highest quality. We show how a variant of the Relaxation Adaptive Memory Programming (RAMP) method succeeds in solving the CMST effectively. The RAMP approach is a relatively new metaheuristic procedure that takes advantage of primal and dual relationships and adaptive memory programming derived from tabu search. In this research we implemented a version of the RAMP approach that uses surrogate constraint relaxations and adaptive memory to create and project dual solutions onto the primal feasible space. Computational results on a classical set of benchmark instances indicate that even a simple version of the RAMP approach advantageously compares with current state-of-the-art algorithms for the CMST problem. We also sketch how more advanced RAMP strategies can be employed to achieve further enhancements.

10:40 A SIMPLE RAMP ALGORITHM FOR THE SET COVERING PROBLEM

Jose H. Ablanedo* and Cesar Rego, University of Mississippi, University, MS 38677

The Set Covering Problem (SCP) is a classical combinatorial problem used to model a wide range of applications such as airline and railway crew scheduling, political districting, and truck routing, just to cite a few. The problem is NP-Hard and therefore heuristic algorithms are required to solve large scale instances such those commonly arising in real world applications. We present a new algorithm for the SCP based on a relatively simple RAMP approach that combines surrogate constraints relaxation with tabu search. Computational results carried out on a standard set of benchmark problems indicate that the proposed algorithm is competitive with the best and suggest the use of more advanced RAMP strategies to achieve better performance.

THURSDAY AFTERNOON

Magnolia A

1:40 PATTERN RECOGNITION SOFTWARE TOOL DEVELOPED FOR THE CLASSIFICATION OF REMOTE SENSING SPECTRAL REFLECTANCE DATA

Abdullah Faruque (1*), Raj Bahadur (2), and Gregory A. Carter (3), (1) Southern Polytechnic State University, Marietta, GA 30060; (2) Mississippi Valley State University, Itta Bena, MS 38941; (3) Gulf Coast Research Laboratory, Ocean Springs, MS 39566

This paper describes the development and implementation of LIP (Leaf Identification Program), a pattern recognition software tool intended to classify remote sensing spectral reflectance data of stressed soybean leaves by using neural network and other statistical pattern recognition techniques. The development of this software tool takes advantage of the high performance computational and visualization routines of the MATLAB programming environment. LIP provides an integrated environment for various data analysis, data visualization and pattern recognition techniques to analyze remote sensing spectral reflectance data. Data analysis component of LIP includes: principal component analysis, fisher and variance weight calculations and feature selection. Data visualization tool permits visual assessment of the spectral reflectance data patterns and their relationships. Several classification methods have been implemented in LIP using both neural network and statistical pattern recognition techniques. Neural network methods include the back propagation neural network (BPN) and radial basis function (RBF) neural network. Statistical pattern recognition component of LIP includes linear discriminant analysis (LDA), quadratic discriminant analysis (QDA), regularized discriminant analysis (RDA), soft independent modeling of class analogy (SIMCA) and discriminant analysis with shrunken covariance (DASCO). The objective of this study funded by National Aeronautics Space Administration (NASA) at Stennis Space Center was to record and classify the spectral reflectance differences of leaf stress caused by drought, fungal disease, and lead contamination of the soil. LIP software tool has been used successfully to classify the different classes of stressed leaves from their spectral signature.

2:00 A MATRIX EIGENVALUE APPROACH TO TEAM RANKINGS

Kendrick Savage* and James Reed, University of Mississippi, University, MS 38677

A fundamental problem in ranking sports teams is the incomplete nature of most competitions where some teams play each other and some do not. It is challenging to compare teams that do not play each other. An example of this phenomenon is the controversy surrounding the selection of the 2003 NCAA Division 1 Football Champion. Both Louisiana State University and the University of Southern California were named champions by different polls. A reason for the uncertainty as to which of these teams should be higher ranked is the fact that they did not play each other. In fact most of the NCAA Division 1 teams do not play each other as there were 117 such teams in 2003 but each team played roughly 12 games. Hence each team only plays roughly 10% of all the other Division 1 teams. This situation is analogous to the problem of ranking web pages where some pages are linked to each other but the vast majority of web pages are not. The internet search engine Google assigns a rank to each web page called the pages "pagerank". The method Google uses is to model the importance of a particular page relative to the importance of pages that are linked to this particular page. The ranking vector of all web pages is an eigenvector of a matrix. Motivated by the success of the Google pagerank ranking scheme, we apply a similar ranking scheme based on eigenvectors to the 2003 NCAA Division 1 Football Season. We will find the Division 1 School with the largest ranking in the real positive eigenvector of largest modulus. The results of this research will have applications to practical personnel assignment problems. The incomplete information available is the common difficulty of each of these problems: ranking web pages, ranking sports teams, matching job applicants to positions.

2:20 Divisional Business Meeting

FRIDAY MORNING

Magnolia A

Special Subsession on Supercomputing and Concurrent Poster Session

8:00 ADDRESSING INSTALLATION AND CONFIGURATION ISSUES IN A COMPUTATIONAL RESEARCH GRID AT THE MISSISSIPPI CENTER FOR SUPERCOMPUTING RESEARCH

Tyler A. Simon*, Jason Hale, and Taner Pirim, University of Mississippi, University, MS 38677

The nature of GRID computing enables one to harness the resources of remote, heterogeneous computers over potentially wide geographic areas to accomplish computationally intensive tasks. Our testing environment is composed of a RedHat Linux cluster, a SuSE Linux symmetric multiprocessor and an Onyx 10000 Supercomputer running Irix 6.5. Our GRID is constructed using a layered services architecture that uses the Globus Toolkit for Application management, and the Java programming language for application development, and OpenSSL as our persistent inter-node security protocol. To test the system we run MPI jobs that traditionally run on clusters and symmetric multiprocessors. The benefits of this project aim at enabling the researchers of the state of Mississippi with high performance, real time collaboration, as well as letting them take advantage of the emerging technologies that support a GRID computing environment.

8:10 A CUSTOM MULTIHOMED NETWORK TOPOLOGY FOR CLUSTER LOAD BALANCING

Tyler A. Simon, University of Mississippi, University, MS 38677

The current network topology of the Beowulf Linux cluster at the Mississippi Center for Supercomputing Research is composed of a single high bandwidth interconnection ring that facilitates both inter-node communication and disk access. As our production environment has demonstrated, a single thread connecting hundreds of machines can become saturated as processor demands and file I/O increase, leading to reduced overall system performance. We address this single point of contention by distributing interprocess communication and file access over separate network interfaces, and therefore through separate switches. Positive results from these tests involve a reduction in total execution time for a particularly common job requiring consistent disk access and interprocess communication. The goal of this work is to able to increase cluster performance using a custom low cost load balancing mechanism, that may be applied to a common design problem in ring topologies to increase overall cluster performance.

8:25 AN EXPANDED DYNAMIC LOAD BALANCING TECHNIQUE FOR OVERCOMING CLUSTER NODE FAILURES USING MPI

Jason Hale* and Jie Tang, University of Mississippi, Oxford, MS 38677

The goal of shared memory parallel computers and distributed memory compute clusters is to increase the performance of computations over what is possible on single-CPU systems. MPI is a widely used message passing interface for parallelizing computations on distributed memory architectures, such as Beowulf clusters. One of the strategies in optimizing parallel performance is keeping as many available processors/nodes as possible productive at all times. In problems where the work is not clearly divisible by the number of processors available, many processors may sit idle after completing their subtasks, while one or few processors solve the remainder of the problem. In heterogeneous computer clusters, processors of differing speeds may be allocated to the problem, further complicating the task of equally distributing load to maximize performance. Furthermore, if one node of a cluster fails, it can often be rebooted, repaired, or replaced without affecting the rest of the cluster, but parallel computations that were using that node often fail to complete satisfactorily, yet may linger hopelessly in a defunct state, tying up scarce resources and delaying other jobs. Once the doomed job is finally detected and deleted, the user may have to resubmit the job, and wait hours or days before the resubmitted job accumulates enough resources privileges to try to run again. Well-known techniques allow the programmer to anticipate work inequities and write programs that attempt to carve up and dynamically distribute remaining work among available processors. We propose an expanded load balancing technique to allow the original program to save valuable time by surviving the failure of a node, and explore the technique on the Mimosa Intel cluster at the Mississippi Center for Supercomputing Research (MCSR).

8:45 THE PERFORMANCE ANALYSIS OF HIGH PERFORMANCE LINPACK BENCHMARKS ON ALTIX 3700 AND BEOWULF LINUX CLUSTER

Taner Pirim, University of Mississippi, University, MS 38677

The Mississippi Center for Supercomputing Research, MCSR, has recently increased the capacity of its resources by adding a new supercomputer to its High Performance Computing, HPC, lineup, which is acquired in July 2004 and put into production in August 2004. Named "redwood," the new SGI Model 3700 Altix high performance compute server with 64 Itanium2 processors, 64 Gigabytes memory, and 2.336 Terabytes fiber channel disk system serves as a capability resource for researchers who have particularly high performance codes and calculations that cannot be run efficiently on other MCSR supercomputers or clusters. This study presents the high performance linpack benchmark, HPL, analyses of the new SGI Altix 3700 as well as the Mimosa Beowulf Linux Cluster with various configurations such as idle, non-idle situations and different network speeds. It also compares the results obtained from both systems. Furthermore, we outline the importance of running such tests as a method for obtaining reliable processing capability for multi-node supercomputing applications. Thorough analyses of the benchmark results have helped the center to distinguish the performance differences between two systems, numerically. The analysis also has proven to be an integral and necessary step toward system optimization and increased overall performance for the researchers in the state of Mississippi.

9:05 MISSISSIPPI CENTER FOR SUPERCOMPUTING RESEARCH (MCSR) USER ADVISORY GROUP MEETING, POSTER SESSION, AND SPECIAL SUBSESSION ON SUPERCOMPUTING

David G. Roach, University of Mississippi, University, MS 38677

The Mississippi Center for Supercomputing Research was established in 1987 by the Mississippi Legislature and the Institutions of Higher Learning (IHL) in order to provide high performance supercomputing (HPC) support for research and instruction at all state universities. The Mississippi Supercomputer User Advisory Committee (MSUAG) was established by the IHL Research Consortium to provide user input and advice to MCSR management and technical staff on policies and procedures for the Center's operations. It includes member representatives from all IHL institutions. The Advisory Group will meet at this MAS conference. Mr. David G. Roach, Director of the MCSR, will conduct the meeting. The agenda includes an update on MCSR HPC facilities and services, introduction of new MCSR staff members, and site reports and ongoing research updates by MSUAG representatives. A poster session, showcasing research projects that utilize MCSR facilities and services, will follow the Advisory Group Meeting. A Special HPC Subsession of the Mathematics, Computer Science and Statistics Division, sponsored by the MCSR, will also be held to serve as a forum on supercomputing in which faculty and graduate student researchers will have the opportunity to describe their research projects that involve HPC, Internet2, Grid Computing, Visualization, Network Security, Computer Systems Administration, and the use of MCSR resources. IHL faculty and graduate students, with an interest in HPC and/or MCSR facilities and services, are also invited to attend and participate.

9:20 Break

Regular Session Resumes

9:40 EVALUATING COMPUTATIONAL CHEMISTRY APPLICATIONS ON PARALLEL COMPUTING PLATFORM

Haibo Wang, University of Mississippi, University, MS 38677

Many computational chemistry applications have studied by means of different types of parallel computing methods. This presentation will report on a way of evaluating different parallel approaches for these applications. A set of benchmark problem is created by user community for this study. The hardware and software limitations on the parallel implementation for the methods that solve these applications will also be discussed. And, a strategy for resource management to be used while solving the applications will also be included.

10:00 TOWARD AB INITIO THEORETICAL PREDICTIONS OF CHEMICAL REACTIONS

Gregory S. Tschumper* and Brian W. Hopkins, University of Mississippi, University, MS 38677

Although computational chemistry has evolved into a reliable laboratory tool, the theoretical "prediction" of a chemical reaction generally requires a priori knowledge of the potential energy hypersurface (PES). In other words, not only must the reactan(s) be specified but also the product(s) and possibly the transition state(s) and intermediate(s). In this way, the predictive ability of computational chemistry is to a large extent limited by the creativity of chemists. Standard methods are, for example, incapable of finding unspecified or unknown reaction paths. Methods have been developed to address this shortcoming (e.g., isopotential searching and molecular dynamics). Presented here is a different approach to the prediction of chemical reactions and reaction mechanisms that is grounded in graph theory. By combining simple principles from graph theory and chemistry, it is possible to generate every feasible atomic connectivity pattern on a PES by merely specifying the reactant(s). These atomic patterns can be conveniently stored as matrices and converted into 3D molecular structures that can subsequently be used to guide existing methods. This graph theoretical technique allows chemists to systematically and efficiently explore a PES without a priori knowledge of its topology.

10:20 CHARACTERIZING URBAN VEHICLE TEST COURSES BY THEIR POWER SPECTRA

Andrew W. Harrell, Engineering Research and Development Center (ERDC), Vicksburg, MS 39180

This paper will discuss various ways to use wavelet detrending parameters to learn and identify patterns in power spectra. ERDC vehicle ride courses with urban obstacles were analyzed in terms of different time averaged, or windowed, Fourier transform formulas in order to characterize the spectra of their elevation profiles. Simulation results of the High Mobility Multi-purpose Wheeled Vehicle (HMMMV) on two different test courses, both with nearly the same root mean square (RMS) variation, have been found to generate different power spectra response characteristics in test vehicles. The Vehdyn mathematical model that was used for parallel simulations, models a test vehicle's response as being primarily due to the RMS of the test course. In these simulations the spacing of the bumps was found to generate different power spectral characteristics in different test courses with the same RMS. Thus, improving the theoretical understanding of how to characterize the power spectra of the courses should give us new and better ways to improve and validate our modeling. For instance, we expect to see this in terms of developing a better understanding of the effects of the surface geometry in urban terrain with sharp discontinuities such as potholes and obstacles on military vehicles.

10:40 EFFECTIVE INFORMATION EXTRACTION USING NATURAL LANGUAGE PROCESSING TECHNIQUES

Susan Lukose*, Frank Mathew, Sumali Conlon, and Pamela Lawhead, University of Mississippi, University, MS 38677

Information available in electronic form has grown exponentially with the growth of the Internet. Most of this information is in the form of text and is spread over a wide range of documents. If this information can be structured into a tabular form and stored in a database, it can be used for efficient decision making by systems like Real Time Expert Systems, Decision Support Systems, or intelligent agents. But manually going through all these documents to extract information is not practical. Therefore there is a need for automatic information extraction. Our approach to this problem is to build a partially domain independent information extraction system using natural language processing techniques and resources such as the lexical database WordNet and Collocation Information to perform semantic and syntactic text analysis. System development consisted of two phases. In the training phase, a knowledge base was built, which was later used in the test phase to extract information. This extracted information is structured and hence can be stored in a database easily. The unstructured input data that we use are the international corporate reports which appear in the Wall Street Journal. The performance of the system was evaluated using precision and recall of the output and the results obtained where satisfactory with the precision at 85% and recall at 87%.

11:00 Awards