The whole topic of computer algebra is fascinating to me, but I confess
more ignorance than knowledge.
But here is part of a paper I wrote recently, for presentation at the
NEMATYC meeting this April.
------------------------------
Factoring and Antidifferentiation
I don't believe it is widely appreciated how much is known in the field of
computer algebra about factoring and anti-differentiation. The fact is that
algorithms exist for factoring any polynomial over the integers, and for
finding the antiderivative of any expression composed of algebraic and
elementary transcendental functions, if it exists, or determining that no
antiderivative exists (Steen, 1981). However, it is not easy to approach
any of the algorithms for factoring or antidifferentiation. They are
sophisticated and do not lend themselves to hand calculation. A flavor of
this is given below, related to factoring.
Antidifferentiation
Pierre Simon de la Place formulated a conjecture about the integral of
algebraic functions in the early nineteenth century. Niels Henrik Abel
proved it about 1830. This led Joseph Liouville to formulate a general
theorem about the integral of any elementary function - those built up from
the standard transcendental and algebraic functions. This theorem tells
which functions can be integrated, but does not produce the antiderivative.
(Steen, 1981)
Early CAS efforts found antiderivatives by the heuristic rules presented in
most calculus courses. Failure in these cases may only mean the
practitioner is not skilled enough - if an expression does not have a
formal antiderivative, in terms of elementary functions, these heuristics
will not tell that. Nevertheless, these rules still provide the first
attempts at finding an antiderivative for most CAS systems.
An algorithm for generating the formal antiderivative, if it exists, of any
expression of elementary functions, was completed in 1968 by Robert H.
Risch of the System Development Corp. in Santa Monica, California (Steen,
1981). A full discussion of the Risch integration algorithm is found in
Geddes (1992). This algorithm determines that an antiderivative in the form
of elementary functions does not exist, if that is the case.
It is worth noting that the algorithms of computer algebra involve many
basic concepts of college algebra, such as rings and fields, vector spaces,
eigenvalues and eigenvectors, and modular arithmetic of integers and
polynomials. The algorithm of Risch is built on elliptical function theory.
---------------------------
Here is the bibliography.
References
Buchberger, B., Collins, G.E., Loos, R. Editors, (1983). Computer Algebra :
Symbolic And Algebraic Computation. (2nd ed.). Wien: Springer-Verlag. ISBN:
038781776X (Extensive bibliography, introductory chapter about groups who
are studying computer algebra)
Cohen, H. (1995). A Course in Computational Algebraic Number Theory. New
York: Springer-Verlag. ISBN: 038755640-0
Davenport, J. H., Siret, Y., Tournier, E. (1988). Computer Algebra :
Systems And Algorithms For Algebraic Computation. (2nd ed.). London:
Academic Press. ISBN: 0122042301. (Extensive bibliography.)
Geddes, K., Czapor, S., Labahn, G. (1992) Algorithms for Computer Algebra.
Boston: Kluwer Academic Publishers. ISBN: 0-7923-9259-0
Heck, A. (1993) Introduction to Maple. New York: Springer-Verlag, ISBN
0-387-97662-0 (Good bibliography.)
Knuth, D.E. (1981). The Art of Computer Programming, Vol. II, Seminumerical
Algorithms. (2nd ed.). Reading, MA: Addison-Wesley. ISBN: 0-201-03822-6
Mignotte, M. (1992). Mathematics For Computer Algebra. Mignotte, C. trans.
New York : Springer-Verlag. ISBN: 0387976752
Steen, L. A. (1981). Computer Calculus. Science News, Vol. 119, pg.
250-251.
------------------------------------
Actually my paper is called "Factor x^8 - 3x^5 - 4x^4 - 5x^3 + x^2 + 2x + 2,
An Introduction to Computer Algebra." It's not about integration, which I
have not pursued beyond what is written above.
I got interested in how CAS's factor polynomials over the integers, and
the TI-92, and Derive, seemed pretty powerful, and they are. I made up
the polynomial above by multiplying its prime factors, to use as an example
in my paper. I rely very heavily on the demonstration in Knuth, which does
not illustrate the most powerful, newer methodology
Anyway, to my surprise, I discovered that the TI-92 won't factor this
polynomial completely, though Maple will. The theory behind a CAS is very
complicated and difficult to implement in a computer program, and it looks
like the Derive people don't have as complete an implementation as Maple.
The factors are, by the way, (x^2 + 2)(x^3 + x^2 - 1)(x^3 - x^2 - x - 1).
Philip Mahler
Middlesex CC
Bedford, MA
****************************************************************************
* To post to the list: email mathedcc@archives.math.utk.edu *
* To unsubscribe, send mail to: majordomo@archives.math.utk.edu *
* In the mail message, enter ONLY the words: unsubscribe mathedcc *
* Words in the Subject: line are NOT processed! *
* Archives at http://archives.math.utk.edu/hypermail/mathedcc/ *
****************************************************************************