4
$\begingroup$

In Computer Architecture course, I have learnt how computer performs numerical computations.
While using MATLAB, I was introduced to symbolic mathematics toolbox.
I was amazed to see it manipulating trigonometric expressions, indefinite integration etc.
What sorts type of algorithms are used for doing symbolic mathematics.
Is there any text or article available of how symbolic mathematics is performed in computer algebra systems.

$\endgroup$
4
  • 2
    $\begingroup$ 1. This question is too broad to be a good fit for this site -- entire books could be written about the subject, and have been. 2. What research have you done? We expect you to do a significant amount of research before asking, and to show us in the question what you've done. In this case there is even an article on Wikipedia with the obvious name on this subject: en.wikipedia.org/wiki/Computer_algebra_system If Wikipedia has information at the obvious place, that's usually a sign that you haven't done enough research before asking. $\endgroup$ – D.W. Feb 28 '15 at 6:47
  • $\begingroup$ @D.W.: Truth to be told, the wikipedia article you linked to is one of the crappy/underdeveloped ones, especially in terms of references. en.wikipedia.org/wiki/Symbolic_computation is a bit better both in terms of what's being asked here and the quality of the references therein. The book by von zur Gathen and Gerhard referenced there is pretty good; there's now a 3rd (2013) edition out. $\endgroup$ – Fizz Feb 28 '15 at 11:35
  • $\begingroup$ The two books by Cohen are more introductory in nature, so if you math background isn't strong, they're a better starting point. $\endgroup$ – Fizz Feb 28 '15 at 12:05
  • $\begingroup$ Also, there's some confusion over the synonymy (or lack thereof) between "computer algebra" and "symbolic computation". A position paper by Stephen M. Watt has a bit more on this (p.3) $\endgroup$ – Fizz Feb 28 '15 at 12:43
2
$\begingroup$

Note: For this answer I chose to assume that the question was somewhat naive, since, as remarked by @D.W. in his comment, the OP should otherwise search for himself in wikipedia and other places on the web, and the spectrum of problems and techniques is far too wide for an answer here. So I am focussing on the fundamental aspects, obvious to a seasoned computer scientist, but somewhat magical for someone with less technical experience, and seeming to border artificial intelligence, when it is often just the application of appropriate recipes (well, often complex ones). One meta-remark: users who ask questions should give some information regarding their experience (or their age, as a weak indicator). It is often difficult to assess the level appropriate for an answer.

A fundamental question is whether there is any difference between numerical computation and algebraic manipulation.

As a computer scientist (to be ?) you shold more than anyone else be aware that all that is done by the computer, or by the mathematician, is to manipulate representations of abstract entities.

You learn in "algorithmics and data structures" that to deal efficiently with a problem, you have to find a proper representation for the data (e.g. a graph, an array, a string, a hash-table, a binary-tree, etc.) and to manipulate this representation appropriately (which impacts the choice of the proper representation) to get a representation of the result.

Numerical calculation is no different. You represent numbers by sequences of symbols (though some systems use two dimensional representations). Then you define various manipulation schemes of these sequences that corresponds to numerical operations you are interested in.

The invention of the representation 0 for a number measuring the absence of any content, and of positional numeration system (i.e. representation of numbers) was a major step in mathematics, and allowed for more effective encoding techniques for numerical data, and of simpler manipulation techniques for doing the operations.

This oganization is universal: we always work on representations. The computer does nothing else, even when doing simple arithmetics.

So the answer to your question is simply, as always: choose a representation for whatever concepts you want to manipulate an design the algorithms that manipulate these representations in a way that corresponds to the abstract manipulations you are interested in.

Typically, if you want to manipulate algebraic expressions containing constants, variables (identifiers) and operators, you can just represent them as a rooted tree structures with constants and variables on the leaves, and the operators on the nodes. That is easy, though more complex representations may sometimes be useful.

Now you may consider your expression as representing a function of a variable x, that appears among the variables, and you want to compute the derivative of that expression for x. You can probably imagine the algorithm yourself, if you know the rules for computing a derivative, when you do it by hand. This is a fairly simple recursive procedure, since the derivative of an expresson can be defined from the subexpressions and their derivatives, in a way that depends on the top operator.

You can do things similarly for some trigonometric computations, applying various rules and strategies for transforming trigonometric expressions (such as: $\cos(a+b)=\cos a\cos b-\sin a\sin b$ ), that were used by hand by people (including myself) before computers were available to do it.

Now, many of these manipulation problems are actually hard to solve. But that comes from the diffculty of mathematics, not from the fact that it is mechanized in a formal calculation system. There involve a wide variety of techniques and mathematical theories, that have to be adressed individually, and certainly not together in a single question.

As a final remark, we should remember that much of the theory of computation originates with the search for answers to the Entscheidungsproblem, a challenge posed by David Hilbert in 1928 about mechanisation of mathematics, and addressed by such people as Gödel, Church, Turing, and several other pioneers of the field. The fact that computing devices are now used to do just that, mechanize mathematics, was only to be expected. It is always pleasing to see some consistency between the various branches of computer science.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.