Computer Mathematics

The following sections are included:

• PREFACE

• CONTENTS

We show how computer algebra methods based on Gröbner basis computation and implemented in the program FGb enable us to compute all the solution of the Cyclic 9 problem a previously untractable problem. There are one type of infinite solutions of dimension two and 6156 isolated points without multiplicities.

The following sections are included:

• Introduction

• Wiedemann's algorithm with baby steps/giant steps

• Acceleration by blocking

• Improved division-free complexity

• Conclusion

• Acknowledgement

• References

We present a study that addresses the problem of growth of the length of intermediate expressions generated in a polynomial sequence, with special interest in Sturm sequences and Schur-Cohn sequences. We analyze how some features of a polynomial affect the computational efficiency. Particularly we point out some algorithms that use some kind of polynomial sequence, to determine the number of polynomial zeros in a closed region. A computational experiment was designed, to measure how the length of the coefficients changes along a polynomial sequence, according to the kind of polynomial. A Maple program was developed to analyze polynomial sequences using both primitive Sturm and modified Schur-Cohn sequences. The results of the tests show that for the modified Schur-Cohn sequence with Chebyshev polynomials, increasing of the length of the coefficients occurs, but not so intensively as it occurs for most of polynomials. For Sturm sequences with Chebyshev polynomials, the length of the coefficients decreases, but for the same kind of sequence with linear combination of Chebyshev polynomials, the length of the coefficients begins decreasing and in the last terms of the sequence, the length increases.

We report on a recent implementation of Giesbrecht's algorithm for factoring polynomials in a skew-polynomial ring. We also discuss the equivalence between factoring polynomials in a skew-polynomial ring and decomposing p^s-polynomials over a finite field, and how Giesbrecht's algorithm is outlined in some detail by Ore in the 1930's. We end with some observations on the security of the Hidden Field Equation (HFE) cryptosystem, where p-polynomials play a central role.

Let A be an n × n matrix which contains parameters q_i (i = 1, 2, …, k). Given a linear differential equation

where x is an n-dimensional vector, it is generally difficult to compute solution x(t) explicitly. In this paper, we compute the solution in the form of truncated power series in t - t₀ and q_i, where t₀ is a given constant number. We apply the method to a control system design. It is shown that design parameters can be determined in consideration of the time response of controlled system, which simplifies the design process.

A new algorithm to find real zeros of zero-dimensional systems within an absolute error bound is presented. If a zero of the system is (ξ₁,ξ₂,…,ξ_N) ∈ R^N, the presented method first solves the minimal polynomial of x_i to locate ξ_i for each i. Then the algorithm checks if a combination (ξ₁,ξ₂,…,ξ_N) is truly a zero of the system. In order to do this easily, a linear map called a separating map is introduced, which maps a set of hyper-boxes arranged on a lattice in R^N to non-overlapping intervals in R. Zeros obtained by the method has absolute accuracy assured for any variable. An example implementation and experimental results are included. The algorithm described here is a basic one, and many improvements for practical implementation may be possible.

In this paper, the main different methods for solving polynomial systems (Gröbner bases, triangular sets, …) are compared on an example coming from geometry. It is shown that these methods may be combined for automatically studying the number of admissible real solutions of a polynomial system depending on parameters; this study provides as output a description of this number as a function of the parameters.

The increasing complexity in scientific and engineering computation is motivating the building of powerful Problem Solving Environments (PSEs). In this paper, we discuss current PSE-related research and propose a preliminary prototype and easy-to-use PSE for multivariate polynomial GCD computation using a combination of the Maple and Matlab packages and programs in C. This integrated computing environment enables improved use of existing resources to deliver more efficient solutions. This approach is of particular importance for large scale symbolic and numerical computations. An example is given to demonstrate the efficiency gains with solving approximate multivariate polynomial GCDs using Hensel lifting. Various issues related to the implementations are presented.

Open Mathematical Engine Interface (OMEI) aims to establish a uniform application programming interface (API) for heterogeneous mathematical computation systems. OMEI can play an essential role in making mathematical engines easily accessible by front-ends, tools, and servers. The interface enables the development of individual applications that can serve different engines. The motivation, application framework, specification, usage scenarios, and Java implementation for OMEI are presented. An application of OMEI to connect Starfish with MAXIMA is described.

In this paper, we discuss the polynomial solutions of algebraic differential equations. We present an approach to find the polynomial solutions of algebraic differential equations with terms less than or equal to three.

OpenXM is a free, or Open Source, infrastructure for mathematical software systems. It provides methods and protocols for interactive distributed computation and for integrating mathematical software systems. OpenXM package version 1.1.3 is a set of software systems that support OpenXM-RFC 100 and 101 proposed standard protocols. It is currently a collection of software systems Asir ¹⁰, GNUPLOT, Kan/sm1 ¹⁹, Macaulay2 ³, PHC pack ²⁰, TiGERS ⁵, Mathematica interface, and OpenMath/XML ¹ translator. These are wrapped with the OX (OpenXM) stack machine to connect each other. Availability: The OpenXM package¹⁴ and OpenXM-RFC's¹⁴ have been obtainable from January 24, 2000.

Tools for mathematics often need to display formulas, to interact with them, and also make them easily accessible on the Internet. In this paper, we present FIGUE, an interactive two dimensional layout engine specialised for building WYSIWYG environments for symbolic systems and scientific document editors. This component is currently used for developing a mathematical proofs interface. In order to communicate mathematical data on the Internet, FIGUE also supports MathML standard: it generates, processes, and renders MathML documents.

In this paper we propose two symbolic-numeric combined methods to solve polynomial equations by using Ritt-Wu's characteristic sets method. One method uses multivariate approximate-GCD to compute pseudo remainders and a cutoff parameter ϵ to neglect polynomials if the coefficients are sufficiently small. The other method uses Shirayanagi-Sweedler's stabilization techniques to guarantee reliability of obtained solutions. We discuss the two methods by using experimental results obtained from a problem of inverse kinematics of robot manipulators.

In certain proofs of theorems of, e.g., number theory and the algebra of finite fields, one-to-one correspondences and the "pairing off" of elements often play an important role. In textbook proofs these concepts are often not made precise but if one wants to develop a rigorous formalization they have to be. We have, using an inductive approach, developed constructs for handling these concepts. We illustrate their usefulness by considering formalizations of Euler-Fermat's and Wilson's Theorems. The formalizations have been mechanized in Isabelle/HOL, making a comparison with other approaches possible.

In engineering design, as design proceeds, more and more design decisions are being made and more and more design parameters are introduced. As more design parameters come into consideration, designers face increasing difficulties in gaining insights into the relationships among these parameters. This research aims at overcoming the above difficulties by applying Gröbner basis and Quantifier Elimination. The new constraint solving methods help designers in gaining important insights during engineering design. These constraint solving methods have been evaluated through case studies of multidisciplinary engineering design: a robotic arm system design and a heat pump system design. The evaluation results have illustrated that these constraint solving methods are useful for gaining important insights during engineering design to help designers to make informed decision.

JavaMath is free software oriented toward integrating existing compute engines, such as Maple or GAP, into Internet accessible mathematical services. The architecture of the API is described and its use explained.

There exist 21 types of curves as the classification of irreducible quartic curves. Irreducible quartic curves are classified by the singularities. In this paper, we consider the deformation of irreducible quartic curve with a double cusp singularity by using the computer algebra system Risa/Asir.

We generalize Wu–Ritt's algorithm for the computation of characteristic sets by means of one-step pseudo-reduction instead of pseudo-division. This generalization results in a new algorithm which, with optimal selection of reductors and heuristic generation of S-polynomials, may speed up the computation considerably and produce simpler output for large problems. Examples and experiments are provided to show the performance of our new algorithm.

This paper presents a decision method to check inclusion among differential quasi-algebraic varieties. The basic strategy is as follows: applying some equivalent formulas in first-order logic, the problem of deciding inclusion can be transformed into one which checks whether some differential quasi-algebraic varieties are empty; by differential Hilbert Nullstellensatz, it becomes a decision problem of membership in the radical of finitely generated differential ideals, which can be solved by Rosenfeld-Gröebner Algorithm. A decision algorithm and two examples are given in the paper.

We develop techniques of action refinement in a real-time process algebra baptized timed LOTOS. Semantic refinement is performed in a timed extension of bundle event structures. We show that the refinement operations we presented behave well. They meet the commonly expected properties.

In this letter, with the aid of symbolic computation, a simple transformation is powerfully applied to find exact solutions of the coupled MKdV-KdV equation such that many new families of exact solutions are given which contain bell-shaped solitary wave solutions, kink-shaped shock wave solutions, periodic wave solutions and new solutions…

A direct and unified algorithm for constructing multiple traveling wave solutions of nonlinear differential equations is presented and implemented in computer algebraic system Maple. A generic system of coupled ordinary nonlinear differential equations for a pair of real scalar fields is studied by this method, and in addition to rederiving all known solutions in a systematic way, several new solutions (either functional or parametrical) are explicitly obtained.

We present an effective algorithm for isolating the real solutions of semi-algebraic systems, which has been implemented in MAPLE-program realzero. For a large number of examples with various backgrounds, realzero gets the solutions very efficiently.

From the point of view for finding solution to differential equations, this paper introduces the concepts of C-D integrable systems and C-D pair respectively. Under some conditions, we shall prove that these concept are equivalent. An efficient method for finding C-D pairs is presented and the computer aided solver for differential equations is also presented.

The following sections are included:

• AUTHOR INDEX