|
|
|
|
|
|
|
|
|
|
| B. M. Averick, R. G. Carter, J. J. More', and
G.-L. Xue, "The MINPACK-2 Test Problem Collection," ANL/MCS-TM-153
(June 1992). |
Optimization software has often been developed
without any specific application in mind. This generic approach has
worked well in many cases, but as we seek the solution of larger and more
complex optimization problems on high-performance computers, the
development of optimization software should take into account specific
optimization problems that arise in a wide range of applications.
This observation was the motivation for the development of the MINPACK-2
test problem collection. Each of the problems in this collection
comes from a real application and is representative of other commonly
encountered problems. There are problems from such diverse fields as
fluid dynamics, medicine, elasticity, combustion, molecular conformation,
nondestructive testing, chemical kinetics, lubrication, and
superconductivity. |
|
|
| B. M. Averick and J. J. More', ``User Guide for the MINPACK-2
Test Problem Collection,'' ANL/MCS-TM-157
(October 1991). |
The Army High Performance Computing Research Center at the
University of Minnesota and the MCS Division at Argonne are collaborating on the
development of the software package MINPACK-2. As part of the project, they are developing
a collection of significant optimization problems to serve as test problems for the
package. This report describes the software associated with the preliminary version of the
MINPACK-2 test problem collection. The discussion centers on the description of subroutine
parameters, but additional information on the implementation of these subroutines is also
provided. The information in this report should be sufficient to use these subroutines for
testing and evaluating software. |
|
|
| A. Baehr, G. Dunham, A. Ginsburg, R. Hagstrom, D. Joerg, T.
Kazic, H. Matsuda, G. Michaels, R. Overbeek, K. Rudd, C. Smith, R. Taylor, K. Yoshida, and
D. Zawada, ``An Integrated Database to Support Research on Escherichia coli, ANL-92/1 (January
1992). |
Logic programming was used to design and implement a
prototype database of genomic information for the model bacterial organism E. coli. This
report presents the fundamental database primitives that can be used to access and
manipulate data relating to the E. coli genome. The present system, combined with a
tutorial manual, provides immediate access to the integrated knowledge base for E. coli
chromosome data. It also serves as the foundation for development of more user-friendly
interfaces that have the same retrieval power and high-level tools to analyze complex
chromosome organization. |
|
|
| C. Bischof, G. Corliss, and A. Griewank, ``ADIFOR Exception
Handling,'' ADIFOR Working Note #3, ANL/MCS-TM-159
(January 1992). |
This paper addresses the detection and handling of exceptions
in ADIFOR. It is an exception in the ADIFOR-generated code to evaluate a function at a
point at which the function may not be mathematically differentiable. When an exception is
detected by tests written into the ADIFOR-generated code, an error handler is called. The
error handler prints an error message (optionally), halts execution (optionally), and
returns a value that allows the user's client program to detect that a requested
derivative is not available. Code is included for all of the necessary Fortran intrinsic
functions and for the error handler. |
|
|
| C. Bischof, G. Corliss, and A. Griewank, ``Hybrid Evaluation
of Second Derivatives in ADIFOR,'' ADIFOR Working Note #8, ANL/MCS-TM-166 (May
1992). |
Many algorithms for scientific computation require second- or
higher-order partial derivatives, which can be efficiently computed by propagating a set
of univariate Taylor series. This paper describes how to implement second-order mixed
partial derivative computations in ADIFOR, a Fortran-to-Fortran source transformation
tool. The source transformations are described, and an example of the transformed code is
given. |
|
|
| C. Bischof and P. Hovland, ``ADIFOR Working Note #2: Using
ADIFOR to Compute Dense and Sparse Jacobians,'' ANL/MCS-TM-158
(January 1992). |
ADIFOR produces code to compute the matrix-matrix product JS,
where J is the Jacobian of the ``function'' with respect to the user-defined independent
variables, and S is the composition of the derivative objects corresponding to the
independent variables. This interface is flexible; by setting S=x, one can compute the
matrix-vector product Jx, or by setting S=I, one can compute the whole Jacobian J. Other
initializations of S allow one to exploit a known sparsity structure of J. This paper
illustrates the proper initialization of ADIFOR-generated derivative codes and the
exploitation of a known sparsity structure of J. |
|
|
| R. Butler and E. Lusk, "User's Guide to the p4 Parallel
Programming System," ANL-92/17 (October
1992, revised 4/94). |
This is both the reference manual and the user's guide for
the p4 parallel programming system. It contains definitions of all functions for
both C and Fortran, exmaples, a brief tutorial, and discussions of related systems. |
|
|
| G. F. Corliss, ADIFOR Working Note #10: ADIFOR Case Study:
VODE + ADIFOR, ANL/MCS-TM-168
(August 1992). |
ADIFOR can be used to generate the Jacobians required by VODE
in a manner that is easy to use. This report provides a template to interface the
ADIFOR-generated code with VODE and shows how the template is used in a sample system of
stiff ordinary differential equations. The ADIFOR-generated code is about ten percent
faster than the hand-coded Jacobian for this example. |
|
|
| G. F. Corliss, ed., Automatic Differentiation Bibliography, ANL/MCS-TM-167 (July
1992). |
This is a 30-page bibliography of work related to automatic
differentiation. |
|
|
| G. Corliss, A. Griewank, T. Robey, and S. Wright, ``Automatic
Differentiation Applied to Unsaturated Flow--ADOL-C Case Study,'' ANL/MCS-TM-162
(April 1992). |
This paper reports results of experiments with variants of
the code dual.c for two-dimensional unsaturated flow in a porous medium. The goal was to
speed the evaluation of derivatives required for a Newton iteration. The authors have
primarily investigated the use of ADOL-C, a C++ tool for automatic differentiation. |
|
|
| I. Foster, M. Henderson, and R. Stevens, organizers,
``Proceedings of the Workshop on Data Systems for Parallel Climate Models, July 15-16,
1991,'' ANL/MCS-TM-169 (September 1992). |
This 258-page report comprises the slides presented at the
Workshop on Data Systems for Parallel Climate Models. The objective of the workshop was to
encourage researchers, systems and model designers, and computer vendors to discuss the
requirements and resources needed to provide high-performance data system support for the
new class of emerging parallel climate models. |
|
|
| I. Foster, H. Kaper, and M. K. Kwong, organizers,
``Proceedings of the Workshop on The Earth's Climate as a Dynamical System, held at
Argonne National Laboratory September 25-26, 1992,'' ANL/MCS-TM-170 (October 1992). |
This report contains the abstracts of the presentations and
copies of the overhead transparencies used by the speakers at a two-day workshop on The
Earth's Climate as a Dynamical System. The workshop was organized as an Argonne Theory
Institute in support of the DOE-sponsored Computer Hardware, Advanced Mathematics, and
Model Physics (CHAMMP) program. Three basic issues were addressed: the construction of
mathematical models of the earth's atmosphere, oceans, and biosphere; the analysis of the
predictive properties of these models; and the computability of climate change on the
basis of these models. |
|
|
| W. Gropp and E. Lusk, ``A Test Implementation of the MPI
Draft Message-Passing Standard,'' ANL-92/47
(December 1992). |
This document describes a running implementation of most of
the Message-Passing Interface (MPI) draft standard. Also included are suggestions that
resulted from discussions in November 1992. |
|
|
| R. Hagstrom, R. Overbeek, and M. Price, ``Users Guide and
Tutorial for PC-GenoGraphics, Version 1,'' ANL-92/45 (December 1992). |
PC-GenoGraphics is a visual database/query facility designed
for reasoning with genomic data. Data are represented to reflect variously accurate
notions of the location of their sites, etc., along the length of the genome. Sequence
data are efficiently stored and queried via a rather versatile language so that entire
sequences of organisms will be treatable as they emerge. Other classes of information,
such as function descriptions, are stored in a relational form, and joint queries relating
these to sequence properties are supported. All queries result in visual responses that
indicate locations along the genome. The results of queries can themselves be promoted to
be queryable objects against which further queries can be launched. |
|
|
| R. Hagstrom, G. S. Michaels, R. Overbeek, M. Price, R.
Taylor, K. Yoshida, and D. Zawada, ``BGenoGraphics for OpenWindows,'' ANL-92/11 (April
1992). |
GenoGraphics is a generic utility for constructing and
querying one-dimensional linear plots. The outgrowth of a request from Dr. Cassandra Smith
for a tool to facilitate her genome mapping research, GenoGraphics' development has
benefited from a continued collaboration with her. Written in Sun Microsystems' Open
Windows environment and BTOL toolkit developed at Argonne, GenoGraphics provides an
interactive, intuitive, graphical interface. Its features include viewing multiple maps
simultaneously, zooming, and querying by mouse clicking. By expediting plot generation,
GenoGraphics gives the scientist more time to analyze data and a novel means for deducing
conclusions. |
|
|
| M. K. Kwong, ``Sweeping Algorithms for Five-Point Stencils
and Banded Matrices,'' ANL/MCS-TM-165 (June
1992). |
This paper records MATLAB experiments implementing the
sweeping algorithms proposed recently to solve five-point stencils arising from the
discretization of PDEs, notably the Ginzburg-Landau equations from the theory of
superconductivity. Algorithms tested included two-direction, multistage, and partial
sweeping. |
|
|
| E. L. Lusk and W. W. McCune, ``An Entry in the 1992 Overbeek
Theorem-Proving Contest,'' ANL/MCS-TM-172
(November 1992). |
At CADE-10, Ross Overbeek proposed a contest to stimulate and
reward work in automated theorem proving. This paper represents an entry, or perhaps a
family of related entries, in the contest. The work won a first prize. |
|
|
| G. W. Pieper, ``Activities of Visitors and Temporary Staff,
1991,'' Informal Report (January 1992). |
In this informal report, many of the MCS Division visitors
summarize their accomplishments during 1991. |
|
|
| G. W. Pieper, ed., ``Research in Mathematics and Computer
Science at Argonne: March 1, 1991, through September 30, 1992,'' ANL-92/37 (October 1992).
|
This report highlights the research activities of the MCS
Division during the period March 1991 through September 1992. |
|
|
| V. L. Winter, G. H. Chisholm, B. T. Smith, and A. J. Wojcik,
``A Formal Model for Verification of Abstract Properties,'' ANL-92/10 (April 1992). |
The authors define a formal method that can be used to verify
that a program written according to a specification s does indeed have the data
dependencies specified by s. |
|
|
| K. Yoshida, C. L. Smith, and R. Overbeek, ``A Primer on Rapid
Prototyping of Genomic Databases,'' ANL/MCS-TM-160 (January 1992). |
This report presents a tutorial on how one might create an
integrated database of genomic information. The paper outlines the required steps for
implementation, gives a brief introduction to Prolog, and discusses the query facility
supported by the system. The goal is to enable researchers to begin constructing their own
biological information system. |
|
|
|
|
|
|
|
| Man Kam Kwong, ``A Dirichlet Problem with Infinite
Multiplicity,'' WSSIAA, Vol. 1 (1992), pp. 393-402. Preprint MCS-P279. Look here
for the DVI version. |
We construct examples of strictly convex functions f on
(-infty , infty) satisfying f'(-infty) < n**2 < f'(infty) such that the Dirichlet
problem u'' + f(u) = h(x) in [0, pi], u(0) = u(pi) = 0, has an infinite number of
solutions, for any choice of h(x). Examples with five solutions were given to settle a
conjecture raised by Lazer and McKenna. We also give a sufficient condition for the number
of solutions to be finite. Bounds for the number of solutions of a Dirichlet problem is of
interest in the study of boundary value problems of semilinear elliptic equations. We
construct examples of strictly convex functions f on (-infty , infty) satisfying
f'(-infty). |
|
|
| C. H. Bischof and X. Sun, ``A Divide-and-Conquer Method for
Tridiagonalizing Symmetric Matrices with Repeated Eigenvalues,''MCS-P286-0192. |
This paper presents a divide-and-conquer tridiagonalization
approach for matrices with repeated eigenvalues. A slight modification of the usual
orthogonal reduction algorithm makes it possible to reveal this structure, which then
leads to parallelism in the form of independent diagonal blocks. Compared with the usual
Householder reduction algorithm, this approach allows significantly more scope for the
exploitation of parallelism and can reduce the number of floating-point operations by up
to 50 percent. The resulting tridiagonal structure can be employed advantageously in
determining range and nullspaces of symmetric matrices with two distinct eigenvalues, one
of which is zero. |
|
|
| E. Lusk, ``Performance Visualization for Parallel Programs,''
MCS-P287-0192. |
This paper describes a set of graphical performance
visualization tools that have been developed at Argonne for increasing one's understanding
of the behavior of parallel programs. |
|
|
| C. Bischof, A. Carle, G. Corliss, and A. Griewank, ``ADIFOR
Working Note #5: ADIFOR: Automatic Differentiation in a Source Translator Environment,'' MCS-P288-0192. |
This paper continues the work reported in Working Note No. 4.
Studies show that ADIFOR-generated codes are competitive with divided-difference
approximations of derivatives. In addition, the source-translation approach to automatic
differentiation may improve the time required to compute derivatives by orders of
magnitude. |
|
|
| I. Foster, ``Information Hiding in Parallel Programs,'' MCS-P290-0292. |
A fundamental principle in program design is to isolate
difficult or changeable design decisions. Application of this principle to parallel
programs requires identification of decisions that are difficult or subject to change, and
the development of techniques for hiding these decisions. In this paper the authors
experiment with three complex applications and identify mapping, communication, and
scheduling as areas in which decisions are particularly problematic. The paper presents
computational abstractions that hide such decisions and shows how these abstractions can
be used to develop elegant solutions to programming problems. In particular, the
abstractions allow the programmer to encode common structures, such as transforms,
reductions, and meshes, as software cells and templates that can be reused in different
applications. |
|
|
| W. McCune and L. Wos, ``Application of Automated Deduction to
the Search for Single Axioms for Exponent Groups,'' Proc. of LPAR-92 (Conference on
Logic Programming and Automated Reasoning), held July 15-20, 1992, St. Petersburg,
Russia. Also preprint MCS-P291-0292. |
This paper presents new results in axiomatic group theory
obtained by using automated deduction programs. The results include single axioms, some
with the identity and others without, for groups of exponents 3, 4, 5, and 7, and a
general form for single axioms for groups of odd exponent. The results were obtained by
using the programs in three separate ways: as a symbolic calculator, to search for proofs,
and to search for counterexamples. The paper also touches on relations between logic
programming and automated reasoning. |
|
|
| M. T. Jones and P. E. Plassmann, ``The Effect of Many-Color
Orderings on the Convergence of Iterative Methods,'' MCS-P292-0292. |
Orderings based on graph colorings can be used to build
scalable, parallel iterative methods. For example, SOR with consistent orderings, SSOR,
and incomplete Cholesky can all be implemented in a scalable manner using graph colorings.
It has been observed experimentally that if, for a fixed problem, the number of colors
used is increased, then the SSOR PCG method will converge faster. This paper proves that
for a model problem the multilevel SOR algorithm with consistent orderings will converge
more quickly as the number of colors used is increased. The authors give a formula for
computing the optimal relaxation parameter and rate of convergence as a function of the
number of colors. They prove a similar but limited result for ICCG. These results allow
the algorithm designer to trade off parallel efficiency for fewer iterations. |
|
|
| I. Foster, R. Olson, and S. Tuecke, ``Productive Parallel
Programming: The PCN Approach,'' MCS-P295-0392. |
This paper describes the PCN programming system, focusing on
those features designed to improve the productivity of scientists and engineers using
parallel supercomputers. These features include a simple notation for the concise
specification of concurrent algorithms, the ability to incorporate existing Fortran and C
code into parallel applications, facilities for reusing parallel program components, a
portable toolkit that allows applications to be developed on a workstation or small
parallel computer and run unchanged on supercomputers, and integrated debugging and
performance analysis tools. Several scientific applications are surveyed and problem
classes identified for which PCN has proved particularly useful. |
|
|
| C. Bischof, G. Corliss, and A. Griewank, ``ADIFOR Working
Note #6: Structured Second- and Higher-Order Derivatives through Univariate Taylor
Series,'' MCS-P296-0392. |
Second- and higher-order derivatives are required by
applications in scientific computation, especially for optimization algorithms. The two
complementary concepts of interpolating partial derivatives from univariate Taylor series
and preaccumulating of ``local'' derivatives form the mathematical foundations for
accurate, efficient computation of second- and higher-order partial derivatives for large
codes. We compute derivatives in a fashion that parallelizes well, exploits sparsity or
other structure frequently found in Hessian matrices, can compute only selected elements
of a Hessian matrix, and computes Hessian times vector products. |
|
|
| H. G. Kaper, M. K. Kwong, and Y. Li, ``Symmetry Results for
Reaction-Diffusion Equations,'' MCS-P299-0392. |
This paper is concerned with symmetry properties of the
solutions of reaction-diffusion equations in a bounded connected domain. |
|
|
| L. Wos, ``The Kernel Strategy and Its Use for the Study of
Combinatory Logic,'' MCS-P300-0492. |
This article presents a powerful new strategy, called the
kernel strategy, for studying fragments of combinatory logic in the context of questions
concerned with fixed point properties. It is shown how the kernel strategy was used to
answer a number of open questions when used in conjunction with the automated reasoning
program OTTER. The paper also offers questions for possible research and provides input
files that might be used for such research. |
|
|
| A. J. Carpenter and R. S. Varga, ``Some Numerical Results on
Best Uniform Polynomial Approximation of x**alpha on [0,1]. |
This paper presents extremely accurate numerical results
obtained in constructive approximation theory. |
|
|
| R. Berrendorf, ``Memory Access in Shared Virtual Memory,''
MCS-P302-0492. |
Shared virtual memory (SVM) is a virtual memory layer with a
single address space on top of a distributed real memory on parallel computers. The author
examines the behavior and performance of SVM running a parallel program with
medium-grained, loop-level parallelism on top of it. A simulator for the underlying
parallel architecture can be used to examine the behavior of SVM more deeply. The
influence of several parameters, such as the number of processors, page size, cold or warm
start, and restricted page replication, is studied. |
|
|
| L. Wos, ``The Problem of Demodulation during Inference Rule
Application,'' MCS-P303-0492. |
The problem posed for research asks one to find criteria for
deciding when to permit and when to avoid demodulation during the application of inference
rules, focusing mainly on hyperresolution, UR-resolution, and hyperparamodulation. Since
these three inference rules admit natural points at which one or more demodulators
(rewrite rules) could be applied--for example, after the removal of a literal or the
replacement of a term--and since the dominant practice is to demodulate only after an
inference rule has been completely applied, the proposed research focuses on an intriguing
alternative. For evaluating a proposed solution to this research problem, problems are
suggested from mathematics, logic, circuit design, program verification, and the world of
puzzles. |
|
|
| L. Wos, ``The Problem of Demodulating across Argument and
Literal Boundaries,'' MCS-P304-0492. |
The problem posed for research asks one to find an
appropriate theory for demodulating across argument and across literal boundaries. Because
demodulation has proved so useful--in most cases, even crucial--to automated reasoning,
extending this concept to permit canonicalization to be applied at the predicate and at
the clause and subclause levels merits exploration. For evaluating a proposed solution to
this research problem, problems from mathematics, logic, program verification, database
inquiry, and the world of puzzles are suggested. |
|
|
| L. Wos, ``The Problem of Demodulator Adjunction,''
MCS-P305-0492. |
The problem proposed for research asks one to find criteria
for deciding which equality unit clauses to adjoin as demodulators (rewrite rules). The
choice of demodulators can materially affect program performance with regard to CPU time
and may affect refutation completeness. For evaluating a proposed solution to this
research problem, problems are suggested from mathematics, logic, circuit design, program
verification, and the world of puzzles. |
|
|
| I. Foster and S. Taylor, ``A Compiler Approach to Scalable
Concurrent Program Design,'' MCS-P306-0492. |
The authors use abstraction in the design of concurrent
programs, in order to separate design decisions concerned with decomposition,
communication, synchronization, mapping, granularity, and load balancing. This paper
describes programming and compiler techniques designed to facilitate this design strategy.
The programming techniques are based on a core programming notation with two important
properties: the ability to separate concurrent programming concerns, and extensibility
with reusable programmer-defined abstractions. The compiler techniques are based on a
simple transformation system together with a set of compilation transformations and
portable run-time support. The transformation, compilation, and run-time system techniques
have been implemented and are incorporated in a public-domain program development toolkit.
This toolkit operates on a wide variety of networked workstations, multicomputers, and
shared-memory multiprocessors. A variety of substantial applications have been developed
using the toolkit, in areas such as climate modeling and fluid dynamics. |
|
|
| M. K. Kwong, ``Sweeping Algorithms for Inverting the Discrete
Ginzburg-Landau Operator,'' MCS-P307-0492. |
The Ginzburg-Landau equations studied here arise in the
modeling of superconductivity. The paper proposes a method similar to the shooting
technique in the numerical solution of ODEs. For small N, the method requires inverting a
full matrix of dimension 2N. When N is large, an iterative procedure that combines partial
sweeping and the technique of divide-and-conquer is appropriate. |
|
|
| J. V. Burke and J. J. More', ``Exposing Constraints,'' MCS-P308-0592. |
This paper develops the identification properties of linearly
constrained optimization algorithms without any nondegeneracy or linear independence
assumptions. The main result shows that the projected gradient converges to zero if and
only if the iterates enter and remain in the face exposed by the negative gradient. This
result generalizes results of Burke and More' obtained for nondegenerate cases. |
|
|
| J. N. Hagstrom, R. Hagstrom, R. Overbeek, M. Price, and L.
Schrage, Maximum Likelihood Genetic Sequence Reconstruction from Oligo Content,
MCS-P309-0592. |
One promising technique for determining long genetic
sequences is sequencing by oligonucleotide content. This technique involves probing a
segment of the unknown multimillion character genetic sequence for the presence or absence
of known short subsequences. The information obtained from such hybridization experiments
may be represented in network form. Network optimization methods may then be applied to
identify the most likely forms of the unknown target sequence. |
|
|
| R. S. Varga and A. J. Carpenter, ``Some Numerical Results on
Best Uniform Rational Approximation of x ^ alpha on [0,1],'' MCS-P310-0592. |
The authors rigorously determined the numbers for six values
of alpha in the interval (0,1), where the numbers were calculated with a precision of at
least 200 significant digits. Two new conjectures in the theory of rational approximation
are presented. |
|
|
| G. F. Corliss, T. Robey, C. Bischof, A. Griewank, and S. J.
Wright, ``Automatic Differentiation for PDEs -- Unsaturated Flow Case Study," in Advances
in Computer Methods for Partial Differential Equations - VII, R. Vichnevetski, D.
Knight, and G. Richter, Eds., IMACS, New Brunswick, pp. 150-156, 1992. Also Preprint MCS-P311-0692. |
The techniques of automatic differentiation are applied to an
example partial differential equation arising from the modeling of unsaturated flow. The
authors conclude that ADOL-C can be successfully applied to large, complex, existing C
codes; that in the cited application, the fastest ADOL-C code takes twice as long as the
best finite difference code; that the reverse mode in this application takes about twice
as long as the forward mode; and that significant efficiencies are possible in the linear
system solver. |
|
|
| C. H. Bischof and X. Sun, ``A Framework for Symmetric Band
Reduction and Tridiagonalization,'' MCS-P312-0692. |
This paper develops a framework for bandwidth reduction and
tridiagonalization algorithms for symmetric banded matrices. The algorithm family includes
the algorithms by Rutishauser and Schwarz, which underlie the EISPACK and LAPACK
implementations, and the algorithm recently proposed by Lang. The new framework leads to
algorithms that require fewer floating-point operations, allow for space-time tradeoffs,
enable the use of block orthogonal transformations, and increase the degree of parallelism
inherent in algorithms. |
|
|
| M. T. Jones and P. E. Plassmann, ``Solution of Large, Sparse
Systems of Linear Equations in Massively Parallel Applications,'' MCS-P313-0692. |
The authors present a general-purpose parallel iterative
solver for large, sparse systems of linear equations. This solver is used in two
applications, a piezoelectric crystal vibration problem and a superconductor model, that
could be solved only on the largest available massively parallel machine. Results obtained
on the Intel DELTA show computational rates of up to 3.25 gigaflops for these
applications. |
|
|
| M. T. Jones and P. E. Plassmann, ``The Efficient Parallel
Iterative Solution of Large Sparse Linear Systems,'' MCS-P314-0692. |
This paper discusses how recent results in parallel graph
heuristics, convergence analysis, and linear algebra have been incorporated into a
general-purpose iterative solver. First the authors show how the method proposed by Luby,
based on determining maximal independent sets, can be modified to run in an asynchronous
manner. A number of graph reduction heuristics are described that are used in the authors'
implementation to improve the individual processor performance. Finally, performance
issues are discussed, from the perspective of two large-scale applications: a
piezoelectric crystal finite-element modeling problem, and a nonlinear optimization
problem to determine the minimum energy configuration of a three-dimensional, layered
superconductor model. |
|
|
| L. Wos, ``Automated Reasoning Answers Open Questions,''
MCS-P315-0792. |
This paper discusses how OTTER has been used to answer open
questions from fields that include ternary Boolean algebra, group theory, equivalential
calculus, and sentential calculus. Open questions and challenge problems are posed. |
|
|
| R. D. C. Monteiro and S. J. Wright, ``A Globally and
Superlinearly Convergent Potential Reduction Interior Point Method for Convex
Programming,'' MCS-P316-0792. |
This paper focuses on an interior point algorithm for convex
programming in which the steps are generated by using a primal-dual affine scaling
technique. A ``local'' variant of the algorithm is shown to have superlinear convergence
with q-order up to (but not including) 2. The technique is embedded in a potential
reduction algorithm, and the resulting method is shown to be globally and superlinearly
convergent. An important feature of the convergence analysis is its use of a novel strict
interiority condition, which generalizes the usual conical neighborhood of the central
path. |
|
|
| C. Bischof and A. Griewank, ``ADIFOR: A Fortran System for
Portable Automatic Differentiation,'' MCS-P317-0792. |
This paper describes the ADIFOR system, a translator that
augments Fortran programs with statements for the computation of derivatives. The paper
gives an overview of the principles underlying ADIFOR and comments on the power of
automatic differentiation for computing derivatives of implicitly defined functions. |
|
|
| W. D. Gropp and D. E. Keyes, ``Domain Decomposition as a
Mechanism for Using Asymptotic Methods,'' MCS-P322-0892. |
This paper summarizes some recent advances in numerical
analysis for PDEs, particularly those in algebraic domain decomposition techniques, and
demonstrates how such methods may be combined with asymptotic methods to provide robust
and effective solvers. |
|
|
| R. M. M. Mattheij and S. J. Wright, ``Parallel Stable
Compactification for ODE with Parameters and Multipoint Conditions,'' MCS-P323-0992. |
Many algorithms for solving ordinary differential equations
with parameters and multipoint side conditions give rise to systems of linear algebraic
equations in which the coefficient matrices have a bordered block diagonal structure. This
paper shows how these problems can be solved by using parallel algorithms based on
stabilized compactification. |
|
|
| I. Foster and J. Michalakes, ``Massively Parallel
Implementation of the Penn State/NCAR Mesoscale Model,'' MCS-P324-0992. |
This paper reports on a project at Argonne to develop the
Massively Parallel Mesoscale Model (MPMM) for climate modeling. MPMM will be functionally
equivalent to the Penn State/NCAR Mesoscale Model but will use a more fine-grained
approach and will use a high-level language that facilitates load balancing, grid nesting,
and coupling with other models. |
|
|
| R. Hagstrom, G. S. Michaels, R. Overbeek, M. Price, and R.
Taylor, ``Overview of the Integrated Genomic Data System (IGD),'' MCS-P325-0992. |
To enable the comparative analysis of the genomes from
different species, the authors have designed and implemented a new prototype database
system, called the Integrated Genomic Database (IGD). IGD incorporates curator tools that
facilitate the incorporation of physical and genetic data, together with the results of
genome organization analysis, into a common database system. |
|
|
| R. G. Carter, ``Fast Numerical Determination of Symmetric
Sparsity Patterns,'' MCS-P326-0992. |
The paper considers a function for which the Jacobian is
symmetric and sparse. The author shows that it is possible to numerically determine
symmetric sparsity patterns using a relatively small number of g evaluations. Numerical
results are shown for n up to 100,000 in which all nonzeros in the Jacobian are correctly
identified in about one-hundredth of the time required to estimate the sparsity structure
by a full finite difference calculation. When a good initial guess for the sparsity
structure is available, numerical results are presented for $n$ up to 500,000, in which
all missing nonzeros are correctly located almost five thousand times faster than would be
possible with a full finite-difference calculation. |
|
|
| I. T. Foster and K. Mani Chandy, ``Fortran M: A Language for
Modular Parallel Programming,'' J. of Parallel and Distributed Computing 26
(1995), pp. 24-35. Also preprint MCS-P327-0992. |
Fortran M is a small set of extensions to Fortran 77 that
supports a modular approach to the design of message-passing programs. Its features
include modularity, guaranteed deterministic execution, architecture independence, and
efficiency. |
|
|
| A. Cherry, M. W. Henderson, W. K. Nickless, R. Olson, and G.
Rackow, ``Pass or Fail: A New Test for Password Legitimacy,'' MCS-P328-1092. |
While other programs check for bad passwords after the fact,
it is important to have good passwords at all times, not just after the latest Crack run.
To this end, the authors have modified Larry Wall's Perl password program and added, among
other features, the ability to check a sorted list of all the ``bad passwords'' that Crack
will generate, given all the dictionaries that were available to the authors (10 megabytes
of unique words). The combination of improvements has turned publicly available code into
a powerful tool that can aid sites in the maintenance of local security. |
|
|
| F. V. Atkinson, H. G. Kaper, and M. K. Kwong, ``Asymptotics
of a Free Boundary Problem,'' MCS-P329-1092. |
This article is concerned with free boundary problems for a
reaction-diffusion equation. The focus is on radial solutions. |
|
|
| S. Wright, ``An Infeasible Interior Point Algorithm for
Linear Complementarity Problems,'' MCS-P331-1092. |
This paper discusses a polynomial and Q-quadratically
convergent algorithm for linear complementarity problems that does not require feasibility
of the initial point or the subsequent iterates. The algorithm is a modification of the
linearly convergent method of Zhang and requires the solution of at most two linear
systems with the same coefficient matrix at each iteration. |
|
|
| C.-T. Pan and P. T. P. Tang, ``Bounds on Singular Values
Revealed by QR Factorizations,'' MCS-P332-1092. |
A pair of dual concepts are introduced: pivoted blocks and
reverse pivoted blocks. These blocks are the outcome of a special column pivoting strategy
in QR factorization. The main result here is that under such a column pivoting strategy,
the QR factorization of a given matrix can give tight estimates on any two a priori chosen
consecutive singular values of that matrix. In particular, a rank-revealing QR
factorization is guaranteed when the two chosen consecutive singular values straddle a gap
in the singular value spectrum that gives rise to the rank degeneracy of the given matrix.
The pivoting strategy, called cyclic pivoting, can be viewed as a generalization of
Golub's column pivoting and Stewart's reverse column pivoting. Numerical experiments
confirm the tight estimates that the theory asserts. |
