 |
 |
 |
|
 |
|
|
|
|
|
2001 Abstracts of MCS Reports and Preprints |
|
Reports |
|
| E. D. Dolan, "NEOS Server 4.0 Administrative Guide," Technical Memorandum ANL/MCS-TM-250, May 2001. | The NEOS Server 4.0 provides a
general Internet-based client/server as a link between users and software applications.
The administrative guide covers the fundamental principals behind the operation of the
NEOS Server, installation and trouble-shooting of the Server software, and implementation
details of potential interest to a NEOS Server administrator. The guide also discusses making new software applications available through the Server, including areas of concern to remote solver administrators such as maintaining security, providing usage instructions, and enforcing reasonable restrictions on jobs. The administrative guide is intended both as an introduction to the NEOS Server and as a reference for use when running the Server. |
| E. D. Dolan and T. S. Munson, "The Kestrel Interface to the NEOS Server," Technical Memorandum ANL/MCS-TM-248, June 2001. | The NEOS Server provides access to optimization solvers through the Internet with a suite of interfaces. In particular, the Kestrel interface enables the remote solution of optimization problems within the AMPL and GAMS modeling languages. Problem generation, including the run-time detection of syntax errors, occurs on the local machine using any available modeling language facilities. Solution takes place on a remote machine, with the result returned in the native modeling language format for further processing. No significant differences exist between local and remote solutions. A byproduct of the Kestrel interface is the ability to solve in parallel multiple problems generated by a modeling language. |
| E. M. Gertz, P. E. Gill, and J. Muetherig, "Users Guide for SnadiOpt: A Package Adding Automatic Differentiation to Snopt," Technical Memorandum ANL/MCS-TM-245, January 2001. | SnadiOpt is a package that supports the use of the automatic differentiation package ADIFOR with the optimization package Snopt. Snopt is a general-purpose system for solving optimization problems with many variables and constraints. It minimizes a linear or nonlinear function subject to bounds on the variables and sparse linear or nonlinear constraints. It is suitable for large-scale linear and quadratic programming and for linearly constrained optimization, as well as for general nonlinear programs. The method used by Snopt requires the first derivatives of the objective and constraint functions to be available. The SnadiOpt package allows users to avoid the time-consuming and error-prone process of evaluating and coding these derivatives. Given Fortran code for evaluating only the values of the objective and constraints, SnadiOpt automatically generates the code for evaluating the derivatives and builds the relevant Snopt input files and sparse data structures. |
| E. M. Gertz and Stephen J. Wright, "OOQP User Guide," Technical Memorandum ANL/MCS-TM-252, October 2001. | OOQP is an object-oriented software package for solving convex quadratic programming problems (QP). We describe the design of OOQP, and document how to use OOQP in its default configuration. We further describe OOQP as a development framework, and outline how to develop custom solvers that solve QPs with exploitable structure or use specialized linear algebra. |
| R. Jacob, C. Schafer, I. Foster, M. Robis, J. Anderson, "Computational Design and Performance of the Fast Ocean Atmosphere Model, Version One," in Proc. 2001 Int'l Conf. on Comptuational Science (to appear). Also Climate and Global Change Report ANL/CGC-005-0401 (ps.Z, pdf), April 2001. | The Fast Ocean Atmosphere Model (FOAM) is a climate system model intended for application to climate science questions that require long simulations. FOAM is a distributed-memory parallel climate model consisting of parallel general circulation models of the atmosphere and ocean with complete physics paramterizations as well as sea-ice, land surface, and river transport models. FOAM's coupling strategy was chosen for high throughput (simulated years per day). A new coupler was written for FOAM and some modifications were required of the component models. Performance data for FOAM on the IBM SP3 and SGI Origin2000 demonstrates that it can simulate over thirty years per day on modest numbers of processors. |
| J. S. Jiang, H. G. Kaper, G. K. Leaf, "Numerical Simulations at Magnetic Reversal in Layered Spring Magnets," Technical Memorandum ANL/MCS-TM-247, Jan. 2001 | This report summarizes the results of numerical investigations of magnetic reversal in layered spring magnets. A one-dimensional model is used of a film consisting of several atomic layers of soft material on top of several atomic layers of hard material. Each atomic layer is taken to be uniformly magnetized, and spatial inhomogeneities within an atomic layer are neglected. The state of such a system is described by a chain of magnetic spin vectors. Each spin vector behaves like a spinning top driven locally by the effective magnetic field and subject to damping (Landau-Lifshitz-Gilbert equation). A numerical integration scheme for the LLG equation is presented that is unconditionally stable and preserves the magnitude of the magnetization vector at all times. The results of numerical investigations for a bilayer in a rotating in-plane magnetic field show hysteresis with a basic period of 2µ at moderate fields and hysteresis with a basic period of µ (or any multiple thereof) at strong fields. |
| I. R. Judson, "The µMural: A Six-Projector Tiled Display," Technical Memorandum ANL/MCS-TM-251, June 2001. | Tiled displays have become a recent technical solution to aggregating commodity displays in order to provide higher resolution displays. This document describes the background, design, and implementation of the micromural, a six projector tiled display developed at Argonne National Laboratory. |
| J. W. Larson, R. L. Jacob, I. Foster, and J. Guo, "The Model Coupling Toolkit," 2001, Proc. 2001 Int'l Conf. on Computational Science, eds. V. N. Alexandrov, J. J. Dongarra, and C. J. K. Tan, Springer-Verlag (to appear). Also Climate and Global Change Report ANL/CGC-007-0401, April 2001. (ps, pdf) | The advent of coupled earth system models has raised an important question in parallel computing: What is the most effective method for coupling many parallel models to form a high-performance coupled modeling system? We present our solution to this problem---The Model Coupling Toolkit (MCT). We explain how our effort to construct the Next-Generation Coupler for NCAR Community Climate System Model motivated us to create this toolkit. We describe in detail the conceptual design of the MCT and explain its usage in constructing parallel coupled models. We present preliminary performance results for the toolkit's parallel data transfer facilities. Finally, we outline an agenda for future development of the MCT. |
| W. McCune, "MACE 2.0 Reference Manual and Guide," Technical Memorandum ANL/MCS-TM-249, May 2001. | MACE is a program that searches for finite models of first-order statements. The statement to be modeled is first translated to clauses, then to relational clauses; finally for the given domain size, the ground instances are constructed. A Davis-Putnam-Loveland-Logeman procedure decides the propositional problem, and any models found are translated to first-order models. MACE is a useful complement to the theorem prover Otter, with Otter searching for proofs and MACE looking for countermodels. |
| J. Taylor and J. Larson, Resolution Dependence in Modeling Extreme Weather Events," Proc. 2001 Int'l conf. on Computational Science, eds. V. N. Alexandrov, J. J. Dongarra, and C. J. K. Tan, Springer-Verlag (to appear). Also, Climate and Global Change Report ANL/CGC-008-0401, April 2001. | At Argonne National Laboraory we have developed a high performance regional climate modeling simulation capability based on the NCAR MM5v3.4. The regional climate simulation system at Argonne currently includes a Java-based interface to allow rapid selection and generation of initial and boundary conditions, a high-performance version of MM5v3.4 modified for long climate simulations on our 512-processor Beowulf cluster (Chiba City), an interactive Web-based analysis tool to facilitate analysis and collaboration via the Web, and an enhanced version of the DAVE5d software capable of working with large climate data sets. In this paper we describe the application of this modeling system to investigate the role of model resolution in predicting extreme events such as the "Hurricane Huron" event of 11-15 September 1996. We have performed a series of "Hurricane Huron" experiments at 80, 40, 20, and 10 km grid resolution over an identical spatiotemporal domain. We conclude that increasing model resolution leads to dramatic changes in the vertical structure of the simulated atmosphere producing significantly different representations of rainfall and other parameters critical to the assessment of impacts of climate change. |
| J. Taylor, J. Larson, S. Voeltz, "Climate Modeling at the Regional Scale," Climate and Global Change Report ANL/CGC-009-0601 (doc, pdf), June 2001. | At Argonne National Laboratory we have developed a high-performance regional climate modeling system based on the NCAR MM5v3.4 mesoscale weather forecasting model. The Argonne system currently includes a Java-based interface to allow rapid selection and generation of initial and boundary conditions, a high-performance version of MM5v3.4 modified for long climate simulations on supercomputers (including Argonne’s 512-processor Linux cluster, Chiba City), an interactive Web-based analysis tool to facilitate analysis and collaboration via the Web, and an enhanced version of the CAVE5d software capable of working with large climate data sets. We illustrate the application of this modeling system to the study of the climate of the U.S. Midwest. In particular, we investigate the role of model resolution in predicting extreme events, such as "Hurricane Huron" event of 11-15 September 1996. We have performed a series of "Hurricane Huron" experiments at 80, 40, 20, and 10 km grid resolution over an identical spatiotemporal domain. We conclude that increasing model resolution in our regional climate simulations leads to dramatic changes in the vertical structure of the simulated atmosphere, producing significantly different representations of rainfall, wind velocities, and other parameters critical to the assessment of impacts of climate change. Future climate simulations at regional resolution could provide a much more realistic basis for the assessment of the impacts of future climate change on both natural and human systems. |
Preprints |
|
| S. J. Wright, "Effects of Finite-Precision Arithmetic on Interior-Point Methods for Nonlinear Programming," Preprint ANL/MCS-P705-0198, Jan. 2001. | We show that the effects of
finite-precision arithmetic in forming and solving the linear system that arises at each
iteration of primal-dual interior-point algorithms for nonlinear programming are benign,
provided that the iterates satisfy centrality and feasibility conditions of the type
usually associated with path-following methods. When we replace the standard assumption
that the active constraint gradients are independent by the weaker Mangasarian-Fromovitz
constraint qualification, rapid convergence usually is attainable, even when cancellation
and roundoff errors occur during the calculations. In deriving our main results, we prove a key technical result about the size of the exact primal-dual step. This result can be used to modify existing analysis of primal-dual interior-point methods for convex programming, making it possible to extend the superlinear local convergence results to the nonconvex case. |
| S. J. Benson and Y.Ye, "DSDP3: Dual Scaling Algorithm for General Positive Semidefinite Programming," Preprint ANL/MCS-P851-1000, Feb. 2001. | We implement a dual scaling algorithm for positive semidefinite programming to handle a broader class of problems than could be solved with previous implementations of the algorithm. With appropriate representations of constraint matrices, we can solve general semidefinite programs and still exploit the structure of large-scale combinatorial optimization problems. Computational results show that our preliminary implementation is competitive with primal-dual solvers on many problems requiring moderate precision in the solution and is superior to primal-dual solvers for several types of problems. |
| E. D. Dolan and J. J. Moré, "Benchmarking Optimization Software with Performance Profiles," Math. Program., Ser. A 91 (2002), pp. 201-213. The original publication is available on LINK at http://link.springer.de. Search on first author. Also Preprint ANL/MCS-P861-1200, Jan. 2001. | We propose performance profile---distribution functions for a performance metric---as a tool for benchmarking and comparing optimization software. We show that performance profiles combine the best features of other tools for performance evaluation. |
| G. von Laszewski, J. Gawor, P. Lane, N. Rehn, and M. Russell, "Features of the Java Commodity Grid Kit" (published title), Concurrency Computat.: Pract. Exper. 14 (2002), pp. 1045-1055. Also Preprint ANL/MCS-P862-1200, Dec. 2000, revised 2002 | In this paper we report on the features of the Java Commodity Grid Kit (Java CoG Kit). The Java CoG Kit provides middleware for accessing Grid functionality from the Java framework. Java CoG Kit middleware is general enough to design a variety of advanced Grid applications with quite different user requirements. Access to the Grid is established via Globus Toolkit protocols, allowing the Java CoG Kit to also communicate with the services distributed as part of the C Globus Toolkit reference implementation. Thus, the Java CoG Kit provides Grid developers with the ability to utilize the Grid, as well as numerous additional libraries and frameworks developed by the Java community to enable network, Internet, enterprise, and peer-to-peer computing. A variety of projects have successfully used the client libraries of the Java CoG Kit to access Grids driven by the C Globus Toolkit software. In this paper we also report on the efforts to develop serverside Java CoG Kit components. As part of this research we ahve implemented a prototype pure Java resource management system that enables one to run Grid jobs on platforms on which a Java virtual machine is supported, including Windows NT machines. |
| J. S. Jiang, H. G. Kaper, G. K. Leaf, "Hysteresis in Layered Spring Magnets," Discrete and Continuous Dynamical Systems-Series B 1, no. 2 (May 2001, 219-232. Also Preprint ANL/MCS-P867-0101, Jan. 2001 | This article addresses a problem of micromagnetics: the reversal of magnetic moments in layered spring magnets. A one-dimensional model is used of a film consisting of several atomic layers of a soft material on top of several atomic layers of a hard material. Each atomic layer is taken to be uniformly magnetized, and spatial inhomogeneities within an atomic layer are neglected. The state of such a system is described by a chain of magnetic spin vectors. Each spin vector behaves like a spinning top driven locally by the effective magnetic field and subject to damping (Landau-Lifshitz-Gilbert equation). A numerical integration scheme for the LLG equation is presented that is unconditionally stable and preserves the magnitude of the magnetization vector at all times. The results of numerical investigations for a bilayer in a rotating in-plane magnetic field show hysteresis with a basic period of 2pat moderate fields and hysteresis with a basic period of p at strong fields. |
| J. Michalakes, S. Chen, J. Dudhia, L. Hart, J. Klemp, J. Middlecoff, W. Skamarock, "Development of a Next-Generation Regional Weather Research and Forecast Model," Preprint ANL/MCS-P868-0101, Jan. 2001. | The Weather Research and Forecast (WRF) project is a multi-institutional effort to develop an advanced mesoscale forecast and data assimilation system that is aaccurate, efficient, and scalable acrossa range of scales and over a host of computer platforms. The first release, WRF 1.0, was Nov. 30, 2000, with operational deployment targeted for the 2004-05 time frame. This paper provides an overview of the project and current status of the WRF development effort in the areas of numerics and physics, software and data architecture, and single-source parallelism and performance portability. |
| S. Vazhkudai, S. Tuecke, I. Foster, "Replica Selection in the Globus Data Grid," to be presented at CCGrid 2001, 5/01, Brisbane, Austr. Preprint ANL/MCS-P869-0201, Feb. 2001. | The Globus Data Grid architecture provides a scalable infrastructure for the management of storage resources and data that are distributed across Grid environments. These services are designed to support a variety of scientific applications, ranging from high-energy physics to computational genomics, that require access to larage amounts of data (terabytes or even petabytes) with varied quality of service requirements. By layering on a set of core services, such as data transport, security, and replica cataloging, one can construct various higher-level services. In this paper, we discuss the design and implementation of a high-level replica selection service that uses information regearding replica location and user preferences to guide selection from among storage replica alternatives. We first present a basic replica selection service design, then show how dynamic information collected using Globus information service capabilities concerning storage system properties can help improve and optimize the selection process. We demonstrate the use of Condor's ClassAds resource description and matchmaking mechanism as an efficient tool for representing and matching storage resource capabilities and policies against application requirements. |
| I. Foster, C. Kesselman, and S. Tuecke, "The Anatomy of the Grid - Enabling Scalable Virtual Organizations," to appear Int'l J. Supercomputer Applications, 2001. Also Preprint ANL/MCS-P870-0201, Feb. 2001. | "Grid" computing has emerged as an important new field, distinguished from conventioanl distributed computng by its focus on large-scale resource sharing, innovative applications, and, in some cases, high-performance orientation. In this article, we define this new field. First, we review the "Grid problem," which we define as flexible, secure, coordinated resource sharing among dynamic collections of individuals, institutions, and resources---what we refer to as virtual organizations. In such settings, we encounter unique authentication, authorization, resource access, resource discovery, and other challenges. It is this class of problem that is addressed by Grid technologies. Next, we present an extensible and open Grid architecture, in which protocols, services, application programming interfaces, and software development kits are categorized according to their roles in enabling resource sharing. We describe requirements that we believe any such mechanisms must satisfy, and we discuss the central role played by the intergrid protocols that enable interoperability among different Grid systems. Finally, we discuss how Grid technologies relate to other contemporary technologies, including enterprise integration, application service provider, storage service provider, and peer-to-peer computing. We maintain that Grid concepts and technologies complement and have much to contribute to these other approaches. |
| B. Allcock, J. Bester, J. Bresnahan, A. L. Chervenak, I. Foster, C. Kesselman, S. Meder, V. Nefedova, D. Quesnel, S. Tuecke, "Secure, Efficient Data Transport and Replica Management for High-Performance Data-Intensive Computing," Preprint ANL/MCS-P871-0201, Feb. 2001. | An emerging class of data-intensive applications involve the geographically dispersed extracation of complex scientific information from very large collections of measured or computed data. Such applications arise, for example, in experimental physics, where the data in question is generated by accelerators, and in simulation science where the data is generated by supercomputers. So-called Data Grids provide essential infrastructure for such applications, much as the Internet provides essential services for applications such as e-mail and the Web. We describe here two services that we believe are fundamental to any Data Grid: reliable, high-speed transport and replica management. Our high-speed transport service, GridFTP, extends the popular FTP protocol with new featuares required for Data Grid applications, such as striping and partial file access. Our replica management service integrates a replica catalog with GridFTP transfers to provide for the creation, registration, location, and management of dataset replicas. We present the design of both services and also preliminary performanace results. Our implementations exploit security and other services provided by the Globus Toolkit. |
| R. Butler, W. Gropp, and E. Lusk, "Components and Interfaces of a Process Management System for Parallel Programs," Parallel Computing 27 (2001), pp. 1417-1429. Also Preprint ANL/MCS-P872-0201, Feb. 2001. | Parallel jobs are different from sequential jobs and require a different type of process management. We present here a process management system for parallel programs such as those written using MPI. A primary goal of the system, which we call MPD (for multipurpose daemon), is to be scalable. By this we mean that startup of interactive parallel jobs comprising thousands of processes is quick, that signals can be quickly delivered to processes, and that stdin, stdout, and stderr are managed intuitively. Our primary target is parallel machines made up of clusters of SMPs, but the system is also useful in more tightly interated environments. We describe how MPD enables much faster startup and better runtime management of parallel jobs. We show how close control of stdio can support the easy implementation of a number of convenient system utilities, even a parallel debugger. We describe a simple but general interface that can be used to separate any process manager from a parallel library, which we use to keep MPD separate from MPICH. |
| E. M. Gertz, "A Quasi-Newton Trust-Region Method," Preprint ANL/MCS-P873-0201, February 2001. | The classical trust-region method
for unconstrained minimization can be augmented with a line search that finds a point that
satisfies the Wolfe conditions. One can use this new method to define an algorithm that
simultaneously satisfies the quasi-Newton condition at each iteration and maintains a
positive-definite approximation to the Hessian of the objective function. This new
algorithm has strong global convergence properties and appears to be robust and efficient in practice. |
| J. Linderoth and S. Wright, "Decomposition Algorithms for Stochastic Programming on a Computational Grid," Preprint ANL/MCS-P875-0401, April 2001 | We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker type (with the workers being used to solve second-stage problems), and the MW runtime support library (which supports master-worker computations) is key to the implementation. Computational results are presented on large sample average approximations of problems from the literature. |
| L. R. Leung, J. G. Michalakes, and X. Bian, "Parallelization of a Subgrid Orographic Precipitation Scheme in an MM5-based Regional Climate Model," Preprint ANL/MCS-P876-0301, March 2001. Also ANL/MCS Climate and Global Change report ANL/CGC-006-0401, April 2001. | Regional Climate Models (RCMs) are
practical downscaling tools to yield regional climate information for assessing the
impacts of climate variability and change. The Pacific Northwest National Laboratory
(PNNL) RCM, based on the Penn State/NCAR Mesoscale Model (MM5), features a novel subgrid
treatment of orographic precipitation for coupling climate, hydrologic, and ecologic
processes at the watershed scale. The parameterization aggregates subgrid variations of
surface topography into a finite number of surface elevation bands. An airflow model and a
thermodynamic model are used to parameterize the orographic uplift/descent as air parcels
cross over mountain barriers or valleys. The parameterization has significant performance
advantages over nesting to achieve comparable resolution of climate information; however,
previous implementations of the subgrid scheme required significant modification to the
host MM5 model, prohibiting its incorporation within the NCAR-supported community version
of MM5. With this effort, software engineering challenges have been addressed to
incorporate, parallelize, and load-balance the PNNL subgrid scheme with minimum changes to MM5. The result is an efficient, maintainable tool for regional climate simulation and a step forward in the development of an MM5-based community regional climate model. |
| R. Shepard, A. F. Wagner, J. L. Tilson, and M. Minkoff, "The Subspace Projected Approximate Matrix (SPAM) Modification of the Davidson Method," J. Computational Physics 172(2) (2001) 572-514. Also Preprint ANL/MCS-P878-0401, April 2001. | A modification of the iterative matrix diagonalization method of Davidson is presented that is applicable to the symmetric eigenvalue problem. This method is based on subspace projections of a sequence of one or more approximate matrices. The purpose of these approximate matrices is to improve the efficiency of the solution of the desired eigenpairs by reducing the number of matrix-vector products that must be computed with the exact matrix. Several applications are presented. These are chosen to show the range of applicability of the method, the convergence behavior for a wide range of matrix types, and also the wide range of approaches that may be employed to generate approximate matrices. |
| M. Garbey, H. G. Kaper, and N. Romanyukha, "A Fast Solver for Systems of Reaction-Diffusion Equations," Preprint ANL/MCS-P879-0301, March 2001. | In this paper we present a fast
algorithm for the numerical solution of systems of reaction-diffusion equations, ¶iu + a × Ñu = Du + F(x,t,u), x e W Ì R3, t > 0 . Here, u is a vector-valued function, u º u(x,t) e Rm, m is large, and the corresponding system of ODEs, ¶tu = F(x,t,u), is stiff. Typical examples arise in air pollution studies, where a is the given wind field and the nonlinear function F models the atmospheric chemistry. |
| T. Colin, C. Galusinski, and H. G. Kaper, "Waves in Ferromagnetic Media," Communications in Partial Differential Equations (to appear). Also Preprint ANL/MCS-P880-0301, March 2001. | It is sown that small perturbations of equi8librium states in ferromagnetic media give rise to standing and traveling waves that are stable for long times. The evolution of the wave profiles is governed by semilinear heat equations. The mathematical model underlying these results consists of the Landau-Lifshitz equation for the magnetization vector and Maxwell's equations for the electromagnetic field variables. The model belongs to a general class of hyperbolic equations for vector-valued functions, whose asymptotic properties are analyzed rigorously. The results are illustrated with numerical examples. |
| T. Iliescu, V. John, and W. J. Layton, "Convergence of Finite Element Approximations of Large Eddy Motion," Preprint ANL/MCS-P881-0401, April 2001. | Fluid motion in many applications occurs at higher Reynolds numbers. In these applications dealing with turbulent flow is thus inescapable. One promising approach to the simulation of the motion of the large structures in turbulent flow is large eddy simulation in which equations describing the motion of local spatial averages of the fluid velocity are solved numerically. This report considers "numerical errors" in LES. Specifically, for one family of space filtered flow models, we show convergence of the finite element approximation of the model and give an estimate of the error. |
| M. R. Paul, M. C. Cross, P. F. Fischer, and H. S. Greenside, "Power Law Behavior of Power Spectra in Low Prandtl Number Rayleigh-Bénard convection," Preprint ANL/MCS-P883-0501, May 2001. | The origin of the power-law decay mesured in the power spectra of low Prandtl number Rayleigh-Bénard convection near the onset of chaos is addressed using long time numerical simulations of the three-dimensional Boussinesq equations in cylindrical domains. The power law is found to arise from quasi-discontinuous changes in the slope of the time series of the heat transport associated with the nucleation of dislocation pairs and roll pinch-off events. For larger frequencies, the power spectra decay exponentially as expected for time continuous deterministic dynamics. |
| M. Anitescu and F. A. Potra, "A Time-Stepping Method for Stiff Multibody Dynamics with Contact and Friction," Int. J. Numer. Meth. Engng 55, no. 7 (2002), pp. 753-784. Also Preprint ANL/MCS-P884-0501, May 2001. | We define a time-stepping procedure to integrate the equations of motion of stiff multibody dynamics with contact and friction. The friction and noninterpenetration constraints are modeled by complementarity equations. Stiffness is accommodated by a technique motivated by a linearly implicit Euler method. We show that the main subproblem, a linear complementarity problem, is consistent for a sufficiently small time step h. In addition, we prove that for the most common type of stiff forces encountered in rigid body dynamics, wehre a damping or elastic force is applied between two points of the system, the method is well defined for any time step h. We show that the method is stable in the stiff limit, unconditionally with respect to the damping parameters, near the equilibrium points of the springs. The integration step approaches, in the stiff limit, the integration step for a system where the stiff forces have been replaced by corresponding joint constraints. Simulations for one- and two-dimensional examples demonstrate the stable behavior of the method. |
| E. Ong, E. Lusk, and W. Gropp, "Scalable Unix Commands for Parallel Processors: A High-Performance Implementation," in Recent Advances in Parallel Virtual Machine and Message Passing Interface, eds. Y. Cotronis and J. Dongarra, Lecture Notes in Computer Science, Vol. 2131, Springer-Verlag, pp. 410-418, Sept. 2001. Also Preprint ANL/MCS-P885-0601, June 2001. | We describe a family of MPI applications we call the Parallel Unix Commands. These commands are natural parallel versions of common Unix user commands such as ls, ps, and find, together with a few similar commands particular to the parallel environment. We describe the design and implementation of these programs and present some performance results on a 256-node Linux cluster. The Parallel Unix Commands are open source and freely available. |
| S. Vazhkudai and G. von Laszewski, "A Greedy Grid - The Grid Economic Engine Directive," Preprint ANL/MCS-P886-0501, May 2001. | The advent of national-scale "Computational Grid" infrastructures has helped deploy advanced services, beyond those taken for granted in today's Internet, such as: remote access to computers, wide area resource management, authentication, and directory services, thus enabling access and utilization of a variety of heterogeneous resources distributed over multiple domains. The availability of these services represents an opportunity to implement advanced services utilizing these basic Grid services. In this paper, we explore issues related to defining services that are based on economy and financial models in order to encourage further resource sharing among the administrative domains while also considering commodity PC's that are part of todays Internet. We propose an extendable architecture, The Grid Economic Engine Directive (Greed), that allows integration of various economy models within the same framework, exposing the services through secure protocols and policies. The services provided by this framework include, for example, a bartering service, a bidding service, and a trading service. We intend to develop components that can be integrated within a customizable Portal simplifying access to many of the services and propose to integrate the Greed economic middleware into the existing Globus metacomupting toolkit, thus enabling the application of economic paradigm to the Globus Computational and Data Grids. We further illustrate the applicability of the proposed Greed services by building a prototype business model as a higher-level application, using the economic middleware. |
| Y. Wang, F. De Carlo, D. C. Mancini,
I. McNulty, B. Tieman, J. Bresnahan, I. Foster, J. Insley, P. Lane, G. von Laszewski,
"A High-Throughput X-Ray Microtomography System at the Advanced Photon Source," Rev.
of Scientific Instruments 72, no. 4 (April 2001), pp. 2062-2068.
Also Preprint ANL/MCS-P887-0401,
April 2001.
|
A third-generation synchrotron radiation source provides enough brilliance to acquire complete tomographic data sets at 100 nm or better resolution in a few minutes. To take advantage of such high-brilliance sources at the Advanced Photon Source, we have constructed a pipelined data acquisition and reconstruction system that combines a fast detector system, high-speed data networks, and massively parallel computers to rapidly acquire the projection data and perform the reconstruction and rendering calculations. With the current setup, a data set can be obtained and reconstructed in tens of minutes. A specialized visualization computer makes rendered three-dimensional (3D) images available to the beamline users minutes after the data acquisition is completed. This system is capable of examining a large number of samples at sub-µm 3D resolution or studying the full 3D structure of a dynamically evolving sample on a 10 min temporal scale. In the near future, we expect to increase the spatial resolution to below 100 nm by using zone-plate x-ray focusing optics and to improve the time resolution by the use of a broadband x-ray monochromator and a faster detector system. |
| R. Ross, D. Nurmi, A. Cheng, M. Zingale, "A Case Study in Application I/O on Linux Clusters," Proc. SC2001, Denver, CO, Nov. 2001. Also Preprint ANL/MCS-P888-0701, July 2001. | A critical but often ignored component of system performance is the I/O system. Today's applications expect a great deal from underlying storage systems and software, and both high performance distributed storage and high level interfaces have been developed to fill these needs. In this paper we discuss the I/O performance of a parallel scientific application on a Linux cluster, the FLASH astrophysics code. This application relies on three I/O software components to provide high performance parallel I/O on Linux clusters: the Parallel Virtual File System (PVFS), the ROMIO MPI-IO implementation, and the Hierarchical Data Format (HDF5) library. First we discuss the roles played by each of these components in providing an I/O solution. Next we discuss the FLASH I/O benchmark and point out its relevance. Following this we examine the performance of our benchmark, and through instrumentation of both the application and underlying system software code we discover the location of major software bottlenecks. We work around the most inhibiting of these bottlenecks, showing substantial performance improvement. Finally we point out similarities between the inefficiencies found here and those found in message passing systems, indicating that research in the message passing field could be leveraged to solve similar problems in high-level I/O interfaces. |
| E. Dolan, P. Hovland, J. Moré. B. Norris, and B. Smith, "Remote Access to Mathematical Software," Preprint ANL/MCS-P889-0601, June 2001. | The network-oriented application services paradigm is becoming increasingly common for scientific computing. The popularity of this approach can be attributed to the numerous advantages to both user and developer provided by network-enabled mathematical software. The burden of installing and maintaining complex systems is lifted from the user, while enabling developers to provide frequent updates without disrupting service. Access to software with similar functionality can be unified under the same interface. Remote servers can utilize potentially more powerful computing resources than may be available locally. We discuss some of the application services developed by the Mathematics and Computer Science Division at Argonne National Laboratory, including the Network Enabled Optimization System (NEOS) Server and the Automatic Differentiation of C (ADIC) Server, as well as preliminary work on Web access to the Portable Extensible Toolkit for Scientific Compuoting (PETSc). We also provide a brief survey of related work. |
| A. Schreiber, "The Integrated Simulation Environment TENT," Preprint ANL/MCS-P890-0701, July 2001. | This paper describes recent development efforts on the integrated simulation environment TENT. TENT is a component-based software integration and workflow management system using the capabilities of CORBA and Java. It is used to integrate the applications required to form complex workflows, which are typical of multidisciplinary simulations in engineering, in which different simulation codes have to be coupled. We present here our work in integrating TENT with the Globus Toolkit to create a Grid computing environment. The Java Commodity Grid Toolkit has been especially useful for this work. |
| M. Gertz and S. Wright, "Object-Oriented Software for Quadratic Programming," ACM Trans. Math. Software 29, no. 1 (2003), pp. 58-81. Also Preprint ANL/MCS-P891-0701, October 2001. | We describe the object-oriented software package OOQP for solving convex quadratic programming problems (QP). The primal-dual interior point algorithms supplied by OOQP are implemented in a way that is largely independent of the problem structure. Users may exploit problem structure by supplying linear algebra, problem data, and variable classes that are customized to their particular applications. The OOQP distribution contains default implementations that solve several important QP problem types, including general sparse and dense QPs, bound-constrained QPs, and QPs arising from support vector machines and Huber regression. The implementations supplied with the OOQP distribution are based on such well known linear algebra packages as MA27/57, LAPACK, and PETSc. |
| P. Fischer and T. Iliescu, "A 3D Channel Flow Simulation at RE[sub \tau] = 180 Using a Rational LES Model," Preprint ANL/MCS-P893-0801, Aug. 2001. | This paper presents numerical results obtained by applying an LES model based on a rational (subdiagonal Padé) approximation in the wave number space. We used a spectral element code to test this LES model, a coarse DNS, and the Smagorinsky model with Van Driest damping in the numerical simulation of a 3D channel flow at Re[sub \tau] = 180. The corresponding results were compared with the fine DNS simulation of Moser, Kim, and Mansour. |
| S. Verma, J. Gawor, G. von Laszewski, and M. Parashar, "A CORBA Commodity Grid Kit," Concurrency Computat.: Pract. Exper. 14 (2002), pp. 1057-1074. Also Preprint ANL/MCS-P896-0701, July 2001. | This paper reports on a work-in-progress aimed at designing and deploying a CORBA Commodity Gird (CoG) Kit. The overall goal of this project is to explore how to enable the development of advanced Grid applications while adhering to state-of-the-art software engineering practices and reusing existing Grid infrastructure. As part of this activity, we are currently investigating how CORBA can be used to support this software engineering task. In this paper, we outline the design of a CORBA Commodity Grid Kit that will provide a software development framework for building a CORBA "Grid domain." We also present our current experiences in developing a prototype CORBA CoG Kit that provides access to the Globus toolkit functionality to support Grid development. |
| G. von Laszewski, I. Foster, G. K. Thiruvathukal, B. Toonen, "A Computational Framemwork for Telemedicine," Preprint ANL/MCS-P897-0701, July 2001. | Emerging telemedicine applications require the ability to exploit diverse, geographically distributed resources. These applications use high-speed neworks to integrate supercomputers, large databases, archival storage devices, advanced visualization devices, and/or sophisticated instruments. This form of networked virtual supercomputers is also known as metacomputers and is being used by many other scientific applications areas. In this article, we analyze requirements necessary for a telemedicine computing infrastructure and compare them with requirements found in a typical metacomputing environment. We will show that metacomputing environments can be used to enable a more powerful and unified computational infrastructure for telemedicine. The Globus metacomputing environment can provide the necessary basis to enable a large scale telemedical infrastructure. Globus is designed in a modular fashion and can be extended to support the specific requirements for telemedicine. |
| L. Wos, "The Strategy of Cramming," J. Automated Reasoning (to appear). Also Preprint ANL/MCS-P898-0801, Aug. 2001. | Offered in this article is a new strategy, cramming, that can serve well in an attempt to answer an open question or in an attempt to find a shorter proof. Indeed, when the question can be answered by proving a conjunction, cramming can provide substantial assistance. The basis of the strategy rests with forcing so many steps of a subproof into the remainder of the proof that the desired answer is obtained. As for reduction in proof length, the literature shows that proof shortening (proof abridgment) was indeed of interest to some of the masters of logic, masters that include C. A. Meredith, A. Prior, and I. Thomas. The problem of proof shortening (as well as other aspects of simplification) is also central to the recent discovery by R. Thiele of Hilbert's twenty-fourth problem. Although that problem was not included in his 1900 Paris lecture (because he had not yet sufficiently formulated it), Hilbert stressed at various times in his life the importance of finding simpler proofs. Because a sharp reduction in proof length (of constructive proofs) is correlated with a significant reduction in the complexity of the object being constructed, the cramming strategy is relevant to circuit design and program synthesis. The most impressive success with the use of the cramming strategy concerns an abridgment of the Meredith-Prior abridging of the Lukasiewicz proof for his shortest single axiom for the implicational fragment of two-valued sentential (or classical propositional) calculus. In the context of answering open questions, the most satisfying examples to date concern the study of the right-group calculus and the study of the modal logic C5. Various challenges are offered here. |
| R. Thiele and L. Wos, "Hilbert's Twenty-Fourth Problem," J. Automated Reasoning, vol. 29, no. 1 (2002), pp. 67-89. Also Preprint ANL/MCS-P899-0801, Aug. 2001. | For almost a century, a treasure lay hidden in a library in Germany, hidden until a remarkable discovery was made. Indeed, for most of the twentieth century, all of science thought that Hilbert had posed twenty-three problems, and no others. In the mid-1990s, however, as a result of a thorough reading of Hilbert's files, a twenty-fourth problem was found (in a notebook, in file Cod. ms. D. Hilbert 600:3), a problem that might have a profound effect on research. This newly discovered problem focuses on the finding of simpler proofs and criteria for measuring simplicity. A proof may be simpler than previously known in one or more ways that include length, size (measured in terms of the total symbol count), and term structure. A simpler proof not only is more appealing aesthetically (and has fascinated masters of logic including C. A. Meredith, A Prior, and I. Thomas) but is relevant to practical applications such as circuit design and program synthesis. This article presents Hilbert's twenty-fourth problem, discusses its relation to certain studies in automated reasoning, and offers researchers with varying interests the challenge of addressing this newly discovered problem. In particular, we include open questions to be attacked, questions that (in different ways and with diverse proof refinements as the focus) may prove of substantial interest to mathematicians, to logicians, and (perhaps in a slightly different manner) to those researchers primarily concerned with automated reasoning. |
| M. Rose and K. Wilkinson, "Application of Model Search to Lattice Theory," Association for Automated Reasoning Newsletter, Aug. 2001, No. 52. Also Preprint ANL/MCS-P900-0801, Aug. 2001. | We have used the first-order
model-searching programs MACE and SEM to study various problems in lattice theory. First,
we present a case study in which the two programs are used to examine the differences
between the stages along the way from lattice theory to Boolean algebra. Second, we answer
several questions posed by Norman Megill and Mladen Pavicic on ortholattices and
orthomodular lattices. The questions from Megill and Pavicic arose in their study of quantum logics, which are being investigated in connection with proposed computing devices based on quantum mechanics. Previous questions of a similar nature were answered by McCune and MACE in W. McCune, "Automatic Proofs and Counterexamples for Some Ortholattice Identities," Information Processing Letters 65 (1998), pp. 285-291. MACE (Models And Counter Examples) (W. McCune, "MACE 2.0 Reference Manual and Guide," Tech Memo ANL/MCS-TM-249, MCS Division, Argonne National Laboratory, Argonne, IL, June 2001) and SEM (System for Enumerating Models) (J. Zhang and H. Zhang, "SEM: A System for Enumerating Models. In Proceedings of the International Joint Conf. on AI, Morgan Kaufmann, 1995) are programs that search for finite models of first-order and equational logic statements. If the input statement is the denial of a conjecture, then any models found are counterexamples. MACE searches for models by transforming its input into an equiconsistent propositional problem, then calling a Davis-Putnam-Loveland-Logeman procedure. SEM uses a more direct method of filling in tables according to various heuristics and evaluating the input against the tables. SEM is usually more effective than MACE for problems with large formulas. Both programs are designed to be complete; that is, if the search for a model of size n terminates without finding a model, then there should be none of that size. We believe the lattices we present in this note are the smallest ones satisfying the given properties, because the programs reported that smaller examples do not exist. This note has a companion page on the World Wide Web. The page http://www.mcs.anl.gov/AR/aar_lattice contains links to MACE, SEM, and EQP input files and other data files related to this work. In this note, we refer to those files with bold-faced underlined pseudolinks like this. |
| W. McCune, "Single Axioms: With and Without Computers," Preprint ANL/MCS-P901-0801, Aug. 2001. | This note is an (incomplete) summary of results on single equational axioms for algebraic theories. Pioneering results were obtained d3ecades ago (without the use of computers) by logicians such as Tarski, Higman, Neumann, and Padmanabhan. Use of today's high-speed computers and sophisticated software for searching for proofs and counterexamples has led to many additional results. |
| I. Foster, "Grid Technologies and Applications: Architecture and Achievements," Preprint ANL/MCS-P902-0801, Aug. 2001. | The 18 months since CHEP'2000 have seen significant advances in Grid computing, both within and outside high energy physics. While in early 2000, Grid computing was a novel concept that most CHEP attendees were being exposed to for the first time, we now see considerable consensus on Grid architecture, a solid and widely adopted technology base, major funding initiatives, a wide variety of projects developing applications and technologies, and major deployment projects aimed at creating robust Grid infrastructures. I provide a summary of major developments and trends, focusing on the Globus open source Grid software project and the GriPhyN data grid project. |
| W. D. Gropp, "Learning from the Success of MPI," Preprint ANL/MCS-P903-0801, August 2001. | The Message Passing Interface (MPI) has been extremely successful as a portable way to program high-performance parallel computers. This success has occurred in spite of the view of many that message passing is difficult and that other approaches, including automatic parallelization and directive-based parallelism, are easier to use. This paper argues that MPI has succeeded because it addresses all of the important issues in providing a parallel programming model. |
| G. Allen, D. Angulo, I. Foster, G. Lanfermann, C. Liu, T. Radke, E. Seidel, and J. Shalf, "The Cactus Worm: Experiments with Dynamic Resource Discovery and Allocation in a Grid Environment," Preprint ANL/MCS-P904-0801, Aug. 2001. | The ability to harness heterogeneous, dynamically available "Grid" resources is attractive to typically resource-starved computational scientists and engineers, as in principle it can increase, by significant factors, the number of cycles that can be delivered to applications. However, new adaptive application structures and dynamic runtime system mechanisms are required if we are to operate effectively in Grid environments. In order to explore some of these issues in a practical setting, we are developing an experimental framework, called Cactus, that incorporates both adaptive application structures for dealing with changing resource characteristics and adaptive resource selection mechanisms that allow applications to change their resource allocations (e.g., via migration) when performance falls outside specified limits. We describe here the adaptive resource selection mechanisms and describe how they are used to achieve automatic application migration to "better" resources following performance degradation. Our results provide insights into the architectural structures required to support adaptive resource selection. In addition, we suggest that this "Cactus Worm" is an interesting challenge problem for Grid computing. |
| P. F. Fischer, G. W. Kruse, and F. Loth, "Spectral Element Methods for Transitional Flows," J. of Sci. Comput. 17(1) (2001), pp. 81-98. Also Preprint ANL/MCS-P907-0901, Sept. 2001. | We describe the development and implementation of an efficient spectral element code for simulating transitional flows in complex three-dimensional domains. Critical to this effort is the use of geometrically nonconforming elements that allow localized refinement in regions of interest, coupled with a stabilized high-order time-split formulation of the semi-discrete Navier-Stokes equations. Simulations of transition in a model of an arteriovenous graft illustrate the potential of this approach in biomechanical applications. |
| N. Maltsev, E. Marland, G. X. Yu, S. Bhatnagar, and R. Lusk, "Sentra, a Database of Signal Transduction Proteins," Preprint ANL/MCS-P908-0901, Sept. 2001. | Sentra (http://www-wit.mcs.anl.gov/sentra) is a database of signal transduction proteins with the emphasis on microbial signal transduction. The database was updated to include classes of signal transduction systems modulated by either phosphorylation or methylation reactions such as PAS proteins and serine-threonine kinases, as well as the classical two-component histidine kinases and methyl-accepting chemotaxis proteins. Currently Sentra contains signal transduction proteins from forty-five completely sequenced prokaryotic genomes as well as sequences from 264 organisms from SWISS-PROT and TrEMBL. Signal transduction proteins are annotated with information describing conserved domains, paralogous and orthologous sequences, and conserved chromosomal gene clusters. The newly developed user interface supports flexible search capabilities and extensive visualization of the data. |
| H. G. Kaper and T. J. Kaper, "Asymptotic Analysis of Two Reduction Methods for Systems of Chemical Reactions," Physica D 165 (2002), 66-93. Also Preprint ANL/MCS-P912-1001, Oct. 2001. | This article concerns two methods for reducing large systems of chemical kinetics equations, namely, the method of intrinsiclow-dimensional manifolds (ILDMs) due to Maas and Pope [U. Maas and S. B. Pope, Combustion and Flame 88 (1992) 239-264] and an iterative method due to Fraser [S. J. Fraser, J. Chem. Phys. 88 (1988) 4732-4738] and further developed by Roussel and Fraser. Both methods exploit the separation of fast and slow reaction time scales to find low-dimensional manifolds in the space of species concentrations where the long-term dynamics are played out. The analysis is carried out in the context of systems of ordinary differential equations with multiple time scales and geometric singular perturbation theory (GSPT). A small parameter e measures the separation of time scales. The underlying assumption is that the system of equations has an asymptotically stable slow manifold M0 in the limit as e ¯ 0. Then it follows from GSPT that there exists a slow manifold Me for all sufficiently small positive e, which is asymptotically close to M0. It is shown that the ILDM method yields a low-dimensional manifold whose asymptotic expansion agrees with the asymptotic expansion of Me up to and including terms of O(e). At O(e2), an error appears that is proportional to the local curvature of M0; it vanishes if and only if the curvature is zero everywhere. The iterative method generates, term by term, the asymptotic expansion of the slow manifold Me. Starting from M0, the ith application of the algorithm yields the correct expansion coefficient at O(e i-1) invariant. Thus, after l applications, the expansion is accurate up to and including the terms of O(el). The analytical results are illustrated in two examples: a planar system from enzyme kinetics (Michaelis-Menten-Henri) and a model planar system due to Davis and Skodje. |
| L. C. Berselli, G. P. Galdi, T. Iliescu, W. J. Layton, "Mathematical Analysis for the Rational Large Eddy Simulation Model," Preprint ANL/MCS-P914-1001, Oct. 2001 | In this paper we consider the Rational Large Eddy Simulation model recently introduced by Galdi and Layton. We briefly present this model, which (in principle) is similar to others commonly used, and we prove the existence and uniqueness of a class of strong solutions. Contrary to the gradient model, the main feature of this model is that it allows a better control of the kinetic energy. Consequently, to prove existence of strong solutions, we do not need subgrid-scale regularization operators, as proposed by Smagorinsky. We also introduce some breakdown criteria that are related to the Euler and Navier-Stokes equations. |
| R. B. Ross and W. B. Ligon III, "Server-Side Scheduling in Cluster Parallel I/O Systems," in Parallel I/O for Cluster Computing, eds. Christophe Cerin and Hai Jin, Kogan Page Science, Sterling VA, 2004. Also Preprint ANL/MCS-P915-1101, Nov. 2001. | Parallel I/O has become a necessity in the face of performance improvements in other areas of computing systems. Studies have shown that peak performance is infrequently realized, and work in parallel I/O optimization strives to achieve peak performance for applications. In this paper we revisit one area of performance optimization in parallel I/O, that of server-side scheduling of service. With the wide variety of systems and workloads seen today, multiple server-side scheduling algorithms are necessary to match potential workloads. We show through experimentation that performance gains can be seen in practice through the use of alternative scheduling algorithms, but that no single algorithm provides the best performance across the board. Finally we discuss the potential for automatic matching of server-side scheduling algorithms to workloads in real-time. |
| Z. Ernst, B. Fitelson, K. Harris, L. Wos, "A Concise Axiomatization of RM{sub ->}," Bulletin of the Section of Logic (University of Lodz) 30 (2001): 191194. Also Preprint ANL/MCS-P918-0901, Sept. 2001. |
Let R be the system of relevant implication, and let R{sub ->} be its
implicational fragment. R{sub ->} is given by independent
axiom-schema with the rules modus ponens and substitution: (1) Cpp
(2) CCpqCCqrCpr (3) CpCCpqq (4) CCpCpqCpq
|
| Z. Ernst, B. Fitelson, K. Harris, and L. Wos, "Shortest Axiomatizations of Implicational S4 and S5," Notre Dame J. Formal Logic (to appear). Also Preprint ANL/MCS-P919-0201, February 2001. | Shortest possible axiomatizations for the implicational fragments of the modal logics S4 and S5 are reported. Among these axiomatizations is included a shortest single axiom for implicational S4 (which is unprecedented in the literature), and several new shortest single axioms for implicational S5. A variety of automated reasoning techniques were essential to our discoveries. |
| L. A. Freitag and P. E. Plassmann, "Untangling Mapped Quadrilateral Meshes with Concave Boundaries," Preprint ANL/MCS-P920-1201, Dec. 2001. | The generation of a valid computational mesh is an essential step in the solution of many complex scientific and engineering applications. In this paper we present a new, robust algorithm, and several variants, for untangling invalid quadrilateral meshes. The primary computational aspect of the algorithm is the solution of a sequence of local linear programs, one for each interior mesh vertex. We show that the optimal solution to these local subproblems can be guaranteed and found efficiently. We present experimental results showing the effectiveness of this approach for problems where invalid, or negative area, elements can arise near highly concave domain boundaries or boundaries with sharp corners. |
| O. S. Matlin, E. Lusk, and W. McCune, "SPINning Parallel Systems Software," Preprint ANL/MCS-P921-1201, Dec. 2001. | We describe our experiences in using SPIN to verify parts of the Multi Purpose Daemon (MPD) parallel process management system. MPD is a distributed collection of processes connected by Unix network sockets. MPD is dynamic: processes and connections among them are created and destroyed as MPD is initialized, runs user processes, recovers from faults, and terminates. This dynamic nature is easily expressible in the SPIN/PROMELA framework but poses performance and scalability challenges. We present here the results of expressing some of the parallel algorithms of MPD and executing both simulation and verification runs with SPIN. |
| [MCS | Research | Resources | People | Collaboration | Software | Publications | Information] | |||
|