Computer Algebra – Where we are?, Where we go?

Tateaki Sasaki

Institute of Mathematics, University of Tsukuba Tsukuba-shi, Ibaraki 305, Japan

Abstract

We list some epoch-making events in computer algebra in 1, point out prominent features and thema of algebraic systems in 2, prominent features and thema of algebraic algorithms in 3, and mention where we will or should go next in 4.

0 Brief summary of the talk

After the birth in about 1960 [Appl, Systm], computer algebra has attained astonishing development in these 35 years. By middle 1970’s, elementary operations on polynomials and rational functions, such as GCD and factorization [Factri], have already been made sufficiently efficient, and remarkable advancement has been attained also for most mathematical operations that non-mathematics course students learn, such as indefinite integral [IntDE] and infinite series. After 1980, algorithm research went to higher mathematics, such as ideal and ring theory [Book], and is now building a wonderful realm there. The fruit of algorithm research has immediately been taken into computer algebra systems, and many powerful and useful generalpurpose systems have been constructed so far: REDUCE and MACSYMA representing 1970’s - 1980’s, and Axiom, Maple and Mathematica representing late 1980’s - 1990’s [Systm]. These systems are now used by not only researchers but also teachers and students. The application areas of computer algebra are now ranging from mathematics and physics to most of theoretical science and engineering and even to economics [Appl]. Summarizing the conventional computer algebra, we may say as follows.

[Computer Algebra so far] = [Mathematics] + [Efficiency]
⇒ Computerization of Mathematics

Then, where will computer algebra go ? Undoubtedly, computerization of mathematics will go further, which is, although satisfactory from the viewpoint of mathematics, never satisfactory from the viewpoints of users. The reason is lack of practicality. For example, for algebraic equation, conventional computer algebra tries to find algebraic numbers as exact solutions, which is usually quite difficult and requires much time. However, for many users, algebraic numbers are useless; they want to know approximate values of the solutions. In applications, getting approximate answers quickly is often much more important than getting exact answers after many hours of computation. Practicality is a leading principle in numeric computation, and being guided by this principle, numerical analysis has built a unique realm. Recent researches of the author’s group revealed that the principle of practicality also leads computer algebra to a new and fruitful world which we call approximate algebra [AppAlg]. Therefore, the author proposes the following new way.

[Computer Algebra from now] = [Math.] + [Effic.] + [Practicality]
⇒ Infrastructural T echnology

1 Epoch-making events in computer algebra

The following is only an incomplete and restricted list of the events. For more details, see the selected bibliography at the end of this paper.

1959: computer manipulation of polynomials in celestial mechanics [Appl]. 1961: computer program calculating freshman-level integrals (Slagle [Systm]). 1965: FORMAC (Sammet [Systm]), first general-purpose system. 1965: Gröbner basis construction algorithm (Buchberger [Book]). 1966: subresultant algorithm for polynomial GCD (Collins [Book]). 1967: univariate factorization algorithm over Z_{p} (Berlekamp [Factri]). 1969: integration algorithm of elementary functions (Risch [IntDE]). 1969: univariate factorization algorithm over Z (Zassenhaus [Factri]). 1968 – 73 : large-scale application to quantum electro-dynamics [Appl]. 1972 – : REDUCE (Hearn [Systm]), world-wide distributed system. 1973 – 90 : MACSYMA (Moses, et al. [Systm]), big mathematical system. 1973: modular multivariate GCD algorithm (Moses and Yun [Book]). 1973: multivariate factorization algorithm (Wang and Rothschild [Factri]). 1974 – : CAYLEY/Magma (Cannon [Systm]), a system for group theory. 1974 – : SCRATCHPAD/Axiom (Jenks et al. [Systm]), system with abstract data-types. 1975: sylindrical decomposition algorithm (Collins [Book]). 1978: geometry-theorem proving with characteristic set (Wu [Book]). 1979 – : μ-MATH/Derive (Stoutemyer and Rich [Systm]), system on micro-computer. 1980 – : Maple (Geddes et al. [Systm]), compact and portable general-purpose system. ∼1975 – : application of Gröbner basis to commutative algebra [Book]. ∼1980 – : study of automated geometry-theorem proving [Book]. ∼1985 – : study of parallel execution of algebraic computation [Book]. 1987 – : Mathematica (Wolfram et al. [Book]), symbolic-numeric-graphic system. 1989 – : study of approximate algebra [AppAlg].

2 Features and thema of algebraic systems

Modern and general-purpose algebra system is self-containing in that it is equipped with very low to high level mathematical operations, pretty complicated because it contains many data-types categorized variously, it is a long-term growing system, and is an integrated system with facility of symbolic, numeric and graphic computations.

2.1 Self-containing system

In numeric computation, the programming language system, such as FORTRAN or C, provides us with many numeric operations, such as evaluating elementary functions, solving linear and algebraic equations, computing eigen-values and eigen-vectors, calculating various kinds of definite integrals, and so on. In algebraic computation, the programming language system, such as Lisp or C, does not provide us with any algebraic operation, and each algebra system must be equipped with even very low level operations, such as polynomial arithmetic, polynomial GCD, etc. Therefore, general-purpose algebra system becomes of large-scaled. In fact, more than 100 man-year power has been devoted to develop MACSYMA.

2.2 Many data-types categorized variously

A mathematical object is usually categorized variously. For example, polynomial, the most common data-type in computer algebra system, may be categorized as either an element of a ring over Z_{p}, Z, Q, Q(α), R, or C (may be represented approximately by floating-point numbers), an element of a field, of an integral domain or of a Euclidean domain, etc. In addition to polynomials, we must also handle algebraic numbers, algebraic functions, rational functions, and many other mathematical objects. Furthermore, these many data-types must be organized hierarchically. Thus, a general-purpose computer algebra system is quite complicated.

One idea to organize many various algebraic data-types hierarchically is that the system itself does not prepare every necessary data-type but it provides the user with a facility of defining new data-types hierarchically. SCRATCHPAD/Axiom has been constructed on this idea. However, providing such a facility itself is not easy. How to handle many various data-types is still a problem in designing algebra system.

It should be commented, however, that data-types may not be categorized so finely as mentioned above in the system for scientific and technological applications.

2.3 Long-term growing system

In each algebra system, there is a loose hierarchy on algorithms, too; at the lowest level we have algorithms on numbers, such as integer GCD and factorization, at the second lowest level, we have many algorithms on polynomials, such as polynomial GCD and factorization, and so on. In addition, there is a hierarchy among algorithms on each mathematical operation; for example, [Univariate factorization over Z_{p}] ≺ [Univariate factorization over Z] ≃ [Univariate factorization over Q(α)] ≺ [Multivariate factorization over Z] ≺ · · · . Considering operations in higher algebra, we can observe many levels of hierarchy.

The above-mentioned hierarchy forces us to construct corresponding procedures hierarchically. Furthermore, compared with procedures of numeric computation, procedures of algebraic computation require much more time to program. Hence, a long-term is necessary to develop general-purpose system, and the system will continue to grow several decades usually. In fact, REDUCE has been growing continuously these 25 years.

2.4 Integration of symbolic, numeric, graphic computations

Drawing graphs is absolutely necessary in school mathematics. Similarly, graphics is very useful in algebra system, too. Mathematica is the first system that is equipped with facility of integrating symbolic, numeric and graphic computations, and it has achieved a great fame by this facility. Today, every modern general-porpose system is equipped with this facility.

It should be commented that current symbolic-numeric integrated computation is very limited in ability. We will explain this in 4.3.

3 Features and thema of algebraic algorithms

So far, quite many algebraic algorithms of various kinds have been invented, many of them are quite efficient. In this section, we do not explain individual algorithm separately but point out prominent features and thema of algebraic algorithms complehensively.

3.1 Canonical forms and reductions

Many algebraic algorithms can be viewed as procedures which transform given expressions into unique canonical forms. For example, the complete partial fraction representation is a canonical form of rational function, and rational function in sin(x) and cos(x) can be transformed into a canonical form by the replacements sin(x) → (y − y^{−1})/2i and cos(x) → (y + y^{−1})/2, with y = e^{ix}, and by transforming the resulting rational function in y into a canonical form.

Practically very important case is a set of polynomials

{P_{1}(x, y, …, z), ⋯, P_{r}(x, y, …, z)} ⊂ K[x, y, …, z], K = a number field.

In order to define a canonical form, we introduce two operators, a term order operator ≻ and and a term elimination operator E. For example, we define ≻ by the degree w.r.t. main variable x and E by the following leading term elimination.

E_{lt}(P_{i}, P_{j}) = \frac{lcm}{lt(P_{i})} · P_{i} − \frac{lcm}{lt(P_{j})} · P_{j} (i ≠ j),

where lt(P) is the leading term of P (highest degree term w.r.t. x),
and lcm = Least-Common-Multiple of lt(P_{i}) and lt(P_{j}).

Note that the leading term in {P_{i}, P_{j}} is eliminated by the operation E_{lt}, and we have

E_{lt}(P_{i}, P_{j}) ≺ higher order element of {P_{i}, P_{j}}.

Therefore, the leading term elimination can be viewed as a reduction w.r.t. ≻.

Applying E_{lt} to a set of two polynomials {P_{1}, P_{2}} successively, we can generate a polynomial remainder sequence (rem denotes the remainder operation)

(R_{1} = P_{1}, R_{2} = P_{2}, R_{3} = c_{3} rem(R_{1}, R_{2}), ⋯, R_{k} = c_{k} rem(R_{k−2}, R_{k−1})),
where c_{i} ∈ K(y, …, z), R_{i} ∈ K[x, y, …, z] (i = 3, …, k).

If R_{k+1} = rem(R_{k−1}, R_{k}) = 0 then R_{k} = c gcd(P_{1}, P_{2}), c ∈ K(y, …, z), and (R_{k}) is a canonical form of the ideal (P_{1}, P_{2}) over K(y, …, z). Applying E_{lt} to a set of r polynomials {P_{1}, ⋯, P_{r}} successively, we obtain Ritt-Wu’s characteristic set {R_{1}, R_{2}, ⋯, R_{s}} which plays an essential role in determining the common zeros of {P_{1} = 0, ⋯, P_{r} = 0} algorithmically [Book].

We can define ≻ by a monomial order ≻_{mono} which orders every monomial in K[x, y, …, z] uniquely up to numeric coefficients, and define E by the following head term elimination.

E_{ht}(P_{i}, P_{j}) = \frac{lcm}{ht(P_{i})} · P_{i} − \frac{lcm}{ht(P_{j})} · P_{j} (i ≠ j),

where ht(P) is the head term of P (highest order monomial w.r.t. ≻_{mono}),
and lcm = Least-Common-Multiple of ht(P_{i}) and ht(P_{j}).

In this case, if ht(P_{j})|ht(P_{i}) hence lcm = ht(P_{i}) then E_{ht}(P_{i}, P_{j}) ≺ P_{i} and the above operation defines a reduction w.r.t. ≻_{mono}. Applying E_{ht} to every pair of elements of {P_{1}, ⋯, P_{r}} successively, we obtain a Gröbner basis {Q_{1}, Q_{2}, ⋯, Q_{s}} of the polynomial ideal (P_{1}, ⋯, P_{r}). This is the essence of celebrated Buchberger’s algorithm [Book].

3.2 Intermediate expression swell and modular method

In performing algebraic computation, we often encounter large-sized expressions during the computation, although the initial and final expressions are small-sized or medium-sized. This phenomenon is called intermediate expression swell. We show this phenomenon in the GCD calculation by Euclidean algorithm.

Example 1 Calculation of GCD by pseudo-remainder sequence, where pseudo-remainder of polynomials F and G, with deg(F) ≥ deg(G), is defined as follows.

prem(F, G) = rem(lc(G)^{deg(F)−deg(G)+1}F, G),

here lc(P) is the leading coefficient (coefficient of the leading term) of P. Let P_{1} and P_{2} be polynomials given as P_{1} = x^{8} +x^{6} −3x^{4} +4x^{3} −5x^{2} +4x−3 and P_{2} = 3x^{6} −2x^{4} −5x^{2} +7x−13. The pseudo-remainders, with initial polynomials P_{1} and P_{2}, are calculated as follows.

P_{3} = prem(P_{1}, P_{2}) = 3 × (−2x^{4} + 15x^{3} + 19x^{2} + x + 38),
P_{4} = prem(P_{2}, P_{3}) = 243 × (−1493x^{3} − 1705x^{2} − 473x − 3286),
P_{5} = prem(P_{3}, P_{4}) = 1417176 × (−29152x^{2} − 20590x − 11421),
P_{6} = prem(P_{4}, P_{5}) = 2175722297384036782464 × (108918x − 577823),
P_{7} = prem(P_{5}, P_{6}) = (a very long integer) × (1).

Finally, we find that gcd(P_{1}, P_{2}) = 1 because deg(P_{7}) = 0. How wastful computation we have done to get this simple result ! □

The intermediate expression swell occurs so frequently, and it makes the corresponding computation very slow. In order to perform the computation efficiently, we must suppress the expression swell almost completely. Fortunately, there is a general technique to avoid the swell, the so-called modular method.

We explain how the modular method improves the computation in Example 1, where the expression swell occurs only in the numeric coefficients. The idea is very simple: we perform the computation modulo some big prime p or primes p_{1}, p_{2}, …, p_{k}. If p/2 or p_{1}p_{2} ⋯ p_{k}/2 is larger than any |coefficient| of the final answer, and if the primes do not divide leading coefficients of P_{1}, P_{2}, ⋯, P_{7}, which we say that the primes are lucky, then we can calculate the final answer correctly. For details of modular methods, see the literature [Book].

3.3 Construction of target expressions directly

There are various kinds of modular methods. Currently, most efficient algorithms for polynomial GCD and factorization, multivariate as well as univariate, adopt the modular method. Furthermore, the method is quite effective for Gröbner basis construction, too. The following Example 2 explains how multivariate factorization is performed by a modular method.

Example 2 Let F (x, y, z) = x^{2} + (−yz − z^{2} + y + z + 2)x + yz^{3} − y^{2}z − z^{3} − yz + 2z. Let S = (y, z) be the ideal generated by y and z. We first factorize F (x, y, z) modulo S, which is nothing but factorization of univariate polynomial F (x, 0, 0) :

F (x, y, z) ≡ F (x, 0, 0) = x^{2} + 2x = x(x + 2) (mod (y, z)).

With G^{(0)}(x) = x and H^{(0)}(x) = x + 2 as factors of F modulo S, the generalized Hensel construction allows us to calculate modular factors G^{(k)}(x, y, z) and H^{(k)}(x, y, z) satisfying

F (x, y, z) ≡ G^{(k)}(x, y, z)H^{(k)}(x, y, z) (mod (y, z)^{k+1}), k = 1, 2, · · · .

In our case, G^{(1)}, H^{(1)}, G^{(2)}, H^{(2)} are calculated uniquely as follows.

\begin{matrix}G^{(1)}(x, y, z) = x + z, & H^{(1)}(x, y, z) = x + 2 + y, \\ G^{(2)}(x, y, z) = x + z − yz, & H^{(2)}(x, y, z) = x + 2 + y − z^{2}. \end{matrix}

We see that G^{(2)} and H^{(2)} are factors of F : F (x, y, z) = G^{(2)}(x, y, z)H^{(2)}(x, y, z). □

In order to find factors from the modular factors correctly, we need several additional steps, but Example 2 explains the essence of a multivariate modular method.

Example 2 gives us an impression that the computation there is performed not to derive the answer through many procedual steps but to construct the target expression directly. In fact, G^{(0)} and G^{(1)} are parts of the answer G^{(2)}. This style of computation allows us to get the answer very quickly. We comment that Risch’s algorithm for computing indefinite integrals of elementary functions also constructs the final answer directly.

3.4 Main fault - impracticality

Today, numeric computation is an infrastructural technology in scientific and industrial worlds. On the other hand, algebraic computation has not attained such a position yet, although everybody will agree that computer algebra systems are very useful and powerful tools for theoretical researches. Why does this difference arise ? The main reason, the author thinks, is lack of practicality in algebraic computation.

Current computer algebra system seems to be satisfactory from the viewpoint of mathematics; it gives us mathematically correct answers, although it often spends large computation time. It is, however, never satisfactory from the viewpoint of practical applications. Consider, for example, solving univariate algebraic equation f(x) = 0. Even if deg(f) = 100, numeric computation gives us all the numeric roots to precision 10^{−10} within a second. On the other hand, even if f(x) is as simple as deg(f) = 5, algebraic computation may not give any answer or it will output algebraic numbers of large expression-size. From the viewpoint of practical users, numeric values of roots are much more useful, even if they are approximate, than exact roots in non-numeric expressions.

In applications, most users want to get the answers in simple, concise, and easily understandable forms within a moderate time. From the viewpoint of practical users, we can point out the followings as unsatisfactory points of conventional algebraic computation.

1. No answer is obtained sometimes: solving algebraic equations, etc.

2. Very difficult to get answer sometimes: computation on special functions, etc.

3. Large computational time is required usually ⇐ exact computation.

4. Large-sized expression is output usually ⇐ exact representation of expression.

Since these points are intrinsic properties of conventional algebraic computation, innovatory advancement of the computational method will be necessary to improve the points.

4 Where we go next ?

Summarizing the computer algebra so far, we may say

[Computer algebra so far] = [Constructive algebra] + [Efficiency]
= [Computerization of classical algebra].

Then, what happens next ? Apparently, computerization of algebra will continue, to a wider range and to a higher level, i.e., to computerization of mathematics. Furthermore, computer algebra will go outside universities and launch into new worlds, in particular, into high/middle schools and industrial world. However, launching into new worlds will require innovatory advancement of algebraic computation, as we will explain below.

4.1 Towards “computer mathematics”

We may say that computer algebra so far is, roughly speaking, restricted to handling purely algebraic expressions: we usually did not handle mathematical expressions composed of logical symbols ∨, ∧, ∀, ∃, ¬, etc., relational symbols >, ≥, ≠, etc., or set symbols ∪, ∩, ⊂, ⊆, ∈, ∉, etc. (Of course, in several branches of computer algebra, e.g., automated geometry-theorem proving, some of such expressions have already been handled so far.)

Future computer algebra, or we had better say “computer mathematics”, will surely handle logical, relational, and set-theoretic expressions. As for logical expressions, study of computational logic has been performed intensively so far, and recent study revealed that computer algebra and its techniques are useful for efficient processing of logical expressions. Therefore, research towards integration of algebraic and logical computations will begin.

4.2 When launching into high/middle schools

Today, teaching how to use computer algebra system is being included into university curriculums. However, teaching mathematics in high/middle schools by using computer algebra system is only in an early experimental stage. The existing computer algebra systems are designed to be used by highly educated users only, and they are not suited for teaching elementary mathematics. The author thinks that algebraic system for middle-level education will be almost completely different from current ones. Which kind of system is the best for such education ? This is a big question for us.

4.3 When launching into industrial world

In 3.4, we pointed out that conventional algebraic computation lacks practicality. In industrial world, practicality is one of the most important properties of computation. Remember that the most useful computational method in industrial world is numerical simulation, and it is so practical that it can be applied to almost any problem in industrial world.

Most of the conventional algebraic algorithms are for deriving exact expressions or solutions which can be obtained in idealized cases only. On the other hand, most mathematical problems in industrial world cannot be idealized, because of complicated shapes of objects or boundaries, various kinds of contaminations, and so on. In order that algebraic computation is utilized widely in industrial world, the algorithms must be flexible enough to cope with these complications, while conventional algebraic algorithms are too rigid to cope with. Furthermore, algebraic systems must be able to handle expressions with floating-point number coefficients freely, because computation in industrial world is performed mostly with floating-point number arithmetic.

One may think that we can make algebraic computation practical by combining it with numeric computation. This idea is very old; it appeared in the middle of 1970’s [SymNum]. Since then, many systems have been constructed to combine numeric programming language FORTRAN with symbolic programming language Lisp. Such systems allow us to perform only “patchwork-like” symbolic-numeric computation, that is, the computation is purely numeric in one stage and purely algebraic in another stage, and algebraic computation remains still not so practical. In order to make algebraic computation truely practical, it will be necessary to combine it with numeric computation in algorithmic level.

Combining symbolic computation with numeric one in algorithmic level is not so easy as one thinks. The reason is as follows. Conventional symbolic algorithms rely on discrete mathematics in which discreteness of integers and rational numbers plays an essential role, while numeric algorithms rely on analysis for which continuity of real and complex numbers is essential. In order to make the algebraic computation very useful industrially, the author thinks that we must develop flexible algebraic algorithms by utilizing continuity of real and complex numbers.

4.4 A new approach - approximate algebra

In order to make the algebraic algorithms flexible, the author has proposed “approximate algebra” recently and is developing various approximate algebraic algorithms in collaboration with his colleagues. The algorithms developed so far can be classified into two classes.

Class 1 : Algorithms handling polynomials and rational functions approximately.

Class 2 : Algorithms handling power-series (infinite theoretically, but truncated practically) with integral and/or fractional powers.

For algorithms in Class 1, we define norm ∥P ∥ of polynomial P as follows.

∥P ∥ =^{def} maximum of the |numeric coefficient|’s of P.

As a representative of algorithms in Class 1, we explain approximate factorization. Suppose a multivariate polynomial F (x, y, …, z) is decomposed as

F (x, y, …, z) = G(x, y, …, z)H(x, y, …, z) + δF (x, y, …, z), ∥δF ∥/∥F ∥ = ε ≪ 1.

Then, we say that F is factorized approximately into G and H with accuracy ε.

Example 3 F (x, y) = x^{3} + 3.0yx^{2} + (2.2y^{2} − 1.7)x − 2.9y, hence ∥F ∥ = 3.0. Although F is absolutely irreducuble, i.e., irreducible over C, it can be decomposed as follows.

F (x, y) = (x^{2} + 1.3yx − 1.7) × (x + 1.7y) − 0.01(y^{2}x + y).

Therefore, F is approximately factorizable with accuracy ∼ 10^{−2}. □

One may think that approximate factorization is very difficult to perform because of the existence of “extra term” δF. However, it can be done rather easily; in fact, we can perform approximate factorization efficiently by the generalized Hensel construction with floating-point number arithmetic and linear algebraic operations on numeric matrix [AppAlg].

In industrial world, we often handle polynomials determined experimentally or contaminated by various reasons. Conventional factorization algorithms are completely powerless for such polynomials; they are powerless even for polynomials with floating-point number coefficients. However, approximate factorization algorithm is applicable to such polynomials without any difficulty, telling us the norm of extra terms. It should be noted that the algorithm is useful for not only practical but also mathematical problems. For example, we can check absolute irreducibility of multivariate polynomials efficiently by using the algorithm. Furthermore, principal idea of approximate factorization leads us to a unified method of various kinds of multivariate polynomial factorizations [AppAlg].

The author thinks that “approximation” is a key to develop flexible algebraic algorithms. This may be understood by comparing numeric with algebraic algorithms of solving univariate algebraic equation; approximation changes the mathematical properties of solutions completely, enabling us to calculate approximate solutions unbelievably simply. Similarly, approximation is quite effective for solving multivariate algebraic equation. It is well-known that solutions of bivariate algebraic equation F (x, y) = 0, w.r.t. the main variable x, can be expressed by Puiseux series (fractional-power series) in y. Compared with conventional solutions expressed in radicals, solutions in Puiseux series can be calculated without any mathematical difficulty. Only one “fault” of Puiseux series solutions is that they are approximate ones because we can calculate only truncated series and not infinite series.

Conventionally, Newton-Puiseux’s method is used to calculate the Puiseux series solutions, which is very inefficient. Recently, the author has found in collaboration with his colleagues an efficient algorithm of calculating Puiseux series solutions of multivariate as well as bivariate algebraic equations. The algorithm is based on the generalized Hensel construction and is being used to solve various algebraic problems practically [AppAlg].

Selected bibliography

[Book] Books on computer algebra.

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968. B. Buchberger, G. E. Collins and R. Loos (Ed.), Computer Algebra - Symbolic and Algebraic Computation, Springer-Verlag, 1982; B. Buchberger, Gröbner bases: An algorithmic method in polynomial ideal theory, Recent Trends in Multidimensional Systems Theory, Section 6, Reidel, Dordrecht, 1985; J. H. Davenport, Y. Siret and E. Tournier, Computer Algebra - Systems and Algorithms for Algebraic Computation, Academic Press, London, 1988; S. Wolfram, Mathematica - A System for Doing Mathematics by Computer, Addison-Wesley, 1988; S. C. Chou, Mechanical Geometry Theorem Proving, Reidel, Dordrecht, 1988; R. E. Zippel (Ed.), Computer Algebra and Parallelism / Lect. Notes Comp. Sci., 584, Springer-Verlag, 1992; K. O. Geddes, S. R. Czapor and G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Pub., Boston, 1992; T. Becker and V. Weispfenning, Gröbner Bases - A Computational Approach to Commutative Algebra, Springer-Verlag, 1993.

[Appl] Review papers on earlier applications of computer algebra. W. H. Jefferys, Automated algebraic manipulation in celestial mechanics, C. ACM 14 (1971); D. Barton and J. P. Fitch, General relativity and the application of algebraic manipulation systems, ibid ; A. C. Hearn, Application of symbolic manipulation in theoretical physics, ibid .

[Systm] Papers/Manuals on systems on algebraic computation. J. R. Slagle, A heuristic program that solves symbolic integration problems in freshman calculus, J. ACM 14 (1963), 4; J. E. Sammet and E. Bond, Introduction to FORMAC, IEEE Trans.

Electr. Comp. 13 (1965), 4; A. C. Hearn, REDUCE-2 User’s Manual, Dept. Comp. Sci., Univ. Utah, 1973; The MATHLAB Group, MACSYMA Reference Manual, Lab. Comp. Sci., M.I.T., 1974; J. J. Cannon, A general purpose group theory program, Proc. 2nd Conf. on Theory of Groups / Lect. Notes Math., 372 (1974), 204; A. Rich and D. R. Stoutemyer, Capabilities of μ-MATH 79 computer algebra system for the Intel-8080 microprocessor, Proc. EUROSAM ’79 / Lect. Notes Comp. Sci. 72 (1979), 241; R. D. Jenks and B. M. Trager, A language for computational algebra, Proc. SYMSAC ’81, ACM (1981), 6; B. W. Char, K. O. Geddes, W. M. Gentleman and G. H. Gonnet, The design of Maple: a compact, portable and powerful computer algebra system, Proc. EUROCAL ’83 / Lect. Notes Comp. Sci. 162 (1983), 101.

[Factri] Papers on polynomial factorization.

E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853; H. Zassenhaus, On Hensel Factorization I, J. Number Theory 1 (1969), 291; P. S. Wang and L. P. Rothschild, Factoring multivariate polynomials over the integers, Math. Comp., 29 (1975), 935; A. K. Lenstra, H. W. Lenstra and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515.

[IntDE] Papers on integration and differential equation. R. H. Risch, The problem of integration in finite terms, Trans. AMS 139 (1969), 167; J. Davenport, On the integration of algebraic functions, Lect. Notes Comp. Sci., 102, Springer-Verlag, 1981. M. F. Singer, B. D. Saunders and B. F. Caviness, An extension of Liouville’s theorem on integration in finite terms, Proc. SYMSAC ’81, ACM (1981), 105; P. S. Wang, Symbolic evaluation of definite integrals by residue theory in MACSYMA, Proc. IFIP ’74, North-Holland (1974); M. F. Singer, Liouvillian solution of n-th order homogeneous linear differential equations, AJM 103 (1980), 661; S. Watanabe, A technique for solving ordinary differential equation using Riemann’s P-functions, Proc. SYMSAC ’81, ACM (1981), 36.

[SymNum] Review papers on symbolic-numeric computation. W. S. Brown and A. C. Hearn, Applications of symbolic algebraic computation, Comp. Phys. Commun. 17 (1979), 207; E. W. Ng, Symbolic-numeric interface : a review, Proc. EUROSAM ’79 / Lect. Notes Comp. Sci., 72 (1979), 330.

[AppAlg] Papers on approximate algebra.

T. Sasaki and M-T. Noda, Approximate square-free decomposition and root-finding of illconditioned algebraic equations, J. Inform. Proces., 12 (1989), 159; T. Sasaki and M. Sasaki, Analysis of accuracy decreasing in polynomial remainder sequence with floating-point number coefficients, J. Inform. Proces., 12 (1989), 394; M. Ochi, M-T. Noda and T. Sasaki, Approximate greatest common divisor of multivariate polynomials and its application to ill-conditioned systems of algebraic equations, J. Inform. Proces., 14 (1991), 292; T. Sasaki, M. Suzuki, M. Kolár̆ and M. sasaki, Approximate factorization of multivariate polynomials and absolute irreducibility testing, Japan J. Indust. Appl. Math., 8 (1991), 357; T. Sasaki, T. Saito and T. Hilano, Analysis of approximate factorization algorithm I, Japan J. Indust. Appl. Math., 9 (1992), 351; T. Sasaki and M. Sasaki, A unified method for multivariate polynomial factorizations, Japan J. Indust. Appl. Math., 10 (1993), 21; T. Sasaki and F. Kako, Solving multivariate algebraic equation by Hensel construction, preprint of Univ. Tsukuba (Jan., 1993); T. Kitamoto, Approximate eigenvalues, eigenvectors and inverse of a matrix with polynomial entries, Japan J. Indus. Appl. Math., 11 (1994), 73; T. Sasaki, T. Kitamoto and F. Kako, Error analysis of power series roots of multivariate algebraic equation, preprint of Univ. Tsukuba (Feb., 1994); T. Sasaki, A study of approximate polynomials, I – representation and arithmetic –, Japan J. Indust. Appl. Math., 12 (1995), 137; K. Shiihara and T. Sasaki, Analytic continuation and Riemann surface determination of algebraic functions by computer, Japan J. Indus. Appl. Math. (to appear); T. Sasaki, A study of approximate polynomials, II – properties of approximate factors –, preprint of Univ. Tsukuba (Jan., 1995), etc.