Skip to main content
main-content

Über dieses Buch

Advances in computer technology have had a tremendous impact on mathematics in the last two decades. In June of 1989, an international conference was held at MIT, bringing together mathematicians and computer scientists, to survey the work that has been done in computational mathematics, to report recent results in this field, and to discuss research directions as well as educational issues. This book presents a fascinating collection of contributions on topics ranging from computational algebra, and parallel computing, to mathematics education. Mathematicians interested in the computational aspects of their discipline as well as computer scientists interested in mathematical applications will enjoy the integrative view provided by this book.

Inhaltsverzeichnis

Frontmatter

Track A (10:45am–12:30pm)

A Completion Procedure for Computing a Canonical Basis for a k-Subalgebra

A completion procedure for computing a canonical basis for a k-subalgebra is proposed. Using this canonical basis, the membership problem for a k-subalgebra can be solved. The approach follows Buchberger’s approach for computing a Grobner basis for a polynomial ideal and is based on rewriting concepts. A canonical basis produced by the completion procedure shares many properties of a Gröbner basis such as reducing an element of a k-subalgebra to 0 and generating unique normal forms for the equivalence classes generated by a k-subalgebra. In contrast to Shannon and Sweedler’s approach using tag variables, this approach is direct. One of the limitations of the approach however is that the procedure may not terminate for some orderings thus giving an infinite canonical basis. The procedure is illustrated using examples.

Deepak Kapur, Klaus Madlener

Summation of Harmonic Numbers

The problem of finding closed forms for a summation involving harmonic numbers is considered. Solutions for ∑in=1P(i)Hi(k) , where p(i) is a polynomial, and ∑in=1 Hi/(i+m), where m is an integer, are given. A method to automate these results is presented. This is achieved by using Moenck’s algorithm and by exploiting the relationship between polygamma functions and harmonic numbers.

Dominic Y. Savio, Edmund A. Lamagna, Shing-Min Liu

Algorithm and Implementation for Computation of Jordan Form over A[x 1,...,x m ]

I outline a sequential algorithm for computation of the Jordan form for matrices in K = A[x1,... ,xm], with A an unique factorization domain with separability. The algorithm has average cost (for K integers) of O(n4L(d)2). I have implemented this algorithm in MACSYMA and it is currently distributed as part of the Climax system.

Nicholas Strauss

Fast Group Membership Using a Strong Generating Test for Permutation Groups

Many important algorithms in computations with permutation groups require an efficient solution to the group membership problem. This requires deciding if a given permutation is an element of a permutation group G specified by a set of generators. Sims [8] developed an elegant solution to this problem. His method relies on the construction of an alternative generating set for G known as a strong generating set which can be easily used to test membership of an arbitrary permutation in G. This algorithm was shown to have worst case time O(n6). Later versions [1, 5, 6] have improved the theoretical worst case time but without necessarily improving the performance in practice. An algorithm is presented here which has an observed running time of O(n4) for all permutations groups for which it has been tested. (The worst-case time for this algorithm is O(n5).) The key idea is a new test [3] for whether a set of generators is a strong generating set. Each call to this last test has worst case time O(n4). A further reduction in time is achieved by using a fast algorithm for finding reduced generating sets. For groups with small bases, the running running time is O(n2), which is optimal for the data structure used.

Gene Cooperman, Larry Finkelstein, Paul Walton Purdom

Finite-Basis Theorems and a Computation-Integrated Approach to Obstruction Set Isolation

Recent advances in well-partial-order theory, especially the seminal contributions of Robertson and Seymour, make tools available that establish only the existence of polynomial-time decision algorithms. The finite-basis theorems that are the engine of these developments are inherently nonconstructive, providing no effective means for capturing the obstruction sets on which these polynomial-time algorithms are based. In this paper, we use a well-studied matrix permutation problem to describe an approach to obstruction set isolation that makes essential use of the computer in a mathematical proof. (In fact, the task of identifying such obstruction sets appears to pose many “4CT-like” problems for which computational assistance is vital.) We also discuss an approach based on a computational “learning” paradigm that incorporates a fundamental component of computer-aided obstruction identification with self-reduction to obtain known polynomial-time algorithms that do not depend on the knowledge of an entire obstruction set.

Michael R. Fellows, Nancy G. Kinnersley, Michael A. Langston

Track B (10:45am–12:30pm)

Practical Determination of the Dimension of an Algebraic Variety

The determination of the dimension of an algebraic variety is a problem that, in principle, can be solved in an algorithmic way. If the variety is projective, this can be made through the computation of the Hilbert polynomial; if it is affine, consider a completion of the affine variety; the completion may have larger dimension than the affine variety, but in this case it may have irreducible components contained in the hyperplane at infinity. This can be checked, and if this happens, a decomposition into irreducible components reduces the problem to the other case. Moreover, if the completion of the affine variety is made with respect to the affine immersion given by a standard basis (also called Gröbner basis) with respect to an homogeneous term ordering, no irreducible component may be contained in the hyperplane at infinity. Hence, a standard basis computation is sufficient to decide the question.

André Galligo, Carlo Traverso

A Computer Generated Census of Cusped Hyperbolic 3-Manifolds

In this paper, we describe how we used a computer to produce a census of cusped hyperbolic 3-manifolds obtained from 5 or fewer ideal tetrahedra. We note some of the techniques involved in writing and debugging the programs and give a brief summary of the results.

Martin Hildebrand, Jeffrey Weeks

Classicality of Trigonal Curves of Genus Five

This paper is the description of a computer-assisted search leading to the Theorem 1All trigonal curves of genus five are classical. Classical here is to be understood in the sense of F.K.Schmidt [9], that is, the vanishing sequence of the canonical line bundle is the classical sequence 0,1,2,3,4. Nonclassical curves are only possible if the characteristic of the field of definition does not exceed 2g — 2 , where g is the genus of the curve, and non-classical curves up to genus 4 were classified by Komiya [7].

Paulo Viana

Symmetric Matrices with Alternating Blocks

A statement in algebraic geometry over fields of arbitrary characteristic follows from the existence of matrices with integer entries of the type mentioned in the title. It is shown how these matrices can be built from a finite number of small matrices. It is reported how these small matrices, of which the largest is a 25 by 25 matrix, were found using computer algebra systems.

Abramo Hefez, Anders Thorup

Cohomology to Compute

Our purpose is to interest people to calculate (co)homology with help of a computer, in particular, (co)homology of Lie algebras and Lie superalgebras.

D. Leites, G. Post

Track A (4:00pm–5:45pm)

Use of symbolic methods in analyzing an integral operator

The “stability of matter” problem in theoretical quantum mechanics is to derive from basic theory a mathematically rigorous lower bound on the energy per nucleus of an arbitrary configuration of nuclei and electrons. Such a lower bound provides a theoretical explanation of why the electrons do not simply collapse into the nuclei. The existence of a lower bound for the energy was originally proved by Dyson and Lenard in [1]. Lieb and Thirring [4,3] later established a much better bound, coming within a factor of about 5.4 of the value suggested by experimental data. Recently, C. Fefferman [2] has presented a method that promises to yield a further improvement. Roughly, the idea is to express the total energy as an integral over all balls (of all sizes) in R3 , and then for each ball that contains nuclei to assign its energy in equal shares to all nuclei in it, and for each ball that contains no nuclei to assign its energy to the nearest nucleus. The lowest energy assigned to any nucleus is obviously a lower bound for the average energy per nucleus. Arguments given in [2] provide bounds for the energy contributed to a nucleus by all balls except those that are contained within a sphere of radius 28 about the nucleus and have their center within a distance 5 of the nucleus, where 25 is the distance to the nearest other nucleus. It is also shown in [2] that a lower bound for the energy contributed by the remaining balls can be obtained in terms of the sum of the negative eigenvalues of the quadratic form Q = K – V described below, which is essentially the part contributed by the same family of balls to the energy for a single electron in the field of a stationary nucleus with charge Z. (In the limit as δ goes to infinity, K becomes the kinetic energy given by the Laplacian, and V the Coulomb energy (given by a “1/r” potential) for such an electron.) The present paper discusses the computational problem of getting a rigorous lower bound on the negative eigenvalues of Q . As stated above, Fefferman is entirely responsible for formulating the problem; in addition, he has been closely involved in the computational analysis and some of what is reported here is joint work with him.

H. F. Trotter

Computer Algebraic Methods for Investigating Plane Differential Systems of Center and Focus Type

For plane differential systems of center and focus type, the author described an algorithmic procedure based on the principle of Poincare’s method and implemented a program DEMS for computing the Liapunov function and Liapunov constants. This function and these constants are used in the study of stability criteria, differentiation between center and focus and the construction of limit cycles. The solutions of the problems concerning the investigation of Liapunov constants then require that algebraic decision problem, algebraic simplification and algebraic equations solving, to which Wu’s characteristic set method and Buchberger’s Gröbner basis method are successfully applied. Using the program DEMS and these computer algebraic methods, the author studied some concrete differential systems and obtained the stability criteria and the relations between the computed Liapunov constants and other conditions. In particular, we discovered that Kukles’ conditions for the existence of a center for a type of cubic differential systems are possibly incomplete, and presented a class of cubic differential systems with the origin as a 6-tuple focus from which one can create 6 limit cycles by a small perturbation. This paper is a summarization of our recent work.

Dongming Wang

An Example of Computer Enhanced Analysis

In this report, a first order nonlinear partial differential equation with a parameter dependent initial condition is examined. Even though an analytic solution of the equation is determined, a surprising bifurcation phenomenon is discovered via computer graphics. This “computer-discovered” bifurcation, in turn, leads to further mathematical analysis and deeper geometric understanding of the solution. Indeed, this is a simple example of an elementary catastrophe (in the sense of Thorn) and demonstrates the usefulness of numerical computations in providing qualitative information even in the presence of exact solutions.

Peter J. Costa, Ruth Hampton Westlake

An Algorithm for Symbolic Computation of Hopf Bifurcation

The Hopf bifurcation has become a widely used method in the study of periodic oscillations of nonlinear dynamical systems. The purpose of this paper is not to carry out a direct symbolic algebraic manipulation of formulae characterizing this bifurcation (direction, stability and amplitudes of bifurcating periodic orbits, ...). It is planned to develop a recursive algorithm well suited to symbolic computation implementation, which is based upon the normal form approach and supplies the necessary information to characterize generalized Hopf bifurcations.An efficient procedure to obtain the normal form corresponding to a Hopf bifurcation is presented; it is based upon the use of Lie transforms. The calculations are arranged in a recursive scheme using complex variables and so the computational effort is optimized. The devised algorithm is implemented on REDUCE 3.2 and applied to several examples.

Emilio Freire, Estanislao Gamero, Enrique Ponce

Application of the REDUCE Computer Algebra System to Stability Analysis of Difference Schemes

The stability regions of difference schemes approximating systems of linear partial differential equations are automatically obtained by using the Computer algebra system REDUCE and numerical methods for polynomial roots location. The stability analysis is performed by the Fourier method and polynomial root location is based on the Routh algorithm. Several practical examples show the usefulness of the programs described.

Victor G. Ganzha, Richard Liska

Track B (4:00pm–5:45pm)

Signs of Algebraic Numbers

This payer presents an algorithm for the computation of the sign of the value of a polynomial at an algebraic number.

Takis Sakkalis

Efficient Reduction of Quadratic Forms

The positive definite integer quadratic form, ax2 + bxy + cy2, is of some importance in number theory. For example such quadratic forms have been shown useful in factorization of large integers. For many applications it is important to be able to recognize when two quadratic forms are equivalent, so it is useful to be able to reduce these quadratic forms to a canonical representation.For applications in factorization, the quadratic forms used have large coefficients, which must be represented as multiple computer words. This paper shows how to efficiently reduce such multi precision quadratic forms.

Neil W. Rickert

A Story About Computing with Roots of Unity

In the course of studying idempotents of the group algebra of the symmetric group that characterize Lie elements of the free symmetric algebra, we show how we obtained new unexpected results trough computer algebra experiments. This was the direct result of computing in the ring of polynomials modulo the cyclotomic polynomial, instead of computing with roots of unity.

F. Bergeron

Exact Algorithms for the Matrix-Triangularization Subresultant PRS Method

In [2] a new method is presented for the computation of a greatest common divisor (gcd) of two polynomials, along with their polynomial remainder sequence (prs). This method is based on our generalization of a theorem by Van Vleck (1899)[12] and uniformly treats both normal and abnormal prs’s, making use of Bareiss’s (1968)[4] integer-preserving transformation algorithm for Gaussian elimination; moreover, for the polynomials of the prs’s, this method provides the smallest coefficients that can be expected without coefficient gcd computations. In this paper we present efficient, exact algorithms for the implementation of this new method, along with an example where bubble pivot is needed.

Alkiviadis G. Akritas

Computation of Fourier Transforms on the Symmetric Group

Let G be a finite group and f any complex-valued function defined on G. If p is a matrix representation of G then the Fourier transform of f at p is defined as the matrix ∑s∊Gf(s)p(s)-Various applications demand the computation of the Fourier transforms of f at all irreducible representations of G. Direct computation of all such Fourier transforms requires on the order of |G|2 arithmetic operations.In earlier work with Diaconis ([DR]) ideas have been presented for more efficient methods of computing Fourier transforms. In particular, for Sn several algorithms were sketched. This paper describes in detail a running implementation of one of these algorithms which has been used effectively on a VAX11/750 and a SUN4.

Daniel Rockrmore

Track A (9:00am–10:20am)

Integration in Finite Terms and Simplification with Dilogarithms: A Progress Report

In this extended abstract, we report on a new theorem that generalizes Liouville’s theorem on integration in finite terms. The new theorem allows dilogarithms to occur in the integral in addition to elementary functions. The proof is based on two identities, for the dilogarithm, that characterize all the possible algebraic relations among dilogarithms of functions that are built up from the rational functions by taking transcendental exponentials, dilogarithms, and logarithms. We report also on a generalization of Risch’s decision procedure for integrating elementary transcendental functions to include dilogarithms and elementary functions in the integral.

Jamil Baddoura

Why Integration is Hard

This paper is a brief introduction to how the techniques of computational complexity can be applied to real analysis—integration in particular. We investigate how the difficulty of computing a function relates to the difficulty of computing its integral. Our comments are directed to an audience that is more familiar with traditional analysis and numerical methods than it is with complexity theory.

H. James Hoover

Liouvillian Solutions of Linear Differential Equations with Liouvillian Coefficients

Let L(y) = b be a linear differential equation with coefficients in a differential field K. We discuss the problem of deciding if such an equation has a non —zero solution in K and give a decision procedure in case K is an elementary extension of the field of rational functions or is an algebraic extension of a transcendental liouvillian extension of the field of rational functions. We show how one can use this result to give a procedure to find a basis for the space of liouvillian solutions of L(y) = 0 where L(y) has coefficients in such a field.

Michael F. Singer

Recipes for Classes of Definite Integrals Involving Exponentials and Logarithms

There are many classes of definite integrals for which the corresponding indefinite integral cannot be expressed in closed form whereas the definite integral can be expressed (often in terms of special functions). A computer algebra system should be capable of recognizing a wide variety of definite integrals and, in order to achieve a broad coverage, it is desirable to encode this knowledge in programs which are more general than simple table look-up. By exploiting integral definitions of the various special functions of mathematics and by generalization and differentiation, we are able to derive closed-form solutions for broad classes of definite integrals. In this paper we treat integrals involving exponentials and logarithms. The resulting programs, based on pattern matching and differentiation, are very efficient.

K. O. Geddes, T. C. Scott

Track B (9:00am–10:20am)

Logic and Computation in MATHPERT: An Expert System for Learning Mathematics

MATHPERT (as in “Math Expert”) is an expert system in mathematics explicitly designed to support the learning of algebra, trigonometry, and first semester calculus. This paper gives an overview of the design of MATHPERT and goes into detail about some connections it has with automated theorem proving. These connections arise at the borderline between logic and computation, which is to be found when computational “operators” have logical side conditions that must be satisfied before they are applicable. The paper also explains how MATHPERT maintains and uses an internal model of its user to produce individually tailored explanations, and how it dynamically generates individualized and helpful error messages by comparing user errors to its own internal solution of the problem.How MATHPERT is to be used in education, and the implications of learning environments like MATHPERT for curriculum and pedagogy, are discussed in Beeson [1989a, 1989d, 1989e]. The details of the design of MATHPERT are discussed in Beeson [1989b].

Michael J. Beeson

Representation of Inference in Computer Algebra Systems with Applications to Intelligent Tutoring

Presently computer algebra systems share with calculators the property thai a sequence of computations is not a unified computational sequence, thereby allowing fallacies to occur. We argue thai if computer algebra systems operate in a fram,ework of strict mathematical proof fallacies are eliminated. We show that this is possible in a working interactive system, REQD. We explain why computaiional algebra, done under the strict constraints of proof, is relevant to uses of computer algebra systems in instruction.

Tryg A. Ager, R. A. Ravaglia, Sam Dooley

Bunny Numerics

A Number Theory Microworld

A microworld designed for use in number theoretic investigations is described. This microworld, bunny numerics, is being used to complement the workhorse turtle geometry microworld in a Logo based problem solving course that we have recently initiated at SUNY Oswego. The microworld is defined, examples of its use are provided, suggestions for its use are offered, and a few notes on its implementation are made.

Craig Graci, Jack Narayan, Randy Odendahl

Advanced Mathematics from an Elementary Viewpoint: Chaos, Fractal Geometry, and Nonlinear Systems

We are conducting exploratory research to investigate the instructional issues and educational benefits from introducing both a new paradigm and a new area of applied mathematics into the high school curriculum. The new paradigm is experimental mathematics and the new area is mathematical chaos. By experimental mathematics we mean computer modeling of mathematical processes to gain insight into their structure and behavior so as to inform and guide mathematical inquiry. Mathematical chaos is the study of orderly and chaotic behavior in nonlinear processes and in the real world systems modelled by them. Both depend fundamentally on the use of computers and interactive graphics technology.School curricula often present the standard subjects in an intellectually impoverished and uncompelling way, teaching modes of thinking and doing that are distinctly different from those used by practitioners. School math is not a model of real mathematics and school science is not genuine science. Education should be directed to grounding knowledge in experience and in contexts of use. Our thesis is that the introduction of experimental mathematics and mathematical chaos will help accomplish this by creating highly motivating computational environments that foster exploration and discovery and bridge the gulf between schoolwork and real mathematics and science.

Wallace Feurzeig, Paul Horwitz, Albert Boulanger

Track A (10:45am–12:05pm)

Iterated Function Systems and the Inverse Problem of Fractal Construction Using Moments

Let K be a compact metric space and w i :K→K, 1≤i≤N, be a set of contraction maps, with assigned probabilities pi. This contractive iterated function system (IFS) possesses a unique and invariant attractor set A. Given a target set S, the inverse problem consists in finding an IFS {K,w,p} whose attractor A approximates S as closely as possible. We examine a numerical method of approximating a (fractal) target set S by minimizing the distance between the moments of S and A. This amounts to a nonlinear optimization of the parameters defining the IFS. In this way, both the geometry and shading measure encoded in S may be simultaneously approximated in a quantified procedure.

Edward R. Vrscay, Christopher J. Roehrig

Working with ruled surfaces in solid modeling

The interplay between algebraic geometry and graphics/solid modeling is a natural and strong one. This paper addresses the topic of ruled surfaces, a class that has long been of interest to the mathematical community, and brings it more squarely into the realm of computer science by giving constructive algorithms for ruled surfaces. These algorithms allow ruled surfaces to be used more easily in a solid modeling system. Specifically, we show (a) how to identify that a surface is ruled from its equation (b) how to find the generator through a given point of a ruled surface and (c) how to find a directrix curve of a ruled surface. As an example of how these algorithms can be put to use in a solid modeling environment, we show how to parameterize a ruled surface.Ruled surfaces share properties of both curves and surfaces, which make ruled surfaces a very useful class in the difficult transition between curves and surfaces in solid modeling. They can be used to extend algorithms for curves (which are easier to develop) to algorithms for surfaces. The mathematical theory of curves and surfaces can continue to guide their incorporation into solid modelers although, as is shown in this paper, computer scientists will often have to develop constructive techniques to replace existential mathematical statements.

John K. Johnstone

Using MACSyma to Calculate the Extrinsic Geometry of a Tube in a Riemannian Manifold

In this paper we present a MACSyma batch file that calculates the second fundamental form of a tubal hypersurface of a Riemannian manifold. This program is currently being used to investigate the extrinsic geometry of tubes about totally umbillic submanifolds in a complex space form and is implemented on a Sun 3/60.

Harry S. D. Mills, Micheal H. Vernon

Computer Algebra in the Theory of Ordinary Differential Equations of Halphen Type

We present an algorithm for solving linear differential equations in spectral parameter of Halphen type. The integrability condition of the pair of equations of Halphen type gives the large family of nonlinear differential equations of Lax-Novikov type. This algorithm is implemented on the basis of the computer algebra system REDUCE.

V. F. Gerdt, N. A. Kostov

Track B (10:45am–12:05pm)

Symbolic Derivation of Equations for Mixed Formulation in Finite Element Analysis

One important application area of symbolic manipulation systems is to use them as preprocessors to generate numerical code for target machines, thus facilitating the tedious pre-processing involved in numerical computing, particularly in Finite Element Method (FEM). However, pre-processing the given formulation often generates unacceptable results due to the number of derivation steps involved as well as the exponential growth of expressions produced. Presented in this paper are some of the procedures and techniques we have developed for efficient derivation of element equations in FEM. Examples are given for applications of those procedures and techniques in the derivation of element equations for mixed formulations.

H. Q. Tan

Semantics in Algebraic Computation

I am interested in symbolic computation for theoretical research in algebraic topology. Most algebraic computations in topology are hand calculations; that is, they can be accomplished by the researcher in times ranging from hours to weeks, and they are aimed at discovering general patterns rather than producing specific formulas understood in advance. Furthermore, the range of algebraic constucts used in such calculations is very wide.

D. L. Rector

Symbolic Computation with Symmetric Polynomials an Extension to MACSYMA

We present here a package of manipulations of symmetric polynomials implemented in Franzlisp. This package, called SYM, constitutes at present an extension of the system of symbolic computation MACSYMA. It performs a few manipulations on symmetric polynomials; it can also be used for direct applications. Some algorithms extend easily to functions that are symmetric with respect to sets of variables (i.e. multi-symmetric functions); these functions will be dealt with in the present paper.

Annick Valibouze

Simultaneous Computations in Fields of Different Characteristics

This paper presents new software for computing simultaneously in fields of different characteristics.

Dominique Duval
Weitere Informationen