|
|
|
|
|
|
|
|
|
| B. M. Averick and J. J. More', ``User Guide for the MINPACK-2
Test Problem Collection,'' ANL/MCS-TM-157
(October 1991). See also ANL/MCS-TM-153
(June 1992 - 1992 abstracts) |
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. |
|
|
| C. Bischof and J. Hu, "Utilities for Building and Optimizing
a Computational Graph for Algorithmic Decomposition,'' Technical Memorandum ANL/MCS-TM-148
(January 1991). |
This document describes a utility to construct and evaluate
an optimized execution graph from the tapefile generated by the ADOL-C automatic
differentiation software. It describes the format of the ADOL-C tapefile, the data
structures used in building and storing the graph, and the optimizations performed in
transforming the computation trace stored in the tape into an efficient graph
representation. In particular, we eliminate assignments, increase granularity by
``hoisting'' chains of unary operations, and remove so-called dead roots -- intermediate
values that have no influence on the dependent. Examples show that the optimized graphs
contain up to 50% fewer nodes than a graph that would be an exact analogue of the ADOL-C
tape. We also describe an attempt at generating compiled code for the graph evaluation as
an alternative to interpretative approaches to evaluating the graph. |
|
|
| I. Foster and E. Tick, ``Proceedings of the Workshop on
Compilation of (Symbolic) Languages for Parallel Computers,'' ANL-91/34 (November 1991). |
This report comprises the abstracts and papers for the talks
presented at the Workshop on Compilation of (Symbolic) Languages for Parallel Computers
held October 31-November 1, 1991, in San Diego. The goal of the workshop was to bring
together researchers from different disciplines with common problems in compilation. In
particular, the organizers wished to encourage interaction between researchers working in
compilation of symbolic languages and those working on compilation of conventional,
imperative languages. This workshop was a first step at opening up discussions and
contributing to the solution of problems in language compilation for parallel computers. |
|
|
| I. Foster and S. Tuecke, ``Parallel Programming with PCN,'' ANL-91/32, rev. 1
(December 1991). |
This document provides all the information required to
develop parallel programs with the PCN programming system. It includes both tutorial and
reference material. It also presents the basic concepts that underlie PCN, particularly
where these are likely to be unfamiliar to the reader, and provides pointers to other
documentation on the PCN language, programming techniques, and tools. |
|
|
| Ian Foster, Steve Tuecke, and Stephen Taylor, ``A Portable
Run-Time System for PCN,'' ANL/MCS-TM-137, Rev.
1 (December 1991). |
This report describes a run-time system to support Program
Composition Notation (PCN), a high-level concurrent programming notation. The run-time
system is described in terms of an abstract machine. We specify an abstract architecture
that represents the state of a PCN computation and executes abstract machine instructions
that encode tests on or modifications to the computation state. Programs to be executed on
the abstract machine are encoded as sequences of abstract machine instructions. The
abstract machine may be implemented by an emulator written in a low-level language.
Alternatively, sequences of abstract machine instructions may be further compiled to
machine code. The run-time system is designed to run on uniprocessors, multiprocessors,
and multicomputers. |
|
|
| William W. McCune, ``Proofs for Group and Abelian Groupo
Single Axioms,'' ANL/MCS-TM-156,
October 1991. |
This memorandum serves as a companion to the paper
"Single axioms for groups and Abelian groups with various operations." That
paper presents single axioms for groups and Abelian groups in terms of {product, inverse},
{division}, {double division, identity}, {double division, inverse}, {division, identity},
and {division, inverse}. Proofs that were omitted from that paper are presented here. |
|
|
| Robert Olson, ``Using host-control,'' ANL/MCS-TM-154
(October 1991). |
The utility host-control conveniently configures a
set of machines for use with the networked version of PCN. It enables the user to specify
exactly how PCN is to be run on each node, and it allows for easy control of runaway PCN
nodes. This document provides the information needed for a new user to get started with host-control.
It also provides the advanced user with the information needed to get around more
difficult problems in a networked PCN configuration. |
|
|
| R. C. Taylor, ``Automated Insertion of Sequences into a
Ribosomal Alignment: An Application of Computational Linguistics in Molecular Biology,''
ANL-91/29 (November 1991). |
This thesis involved the construction of (1) a grammar that
incorporates knowledge on base invariancy and secondary structure in a molecule, and (2) a
parser engine that uses the grammar to position bases into the structural subunits of the
molecule. These concepts were combined with a novel pinning technique to form a tool that
semi-automates insertion of a new species into the alignment for the 16S rRNA molecule (a
component of the ribosome) maintained by Dr. Carl Woese's group at the University of
Illinois at Urbana. The tool was tested on species extracted from the alignment and on a
group of entirely new species. The results were very encouraging, and the tool should be
of substantial aid to the curators of the 16S alignment. The construction of the grammar
was automated, allowing application of the tool to alignments for other molecules. The
logic programming language Prolog was used to construct all programs involved. The
computational linguistics approach used here was found to be a useful way to attack the
problem of insertion into an alignment. |
|
|
|
|
|
|
|
| Christian Bischof, Andreas Griewank, and David Juedes,
"Exploiting Parallelism in Automatic Differentiation," ACM International
Conference on Supercomputing, June 17-21, 1991, Cologne, Germany. Also Preprint MCS-P204-0191. |
The numerical methods employed in the solution of many
scientific computing problems require the computation of first- or second-order
derivatives of a function f: R^n -> R^m. We present an approach
that, given a serial C program for the computation of f(x), derives a parallel
execution schedule for the computation of f and its derivatives in a completely
automatic fashion. This is achieved by overloading the computation of f(x) in C++
to obtain a trace of the computations to be performed and then transforming this trace
into a data flow graph for the computation of f(x). In addition to the
computation of f(x), this graph also allows us to exactly and inexpensively
compute derivatives of f by the repeated use of the chain rule. Parallelism is
exploited in two ways: rows or columns of derivative matrices can be computed by independent
passes through the computational graph, and parallelism within the processing of this
computational graph can be exploited by processing independent subgraphs concurrently. We
present experimental results that show that good performance on shared-memory machines can
be obtained by using a graph interpreter approach. We then present some ideas that are
currently under development for improving computational granularity and for implementing
parallel automatic differentiation schemes in a portable and more efficient fashion. |
|
|
| Mark T. Jones and Paul E. Plassmann, ``An Improved Incomplete
Cholesky Factorization,'' ACM Transactions on Mathematical Software 21, no. 1
(March 1995), pp. 5-17. Also preprint MCS-P206-0191. Look
here for a DVI
version. |
Incomplete factorization has been shown to be a good
preconditioner for the conjugate gradient method on a wide variety of problems. It is well
known that allowing some fill-in during the incomplete factorization can significantly
reduce the number of iterations needed for convergence. Allowing fill-in, however,
increases the time for the factorization and for the triangular system solutions.
Additionally, it is difficult to predict a priori how much fill-in to allow and how to
allow it. the unpredictability of the required storage/work and the unknown benefits of
the additional fill-in make such strategies impractical to use in many situations. In this
article we motivate, and then present, two ``black-box'' strategies that significantly
increase the effectiveness of incomplete Cholesky factorization as a preconditioner. These
strategies require no parameters from the user and do not increase the cost of the
triangular system solutions. Efficient implementations for these algorithms are described.
These algorithms are shown to be successful for a variety of problems from the
Harwell-Boeing sparse matrix collection. |
|
|
| William W. McCune, ``Single Axioms for the Left Group and
Right Group Calculi,'' Notre Dame Journal of Formal Logic 34, no. 1 (Winter
1993), pp. 132-139. Also preprint MCS-P219-0391. |
This article is on axiomatizations of the left group calculus
and of the right group calculus. The axiomatizations use modus ponens rather than equality
substitution as the inference rule. The structures being axiomatized are ordinary free
group, and the sole operation is division. Previous axiomatizations are due to J. A.
Kalman. The article contains single axioms and other simple axiomatizations of the two
calculi. An automated theorem-proving program was used extensively to find candidate
axiomatizations and to find proofs that candidates are in fact axiomatizations. |
|
|
| William W. McCune, ``Automated Discovery of New
Axiomatizations of the Left Group and Right Group Calculi,'' J. of Automated Reasoning
9 (1992), pp. 1-24. Also preprint MCS-P220-0391. |
This paper shows how the automated theorem-proving program
OTTER was used to discover new axiomatizations, including single axioms, for the left
group and right group calculi. J. A. Kalman's original axiomatizations of the two calculi
each contain five axioms. Three of Kalman's axioms (L1, L4, and L5) for the left group
calculus were shown to be dependent on the remaining two axioms. Four of Kalman's axioms
(R1, R3, R4, and R5) for the right group calculus were shown to be dependent on the
remaining axiom. Alternative simpler axiomatizations were discovered for both calculi,
including a single axiom for the left group calculus and five additional single axioms for
the right group calculus. The program OTTER was vital in discovering candidate
axiomatizations as well as in finding proofs of new axiomatizations. All of the relevant
OTTER proofs are included. |
|
|
| Mark T. Jones and Paul E. Plassmann, ``Algorithm 740: Fortran
Subroutines to Compute Improved Incomplete Cholesky Factorizations,'' ACM Transactions
on Mathematical Software 21, no. 1 (March 1995), pp. 18-19. Also preprint
MCS-P221-0391. |
Efficient and reliable code to compute incomplete Cholesky
factors of sparse matrices for use as preconditioners in a conjugate gradient algorithm is
described. This code implements two recently developed, improved incomplete factorization
algorithms. An efficient implementation of the standard incomplete Cholesky factorization
is also included. |
|
|
| Christian H. Bischof and Ping Tak Peter Tang,
"Generalizing Incremental Condition Estimation," J. Numer. Linear Algebra
1, no. 2 (1992), pp. 149-163. Also preprint MCS-P233-0491. |
This paper presents a generalization of incremental
condition estimation, a technique for tracking the extremal singular values of a
triangular matrix. While the original approach allowed for the estimation of the largest
or smallest singular value, the generalized scheme allows for the estimation of any
number of extremal singular values. For example, we can derive estimates for the
three smallest singular values and the corresponding singular vectors at the same time.
When estimating k singular values at the same time, the cost of one step of our
generalized scheme on an nxn matrix is O(n k^2).
Experimental results show that the resulting estimator does a good job of estimating the
extremal singular values of triangular matrices and that, in particular, it leads to an
inexpensive, yet very accurate and robust condition estimator. |
|
|
| Christian H. Bischof, "Issues in Parallel Automatic
Differentiation," in Automatic Differentiation of Algorithms, A. Griewank
and G. Corliss, Eds., SIAM, Philadelphia, pp. 100-113, 1991. Also Preprint MCS-P235-0491. |
This paper shows how first-order derivatives can be computed
in parallel by considering the computational graph that underlies the evaluation of the
target function. The graph can be generated efficiently from the ADOL-C computational
trace and can be used to automatically deduce the structure of the Jacobian matrix and
compute the Jacobian using the reverse mode of automatic differentiation. By employing
well-known graph-coloring techniques, one can dramatically decrease the number of reverse
passes required. The resulting implementation performs well on the Sequent Symmetry and
BBN Butterfly TC2000 shared-memory multiprocessors. Lastly, we look at the problems that
must be tackled to make automatic differentiation a commonplace computing tool, and to
allow for efficient implementations on high-performance computers. In our view, the key
lies in finding better ways to incorporate user and/or compile-time information about the
behavior of the program into the automatic differentiation approach. |
|
|
| Christian H. Bischof, "LAPACK: Linear Algebra Software
for Supercomputers," Proc. 2nd ODIN Symposium, A. Schreiner and W. Ewinger,
Eds., pp. 101-120, 1991. Also preprint MCS-P236-0491. |
This paper presents an overview of the LAPACK library, a
portable, public-domain library to solve the most common linear algebra problems. This
library provides a uniformly designed set of subroutines for solving systems of
simultaneous linear equations, least-squares problems, and eigenvalue problems for dense
and banded matrices. We elaborate on the design methodologies incorporated to make the
LAPACK codes efficient on today's high-performance architectures. In particular, we
discuss the use of block algorithms and the reliance on the Basic Linear Algebra
Subprograms (BLAS). We present performance results that show the suitability of the LAPACK
approach for vector uniprocessors and shared-memory multiprocessors. We also address some
issues that have to be dealt with in tuning LAPACK for specific architectures. Lastly, we
present results that show that the LAPACK software can be adapted with little effort to we
distributed-memory environments, and discuss future efforts resulting from this project. |
|
|
| W. McCune and L. Wos, ``Experiments in Automated Deduction
with Condensed Detachment,'' Proc. of 11th International Conf. on Automated Deduction
(CADE 11), held June 15-18, 1992, Saratoga Springs, NY. Also preprint MCS-P237-0491. |
This paper contains 112 problems that use condensed
detachment in nine different logic calculi: three versions of the two-valued sentential
calculus, the many-valued sentential calculus, the implicational calculus, the
equivalential calculus, the R calculus, the left group calculus, and the right group
calculus. Results of experiments with the theorem-proving program OTTER are presented.
Each problem was run with at least three strategies: (1) a basic strategy, (2) a strategy
with a more refined method for selecting clauses on which to focus, and (3) a strategy
that uses the refined selection mechanism and deletes deduced formulas according to some
simple rules. Two new features of OTTER are also presented: the refined method for
selecting the next formula on which to focus, and a method for controlling memory usage. |
|
|
| J. N. Lyness and E. de Doncker, ``Quadrature Error
Expansions--Part II: The Full Corner Singularity,'' MCS-P248-0791. |
This paper continues the work of Part I, treating in detail
the theory of numerical quadrature over a square. The extreme case treated here is one in
which the integrand function has a full-corner algebraic singularity. |
|
|
| Christian H. Bischof and Per Christian Hansen, "A Block
Algorithm for Computing Rank-Revealing QR Factorizations," Numerical Algorithms
2 (3-4), (1992), pp. 371-392. Also preprint MCS-P251-0791. |
We present a block algorithm for computing rank-revealing QR
factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block
generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm
reveals the rank by peeling off small singular values one by one, our algorithm identifies
groups of small singular values. In our block algorithm, we use incremental condition
estimation to compute approximations to the nullvectors of the matrix. By applying another
(in essence also rank-revealing) orthogonal factorization to the nullspace matrix such
created, we can then generate triangular blocks with small norm in the lower right part of
E. This scheme is applied in an iterative fashion until the rank has been
revealed in the (updated) QR factorization. We show that the algorithm produces the
correct solution, under very weak assumptions for the orthogonal factorization used for
the nullspace matrix. We then discuss issues concerning an efficient implementation of the
algorithm and present some numerical experiments. Our experiments show that the block
algorithm is reliable and successfully captures several small singular values, in
particular in the initial block steps. Our experiments confirm the reliability of our
algorithm and show that the block algorithm greatly reduces the number of triangular
solves and increases the computational granularity of the RRQR computation. |
|
|
| E. L. Lusk and W. W. McCune, ``Experiments with ROO, a
Parallel Automated Deduction System,'' MCS-P254-0791. |
This paper provides a close look at the behavior of ROO, a
parallel theorem prover, on a wide variety of theorem-proving problems. The problems show
ROO at its best and at its worst. The authors note that the nondeterministic nature of
parallel algorithms means that consecutive runs of the same input file, on the same number
of processes, can produce different results. The question of stability and reproducibility
of the results reported is addressed. |
|
|
| I.-B. Tjoa and L. T. Biegler, ``A Reduced Successive
Quadratic Programming Strategy for Errors-in-Variables Estimation,'' MCS-P255-0891. |
In this study the authors develop a tailored nonlinear
programming strategy for errors-in-variables (EVM) problems. The method is based on a
reduced Hessian approach to successive quadratic programming, but with the decomposition
performed separately for each data set. This leads to the elimination of all variables but
the model parameters, which are determined by a quadratic programming coordination step.
In this way the computational effort remains linear in the number of data sets. Moreover,
the approach directly incorporates constraints on the model parameters. The approach is
demonstrated on five example problems with up to 102 degrees of freedom. Compared with
general-purpose NLP algorithms, large improvements in computational performance are
observed. |
|
|
| J. S. Logsdon and L. T. Biegler, ``Reduced Gradient
Strategies for Dynamic Optimization Problems: Feasible and Infeasible Path Variations,''
MCS-P256-0891. |
Recently, strategies have been developed to solve dynamic
simulation and optimization problems simultaneously. In this paper, the authors develop a
decomposition strategy that can be used for the accurate solution of optimal control
problems. Two types of algorithm are investigated: a reduced gradient approach in which
the state variables are implicitly eliminated through repeated solution of the collocation
equations, and an infeasible path approach that leads to much faster performance.
Nonlinear problems with up to 5500 variables are solved efficiently. |
|
|
| W. Gropp, ``Parallel Computing and Domain Decomposition,'' MCS-P257-0891. |
This paper discusses some of the issues in designing and
implementing a parallel domain decomposition algorithm. A framework for evaluating the
cost of parallelism is introduced and applied to answering questions such as which and how
many processors should solve global problems and what impact load balancing has on the
choice of domain decomposition algorithm. The sources of performance bottlenecks are
discussed. This analysis suggests that domain decomposition techniques will be effective
on high-performance parallel processors and on networks of workstations. |
|
|
| J. N. Lyness and T. Sorevik, ``An Algorithm for Finding
Optimal Integration Lattices of Composite Order,'' MCS-P258-0891. |
This paper describes an algorithm that can be used to
determine optimal integration lattices. |
|
|
| G.-Q. Chen and J.-G. Liu, ``A Nonconservative Scheme for
Isentropic Gas Dynamics,'' MCS-P260-0891. |
A second-order nonconservative scheme for the system of
isentropic gas dynamics is constructed to capture the physical invariant regions, to treat
the vacuum singularity, and to control the local entropy from dramatically increasing near
shock waves. Convergence of this scheme to an entropy solution is established for the
Cauchy problem with L^inf initial data, by analyzing the entropy dissipation
measures. This scheme can be applied to general systems of conservation laws. |
|
|
| S. J. Wright, ``Identifiable Surfaces in Constrained
Optimization,'' Preprint MCS-P261-0891. |
A new concept in Euclidean space is introduced. The author
shows how the smoothness of these surfaces is related to the smoothness of the projection
operator, and he presents finite identification results for certain algorithms for
minimization of a function over this set. The work uses a partially geometric view of
constrained optimization to generalize previous finite identification results. |
|
|
| B. M. Averick and J. M. Ortega, ``Fast Solution of Nonlinear
Poisson-Type Equations,'' Preprint MCS-P262-0991. |
This paper is concerned with the solution of nonlinear
Poisson-type equations. A change of variable is made that effectively reduces the solution
of such equations to solving a linear Poisson equation followed by a series of
one-dimensional nonlinear equations. Comparison with other methods shows the new method to
be competitive. |
|
|
| C. Bischof, A. Carle, G. Corliss, A. Griewank, and P.
Hovland, ``ADIFOR Working Note #1: ADIFOR--Generating Derivative Codes from Fortran
Programs,'' Scientific Programming, Vol. 1 (1992), pp. 11-29. Also Preprint MCS-P263-0991. Look
here for the DVI
version. |
The numerical methods employed in the solution of many
scientific computing problems require the computation of a function f : R**n ->
R**m. Both the accuracy and the computational requirements of the derivative
computation are usually of critical importance for the robustness and speed of the
numerical solution. Automatic Differentiation of FORtran (ADIFOR) is a source
transformation tool that accepts Fortran 77 code for the computation of a function and
writes portable Fortran 77 code for the computation of the derivatives. In contrast to
previous approaches, ADIFOR views automatic differentiation as a source transformation
problem. ADIFOR employs the data analysis capabilities of the ParaScope Parallel
Programming Environment, which enables us to handle arbitrary Fortran 77 codes and to
exploit the computational context in the computation of derivatives. Experimental results
show that ADIFOR can handle real-life codes and that ADIFOR-generated codes are
competitive with divided-difference approximations of derivatives. In addition, studies
suggest that the source transformation approach to automatic differentiation may improve
the time to compute derivatives by orders of magnitude. |
|
|
| I-L. Chern and I. Foster, ``Design and Parallel
Implementation of Two Numerical Methods for Modeling the Atmospheric
Circulation,''MCS-P264-0991. |
Two methods are proposed for simulating on parallel
supercomputers the time evolution of the primitive equations used in atmospheric
circulation models. The first is a control volume method on an icosahedral-hexagonal grid
on the sphere. This method has a number of computational advantages compared with other
methods used for the same purpose, including a nearly uniform resolution on the sphere, no
pole problem, and reduced global data communication requirements. The second method is a
composite-mesh, second-order Godunov method. This also avoids global communication and the
pole problem and, in addition, is able to handle discontinuities. The authors perform
several simulations to demonstrate the convergence of the two methods. They also outline
the techniques used to achieve parallel implementations and report on computational
experiments that demonstrate the methods' suitability for parallel execution. |
|
|
| D. W. Juedes, ``A Taxonomy of Automatic Differentiation
Tools,'' MCS-P265-0991. |
Many of the current automatic differentiation (AD) tools have
similar characteristics. Unfortunately, the similarities between these various AD tools
often cannot be easily ascertained by reading the corresponding documentation. To clarify
this situation, the author has devised a taxonomy of AD tools. The taxonomy places AD
tools into the Elemental, Extensional, Integral, Operational, and Symbolic classes. This
taxonomy is used to classify 29 AD tools. Each tool is examined individually with respect
to the mode of differentiation and the degree of derivatives computed. A list detailing
the availability of the surveyed AD tools is provided in the Appendix. |
|
|
| S. J. Wright, ``A Collection of Problems for Which Gaussian
Elimination with Partial Pivoting Is Unstable,'' MCS-P266-0991. |
A significant collection of two-point boundary value problems
is shown to give rise to linear systems of algebraic equations on which Gaussian
elimination with row partial pivoting is unstable when standard solution techniques are
used. |
|
|
| A. Griewank and S. Reese, ``On the Calculation of Jacobian
Matrices by the Markowitz Rule,'' MCS-P267-1091. |
Automatic differentiation may be applied to evaluate first
and higher derivatives of any vector function that is defined as the composition of easily
differentiated elementary functions, typically in the form of a computer program. The more
general task of efficiently evaluating Jacobians or other derivative matrices leads to a
combinatorial optimization problem, which is conjectured to be NP-hard. This paper
examines this vertex elimination problem and solves it approximately, using a greedy
heuristic. Numerical experiments show the resulting Markowitz scheme for Jacobian
evaluation to be more efficient than column-by-column or row-by-row evaluation using the
forward or reverse mode, respectively. |
|
|
| J. D. F. Cosgrove, J. C. Diaz, and A. Griewank, ``Approximate
Inverse Preconditioning for Sparse Linear Systems,'' MCS-P268-1091. |
This paper presents a special procedure for the adaptive
construction of sparse approximate inverse preconditionings for general sparse linear
systems. The approximate inverses are based on minimizing a consistent norm of the
difference between the identity and the preconditioned matrix. The analysis provides
positive definiteness and condition number estimates for the preconditioned system under
certain circumstances. The authors show that for the 1-norm, restricting the size of the
difference matrix below 1 may require dense approximate inverses. However, this
requirement does not hold for the 2-norm, and similarly reducing the Frobenius norm below
1 does generally require that much fill-in. Moreover, for the Frobenius norm, the
calculation of the approximate inverses yields naturally column-oriented parallelism.
General sparsity can be exploited in a straightforward fashion. Numerical criteria are
considered for determining which columns of the sparse approximate inverse require
additional fill-in. Sparse algorithms are discussed for the location of potential fill-in
within each column. Results using a minimum-residual-type iterative method are presented
to illustrate the potential of the method. |
|
|
| J. N. Lyness and P. Keast, ``Application of the Smith Normal
Form to the Structure of Lattice Rules,'' MCS-P269-0891. |
Two independent approaches to the theory of the lattice rule
have been exploited at length in the literature. In this paper a close connection between
these approaches is demonstrated. This fact may be used to provide a straightforward
solution to the previously intransigent problem of identifying and removing a repetition
in the general t-cycle form. |
|
|
| W. W. McCune, ``Single Axioms for Groups and Abelian Groups
with Various Operations,'' J. of Automated Reasoning 10 (1993), pp. 1-13. Also
preprint MCS-P270-1091. |
This paper summarizes the results of an investigation into
single axioms for groups, both ordinary and Abelian, with each of the following six sets
of operations: {product, inverse}, {division}, {double division, identity}, {double
division, inverse}, {division, identity}, and {division, inverse}. In all but two of those
twelve theories, we present either the first single axioms known to us or single axioms
shorter than those previously known to us. An automated theorem-proving program was used
extensively to construct sets of candidate axioms and to search for and find proofs that
given candidate axioms are in fact single axioms. |
|
|
| J. N. Lyness, ``On Handling Singularities in Finite
Elements,'' Numerical Integration, T. O. Espelid and A. Genz (eds.), Kluwer
Academic Publishers, pp. 219-233. Also preprint MCS-P271. |
In the practice of the Boundary Element Method, a basic task
involves the quadrature over a quadrilateral or triangle of an integrand function which
has a singularity of known form at a vertex. A not uncommon situation is that this
quadrature has already been studied in depth for the standard triangle or the square, and
all that is now necessary is to apply the known results in the context of a different
triangle or parallelogram, one that has been obtained from the standard region by an
affine transformatio. It can be surprising to someone who has not done it himself, how
difficult this task can be. This article provides an account of how easy it is to be
misled in this area. Besides describing an apparently cost effective approach which turns
out to be a disaster, I discuss some of the advantages and disadvantages of using rules
based on extrapolation either as an alternative to, or in conjunction with Gaussian rules.
This article is anecdotal in character. |
|
|
| G. Kirlinger and G. F. Corliss, ``On Implicit Taylor Series
Methods for Stiff Odes,'' MCS-P272-1191. |
Several versions of implicit Taylor series methods (ITSM) are
presented and evaluated. Criteria for the approximate solution of ODEs via ITSM are given.
Some ideas, motivations, and remarks on the inclusion of the solution of stiff ODEs are
outlined. |
|
|
| R. M. Corless and G. F. Corliss, ``Rationale for Guaranteed
ODE Defect Control,'' MCS-P273-1191. |
The authors introduce a modification of existing algorithms
that allows easier analysis of numerical solutions of ordinary differential equations.
They relax the requirement that the specified problem be solved, and instead solve a
``nearby'' problem exactly, in Wilkinson's tradition of backward error analysis. The
precise meaning of ``nearby'' is left to the user. This inexpensive algorithm sublimates
the well-known difficulties associated with the propagation of accumulated error and
avoids the difficulty of exponential growth of inclusion widths associated with interval
techniques. No claim is made for the accuracy with which the specified problem is solved.
It is shown that often no such claim is necessary. |
|
|
| C. H. Bischof, B. N. Datta, and A. Purkayastha, ``A Parallel
Algorithm for the Multi-Input Sylvester-Observer Equation,'' MCS-274-1191. |
This paper presents a new algorithm for solving the
multi-input Sylvester-Observer equation. The algorithm embodies two main computational
phases: the solution of a series of independent equation systems, and a series of
matrix-matrix multiplications. As such, the algorithm is well suited for a parallel
machine. By reducing the coefficient matrix to lower Hessenberg form, one can implement
the algorithm efficiently, with few floating-point operations and little workspace.
Experimental results on the CRAY Y-MP and the Siemens S600/10 are presented that confirm
the efficiency of the algorithm. |
|
|
| E. Lusk and L. Wos, ``Benchmark Problems in Which Equality
Plays the Major Role,'' MCS-P275-1191. |
To facilitate research using paramodulation and to provide
test problems for evaluating other approaches to equality-oriented reasoning, this article
presents a set of benchmark problems in which equality plays the dominant role. The test
problems are taken from group theory, ring theory, Robbins algebra, combinatory logic, and
other areas. For each problem there are included appropriate clauses and comment as to its
status with regard to provability by an unaided automated reasoning program. Also included
are various open questions. |
|
|
| J. N. Lyness and T. Sorevik, ``Lattice Rules by Component
Scaling,'' MCS-P276-1191. Look
here for the DVI
version. |
This paper introduces a theory of rectangular scaling of
integer lattices. This may be used to construct families of lattices. The authors
determine the relation between the Zaremba index of various members of the same family. If
one member of a family has a high order, it appears that some other family members of
higher order may have extraordinarily high indices. The authors have applied a technique
based on this theory to lists of good lattices. They have constructed lists of excellent,
previous unknown lattices of high order in three and four dimensions. |
|
|
| C. Bischof, A. Carle, G. Corliss, A. Griewank, and P.
Hovland, ``ADIFOR Working Note No. 4: ADIFOR: Fortran Source Translation for Efficient
Derivatives,'' MCS-P278-1291
(February 1992). Look here for DVI version. |
The numerical methods employed in the solution of many
scientific computing problems require the computation of derivatives. Both the accuracy
and the computational requirements of the derivative computation are usually of critical
importance for the robustness and speed of the numerical method. ADIFOR is a source
translation tool implemented by using the data abstractions and program analysis
capabilities of the ParaScope Parallel Programming Environment. ADIFOR accepts arbitrary
Fortran 77 code defining the computation of a function and writes portable Fortran 77 code
for the computation of its derivatives. In contrast to previous approaches, ADIFOR views
automatic differentiation as a process of source translation that exploits computational
context to reduce the cost of derivative computations. Experimental results show that
ADIFOR can handle real-life codes, providing exact derivatives with a running time that is
competitive with the standard divided-differences in certain cases. The computational
scientist using ADIFOR is freed from worrying about the accurate and efficient computation
of derivatives, even for complicated ``functions'' and hence is able to concentrate on the
more important issues of algorithm design or system modeling. |
|
|
| J. Zhang and L. Wos, ``Automated Reasoning and Enumerative
Search, with Application to Mathematics,'' MCS-P280-1291. |
More and more mathematical problems are being solved with the
aid of computers. This paper examines the applications of reasoning and search programs to
mathematics. It is also shown that the combination of these two techniques can solve
mathematical problems more effectively. |
|
|
| J. Garner, M. Spanbauer, R. Benedek, K. J. Strandburg, S.
Wright, and P. Plassmann, ``Critical Fields of Josephson-Coupled Superconducting
Multilayers,'' MCS-P281-1291. |
The finite-element representation of the Ginzburg-Landau
free-energy functional introduced by Doria, Gubernatis, and Rainer is generalized to treat
Josephson-coupled superconductor-insulator multilayer materials. Numerical calculations
are performed for applied field parallel to the layers. Results are presented for the
upper and lower critical fields as well as the slope of the magnetization at the upper
critical field. The calculations for the lower critical field are compared with the recent
analytical formulation of Clem et al. No previous prediction is available for the slope of
the magnetization curve in a layered system. |
|
|
| P. T. P. Tang, ``Dynamic Condition Estimation and
Rayleigh-Ritz Approximation,'' MCS-P282-1291. |
It is shown that the well-known Rayleigh-Ritz approximation
method is applicable in dynamic condition estimation. In fact, it can be used as a common
framework from which many recently proposed dynamic condition estimators can be viewed and
understood. This framework leads to natural generalizations of some existing dynamic
condition estimators as well as more convenient alternatives. Numerical examples are also
provided to illustrate these claims. |
