UC Berkeley computer algebra papers

Here's an index to some recent and some older papers. A number of them have appeared in Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), an annual conference usually co-sponsored by the Association for Computing Machinery's Special Interest Group on Symbolic and Algebraic Manipulation (SIGSAM), along with other cooperating organizations.

More recently I've come to the conclusion that just posting papers here when I think they are "ripe" is useful: I can point to them, and search-engine web bots can find them. Formal publication has become less important scientifically, even though it continues to be required for certain kinds of academic recognition.

If you wish to refer to material listed here that is not specifically marked as published, send me a note so I can tell you its current status; it could be that a more formal, archival version exists.

Not all the papers are referenced from this page; you are free to browse the papers directory -- the most recent papers have the more recent dates!

A paper that shows how one can save time computing with rational functions using poles and residues instead of numerators and denominators.

A paper that suggests one can save time multiplying polynomials if one encodes dense univariate polys as long integers instead of sequences of coefficients.

You might find amusing How can we speak math? suggesting that talking into a computer rather than typing or handwriting might have certain advantages. Not as many advantages (if we are successful, at least) as doing Handwriting + Speech for Computer Entry of Mathematics or a paper written with Lucy Zhang Survey of User Input Models for Mathematical Recognition: Keyboards, Mice, Tablets, Voice. .

A number of students and I came up with a synthesis of these ideas in a demonstration project Math Speak and Write . A number of compromises were made, and the extent to which we use Microsoft utilities makes it non-portable except to recent MS operating systems (2000, XP).

A paper written with Ronen Gradwohl on Lisp and Symbolic Functionality in an Excel Spreadsheet: Development of an OLE Scientific Computing Environment, August, 2002. (code available on request)

A paper written with John Chen on a Simple Graph Editor suitable for interfacing with a computer algebra system, August 2002 (code available on request).

A paper on Memory Cache and Lisp: Faster list processing via automatically rearranging memory, August 2002. A paper (draft) written with Ronen Gradwohl on Polynomial Multiplication: Blocking to improve cache performance, July, 2002. A paper which sets up a problem and benchmarks a variety of computer algebra systems and within the same language, tries a variety of techniques: Comparing the speed of programs for sparse polynomial multiplication, July, 2002.

(Summer, 2001) Rough drafts of two papers concerning code-generation from mathematical program descriptions are stored here: Compiling functional pipe/stream abstractions into conventional programs: Software Pipelines Code generation: evaluating polynomials

Here is a somewhat informal paper criticism of the OpenMath project . OpenMath's goals are to provide a technique for encoding all of mathematics; a kind of superset of MathML, which has recently hit the WWW. The topic and approach may have been insufficiently analytical or technical, but I suspect it was just too irritating to the sensibilities of Openmath boosters. ISSAC committee for that year declined the paper.

Richard Fateman and Eylon Caspi: Parsing TeX into Mathematics, presented at a poster session at ISSAC-99 in Vancouver. Powerpoint slides for it are available as well. or look at this html slides for it are available as well.

Richard Fateman and Timothy James: Analysis of a Web User Interface for Mathematics: Experiences with Integral Queries for TILU (Table of Integrals Look Up) , was presented at Workshop on Internet Accessible Mathematical Computation at ISSAC-99. See the powerpoint slides for a somewhat different presentation that is based loosely on the paper but shows more recent statistics and also discusses what we hope to do next.

Every so often someone asks how to write a symbolic differentiation program (often in Fortran or C, not thinking how it might really be used). It may be helpful to refer to a note that was published in 1998:

Richard Fateman: A short note on short differentiation programs in lisp, and a comment on logarithmic differentiation, which among other things provides a complete program for differentiation in 528 characters (including 38 spaces) on 14 text lines. Not counting punctuation marks, there are 128 tokens. It may not be what you need since it does no simplification, but maybe reading the paper would make you think about that.

Richard Fateman: Network Servers for Symbolic Mathematics, ISSAC-97, Hawaii July, 1997.

Richard Fateman: A review of the CD ROM version of the 5th edition of the Gradshteyn and Rhyzik Table of Integrals and Series. This is a (mostly negative) review of the technological transformation of a book to an electronic form. It could have been much better. I sent this to the SIGSAM Bulletin. There is in fact another version being put together by Daniel Zwillinger, taking into account some of the issues raised in the review.

My current views of what computer algebra systems should do for problem solving environments appears in this paper recently (1999) revised for a book-length collection of PSE papers edited by E. Houstis and published by Kluwer Problem Solving Environments and Symbolic Computation .

Here's a paper on the use of symbolic execution for diagnostics, and a kind of shortcut implementation using the "Not a Number" or NaN operands in IEEE 754 standard binary floating-point numbers: Symbolic Execution and NaNs: Diagnostic Tools for Tracking Scientific Computation. After sitting around for 8 years or so, this was presented as a poster at ISSAC-99. See the powerpoint slides for a somewhat different presentation that arose as I was reviewing the paper for presentation.

Here's a paper on some work showing how one might incorporate (for example) David H. Bailey's MPFUN multiprecision floating point package into Lisp: Importing Pre-packaged Software into Lisp: Experience with Arbitrary-Precision Floating-Point Numbers. This was presented as a poster at ISSAC-2000 (St. Andrews, Scotland UK, August, 2000). I have since tried the GMP package with some success (August 2002).

Why Computer Algebra Systems Can't Solve Simple Equations ACM SIGSAM Bulletin. vol. 30, no. 2, June 1996, Issue 116, 8-11.

Richard Fateman and Mark Hayden: Speeding up Lisp-based Symbolic Mathematics ACM SIGSAM Bulletin. vol. 30 no. 1 (issue 115) March, 1996 25-30.

A survey of Symbolic Mathematics System Evaluators appears in Proceedings ISSAC-96. Actually, this on-line version is 16 pages long and contains about twice as much material as was permitted for publication in the Proceedings. A newer (longish) version appears as a chapter in Michael Wester's ``Computer Algebra Systems'' published by Wiley, 1999.

Ted Einwohner and Richard Fateman: Searching Techniques for Integral Tables appeared in ISSAC-95.

H-C (Phil) Liao and Richard Fateman: Evaluation of the Heuristic Polynomial GCD appeared in ISSAC-95.

Richard Fateman, Kevin A. Broughan, Diane K. Willcock, and Duane Rettig: Fast Floating-Point Processing in Common Lisp appeared in ACM Trans. on Math. Software, vol 21 no. 1, March 1995, 26-62.

Adam Dingle and Richard Fateman: Branch Cuts in Computer Algebra appeared in ISSAC-94.

Benjamin Berman and Richard Fateman: Optical Character Recognition for Typeset Mathematics appeared in ISSAC-94.
But you might prefer the longer, more recent, and more polished paper (with Taku Tokuyasu, Benjamin P. Berman, and Nicholas Mitchell) Optical Character Recognition and Parsing of Typeset Mathematics. that appeared Journal of Visual Communication and Image Representation vol 7 no. 1 (March 1996), pages 2-15. (This is the version as sent to them.) They re-typeset it by hand.

In 1993 I attended a conference on problem solving environments (3rd IMACS International Conference on Expert Systems for Numerical Computing), and wrote a paper for that, relating computer algebra to such matters. In my view, researchers "selling" Problem Solving Environments, and the people "buying" for them (i.e. the funding agencies) are not particularly matched up with a commitment to computer algebra. I think they would rather spend money on the nearly infinite sink of parallel computing. Anyway, the paper has continued to grow and change. I've sent it to various places for publication, but so far no one has been so keen on it as to publish it. Frankly, there are lot of small neat ideas that can and should be adopted by a problem solving environment. There are no revolutionary general ideas that have emerged. That is not to say that there are no really good specific ideas for particular tasks. Anyway, you can read a version of it as Problem Solving Environments and Symbolic Computing. And as previously noted, a more concise and recently updated version of some of the ideas, plus some new ones, appears in the Excerpts from a proposal to the National Science Foundation on Programming Environments and Tools for Advanced Scientific Computation .

Here's a paper that influenced the Macintosh graphing program that comes with every PowerPC based system. This paper, Honest Plotting, Global Extrema, and Interval Arithmetic appeared in ISSAC-92.

A serious critique of Mathematica appears in Review of Mathematica from the J. of Symbolic Computation (13, no. 5, May 1992) in PDF form. Although it is now a decade old (and is a review of a computer program that continues to evolve), I think a careful reading shows that the broad comments are still valid.

Some people (Dec '96) on sci.math.symbolic have expressed interest in computing with 1/0. Here is a (previously) unpublished paper by R. Fateman and Tak W. Yan from 1994 that discusses such things: Computing with the Extended Rational Numbers.

Here's a link to A Lisp-language Mathematica-to-Lisp Translator, a paper which first appeared in SIGSAM Bulletin 24, no. 2 p 19-21 (April, 1990). It ws also reprinted in Computer Algebra Nederland Nieuwsbrief 6, October, 1990.

On the Design and Construction of Algebraic Manipulation Systems contrasts computer algebra system building approaches as prototype/hacker vs. mathematical-hierarchy approach. Some people feel I've maligned their systems in this paper because the anomalies I report have since been fixed. This was an invited paper presented at ISSAC-90 (Tokyo). The posted text is based on a slightly revised version presented to an American Society of Mechanical Engineers annual conference. The mini-proceedings, which by the way is an excellent collection of application articles, was edited by A.K. Noor, I. Elishakoff, G. Hulbert, and appears as Symbolic Computations and their Impact on Mechanics, PVP Vol. 205, Amer. Soc. of Mech. Eng. 1990.

Series solutions of algebraic and differential equations is an ISSAC '91 paper that discusses Newton and Hensel iteration in the solution of parameterized algebraic and differential equations. Newton (quadratic) convergence is only marginally faster than Hensel (linear) convergence because the Hensel iteration takes much less time per step.

Improving Exact Integrals From Symbolic Algebra Systems is a paper with W. Kahan that appeared as technical report PAM 386, (1986) of the Center for Pure and Applied Mathematics University of California, Berkeley, The paper has changed since that time, but is in some respects still a work in progress. This will be presented as a poster at ISSAC-2000 (St. Andrews, Scotland UK, August, 2000)

Symbolic Computation of Divided Differences is a rather old paper (circa 1985, but with parts from circa 1975) with W. Kahan that has not appeared in print. I recently successfully converted it to PDF.