Computer algebra system

# Computer algebra system

Discussion
 Ask a question about 'Computer algebra system' Start a new discussion about 'Computer algebra system' Answer questions from other users Full Discussion Forum

Encyclopedia
A computer algebra system (CAS) is a software program
Application software
Application software, also known as an application or an "app", is computer software designed to help the user to perform specific tasks. Examples include enterprise software, accounting software, office suites, graphics software and media players. Many application programs deal principally with...

that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form.

## Symbolic manipulations

The symbolic manipulations supported typically include:
• simplification to a smaller expression or some standard form
Canonical form
Generally, in mathematics, a canonical form of an object is a standard way of presenting that object....

, including automatic simplification with assumptions and simplification with constraints
• substitution of symbols or numeric values for certain expressions
• change of form of expressions: expanding products and powers, partial and full factorization
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...

, rewriting as partial fractions, constraint satisfaction
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...

, rewriting trigonometric function
Trigonometric function
In mathematics, the trigonometric functions are functions of an angle. They are used to relate the angles of a triangle to the lengths of the sides of a triangle...

s as exponentials, transforming logic expressions, etc.
• partial and total differentiation
• some indefinite and definite integration
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...

(see symbolic integration
Symbolic integration
In calculus symbolic integration is the problem of finding a formula for the antiderivative, or indefinite integral, of a given function f, i.e...

), including multidimensional integrals
• symbolic constrained and unconstrained global optimization
• solution of linear and some non-linear equations over various domains
• solution of some differential
Differential equation
A differential equation is a mathematical equation for an unknown function of one or several variables that relates the values of the function itself and its derivatives of various orders...

and difference equations
• taking some limit
Limit of a function
In mathematics, the limit of a function is a fundamental concept in calculus and analysis concerning the behavior of that function near a particular input....

s
• integral transforms
• series operations such as expansion, summation and products
• matrix operations including products, inverses, etc.
• statistical computation
• theorem proving and verification which is very useful in the area of experimental mathematics
Experimental mathematics
Experimental mathematics is an approach to mathematics in which numerical computation is used to investigate mathematical objects and identify properties and patterns...

• optimized code generation

In the above, the word some indicates that the operation cannot always be performed.

Many also include:
• a programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

, allowing users to implement their own algorithms
• arbitrary-precision numeric operations
• exact integer arithmetic and number theory functionality
• Editing of mathematical expressions
Formula editor
A formula editor is a name for a computer program that is used to typeset mathematical works or formulae.Formula editors typically serve two purposes:...

in two-dimensional form
• plotting graphs and parametric plots
Graph of a function
In mathematics, the graph of a function f is the collection of all ordered pairs . In particular, if x is a real number, graph means the graphical representation of this collection, in the form of a curve on a Cartesian plane, together with Cartesian axes, etc. Graphing on a Cartesian plane is...

of functions in two and three dimensions, and animating them
• drawing charts and diagrams
• APIs
Application programming interface
An application programming interface is a source code based specification intended to be used as an interface by software components to communicate with each other...

for linking it on an external program such as a database, or using in a programming language to use the computer algebra system
• string manipulation such as matching and searching
• add-ons for use in applied mathematics
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...

such as physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

, bioinformatics, computational chemistry and packages for physical computation
Computational physics
Computational physics is the study and implementation of numerical algorithms to solve problems in physics for which a quantitative theory already exists...

Some include:
• graphic
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

production and editing such as computer generated imagery and signal processing
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...

as image processing
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...

• sound synthesis

Some computer algebra systems focus on a specific area of application; these are typically developed in academia and are free. They can be inefficient for numeric operations compared to numeric systems
Comparison of numerical analysis software
The following tables provide a comparison of numerical analysis software.- General :- Operating system support :The operating systems the software can run on natively .- Language features :Colors indicate features available as...

.

## Types of expressions

The expressions manipulated by the CAS typically include polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

s in multiple variables; standard functions of expressions (sine
Trigonometric function
In mathematics, the trigonometric functions are functions of an angle. They are used to relate the angles of a triangle to the lengths of the sides of a triangle...

, exponential
Exponential function
In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...

, etc.); various special functions (Γ
Gamma function
In mathematics, the gamma function is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers...

, ζ, erf
Error function
In mathematics, the error function is a special function of sigmoid shape which occurs in probability, statistics and partial differential equations...

, Bessel function
Bessel function
In mathematics, Bessel functions, first defined by the mathematician Daniel Bernoulli and generalized by Friedrich Bessel, are canonical solutions y of Bessel's differential equation:...

s, etc.); arbitrary functions of expressions; optimization; derivatives, integrals, simplifications, sums, and products of expressions; truncated series
Series (mathematics)
A series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....

with expressions as coefficients, matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

of expressions, and so on. Numeric domains supported typically include real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

, complex, interval
Interval arithmetic
Interval arithmetic, interval mathematics, interval analysis, or interval computation, is a method developed by mathematicians since the 1950s and 1960s as an approach to putting bounds on rounding errors and measurement errors in mathematical computation and thus developing numerical methods that...

, rational, and algebraic.

## History

Computer algebra systems began to appear in the 1960s, and evolved out of two quite different sources - the requirements of theoretical physicists and research into artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

.

A prime example for the first development was the pioneering work conducted by the later Nobel Prize laureate in physics Martin Veltman
Martinus J. G. Veltman
Martinus Justinus Godefriedus Veltman is a Dutch theoretical physicist. He shared the 1999 Nobel Prize in physics with his former student Gerardus 't Hooft for their work on particle theory.-Biography:...

, who designed a program for symbolic mathematics, especially High Energy Physics, called Schoonschip
Schoonschip
Schoonschip was one of the first computer algebra systems, developed in 1963 by Martinus J. G. Veltman, for use in particle physics."Schoonschip" literally means "clean ship" in Dutch.FORM can be regarded, in a sense, as the successor to Schoonschip....

(Dutch for "clean ship") in 1963.

Using LISP
Lisp
A lisp is a speech impediment, historically also known as sigmatism. Stereotypically, people with a lisp are unable to pronounce sibilants , and replace them with interdentals , though there are actually several kinds of lisp...

as the programming basis, Carl Engelman created MATHLAB
MATHLAB
MATHLAB is a computer algebra system created in 1964 by Carl Engelman at MITRE and written in LISP."MATHLAB 68" was introduced in 1967 and became rather popular in university environments running on DECs PDP-6 and PDP-10 under TOPS-10 or TENEX...

in 1964 at MITRE
MITRE
The Mitre Corporation is a not-for-profit organization based in Bedford, Massachusetts and McLean, Virginia...

within an artificial intelligence research environment. Later MATHLAB was made available to users on PDP-6 and PDP-10 Systems running TOPS-10 or TENEX in universities. Today it can still be used on SIMH
SIMH
SIMH is a highly portable, multi-system emulator which runs on Windows, Linux, Mac OS X, FreeBSD, OpenBSD, NetBSD, OpenVMS, and other operating systems...

-Emulations of the PDP-10. MATHLAB ("mathematical laboratory") should not be confused with MATLAB
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...

("matrix laboratory") which is a system for numerical computation built 15 years later at the University of New Mexico
University of New Mexico
The University of New Mexico at Albuquerque is a public research university located in Albuquerque, New Mexico, in the United States. It is the state's flagship research institution...

, accidentally named rather similarly.

The first popular computer algebra systems were muMATH
MuMATH
muMATH is a computer algebra system, which was developed in the late 1970s and early eighties by Albert D. Rich and David Stoutemyer of the Soft Warehouse in Honolulu, Hawaii. It was implemented in the muSIMP programming language which was built on top of a LISP dialect called muLISP...

, Reduce
Reduce computer algebra system
Reduce is a general-purpose computer algebra system geared towards applications in physics.The development of the Reduce computer algebra system was started in the 1960s by Anthony C. Hearn...

, Derive (based on muMATH), and Macsyma
Macsyma
Macsyma is a computer algebra system that was originally developed from 1968 to 1982 at MIT as part of Project MAC and later marketed commercially...

; a popular copyleft
Copyleft
Copyleft is a play on the word copyright to describe the practice of using copyright law to offer the right to distribute copies and modified versions of a work and requiring that the same rights be preserved in modified versions of the work...

version of Macsyma called Maxima is actively being maintained. As of today, the most popular commercial systems are Mathematica
Mathematica
Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...

and Maple
Maple (software)
Maple is a general-purpose commercial computer algebra system. It was first developed in 1980 by the Symbolic Computation Group at the University of Waterloo in Waterloo, Ontario, Canada....

, which are commonly used by research mathematicians, scientists, and engineers. Freely available alternatives include Sage (which can act as a front-end to several other free and nonfree CAS).

In 1987 Hewlett-Packard
Hewlett-Packard
Hewlett-Packard Company or HP is an American multinational information technology corporation headquartered in Palo Alto, California, USA that provides products, technologies, softwares, solutions and services to consumers, small- and medium-sized businesses and large enterprises, including...

introduced the first hand held calculator CAS with the HP-28 series
HP-28 series
The HP-28C and HP-28S were two graphing calculators produced by Hewlett-Packard from 1986 to 1992.The HP-28 was the first calculator capable of solving equations symbolically....

, and it was possible, for the first time in a calculator, to arrange algebraic expressions, differentiation, limited symbolic integration, Taylor series construction and a solver for algebraic equations.

The Texas Instruments
Texas Instruments
Texas Instruments Inc. , widely known as TI, is an American company based in Dallas, Texas, United States, which develops and commercializes semiconductor and computer technology...

company in 1995 released the TI-92 calculator with an advanced CAS based on the software Derive
Derive computer algebra system
Derive was a computer algebra system, developed as a successor to muMATH by the Soft Warehouse in Honolulu, Hawaii, now owned by Texas Instruments. Derive was implemented in muLISP, also by Soft Warehouse. The first release was in 1988. It was discontinued on June 29, 2007 in favor of TI-Nspire...

. This, along with its successors (including the TI-89 series and the newer TI-Nspire CAS released in 2007) featured a reasonably capable and inexpensive hand-held computer algebra system.

CAS-equipped calculators are not permitted on the ACT, the PLAN, and in some classrooms because they may affect the integrity of the test/class, though it may be permitted on all of College Board
College Board
The College Board is a membership association in the United States that was formed in 1900 as the College Entrance Examination Board . It is composed of more than 5,900 schools, colleges, universities and other educational organizations. It sells standardized tests used by academically oriented...

's calculator-permitted tests, including the SAT
SAT
The SAT Reasoning Test is a standardized test for college admissions in the United States. The SAT is owned, published, and developed by the College Board, a nonprofit organization in the United States. It was formerly developed, published, and scored by the Educational Testing Service which still...

, some SAT Subject Tests
SAT Subject Tests
SAT Subject Tests is the name for 20 multiple-choice standardized tests given on individual subjects, usually taken to improve a student's credentials for admission to colleges in the United States. Students typically choose which tests to take depending upon college entrance requirements for the...

and the AP
The Advanced Placement program is a curriculum in the United States and Canada sponsored by the College Board which offers standardized courses to high school students that are generally recognized to be equivalent to undergraduate courses in college...

Calculus
AP Calculus
Advanced Placement Calculus is used to indicate one of two distinct Advanced Placement courses and examinations offered by the College Board, AP Calculus AB and AP Calculus BC....

, Chemistry
AP Chemistry
Advanced Placement Chemistry is a course and examination offered by the College Board as a part of the Advanced Placement Program to give American and Canadian high school students the opportunity to demonstrate their abilities and earn college-level credit.-The course:AP Chemistry is a course...

, Physics
AP Physics
AP Physics defines three categories of high school physics courses: A, B, and C. Category A refers to general introductory physics courses that are not mathematically rigorous...

, and Statistics
AP Statistics
Advanced Placement Statistics is a college-level high school statistics course offered in the United States through the College Board's Advanced Placement program...

exams.

## Mathematics used in computer algebra systems

• Symbolic integration
Symbolic integration
In calculus symbolic integration is the problem of finding a formula for the antiderivative, or indefinite integral, of a given function f, i.e...

- Risch algorithm
Risch algorithm
The Risch algorithm, named after Robert Henry Risch, is an algorithm for the calculus operation of indefinite integration . The algorithm transforms the problem of integration into a problem in algebra. It is based on the form of the function being integrated and on methods for integrating rational...

• Hypergeometric summation - Gosper's algorithm
Gosper's algorithm
In mathematics, Gosper's algorithm is a procedure for finding sums of hypergeometric terms that are themselves hypergeometric terms. That is: suppose we have a + ... + a = S − S, where S is a hypergeometric term ; then necessarily...

• Limit computation
Limit (mathematics)
In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...

- Gruntz's algorithm
• Polynomial factorization
Polynomial factorization
In mathematics and computer algebra, polynomial factorization refers to factoring a polynomial into irreducible polynomials over a given field.-Formulation of the question:...

. Over finite fields, Berlekamp's algorithm
Berlekamp's algorithm
In mathematics, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields . The algorithm consists mainly of matrix reduction and polynomial GCD computations. It was invented by Elwyn Berlekamp in 1967...

or Cantor–Zassenhaus algorithm is used.
• Greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

- Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...

• Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...

• Gröbner basis
Gröbner basis
In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R...

- Buchberger's algorithm
Buchberger's algorithm
In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. It was invented by Austrian mathematician Bruno Buchberger...

; generalization of Euclidean algorithm and Gaussian elimination
Padé approximant is the "best" approximation of a function by a rational function of given order - under this technique, the approximant's power series agrees with the power series of the function it is approximating....

• Schwartz–Zippel lemma and testing polynomial identities
• Chinese remainder theorem
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...

• Diophantine equation
Diophantine equation
In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations...

s
• Quantifier elimination
Quantifier elimination
Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. One way of classifying formulas is by the amount of quantification...

over real numbers - Tarski's method/Cylindrical algebraic decomposition
Cylindrical algebraic decomposition
Given a set of polynomials in Rn and a set S in Rn the Cylindrical algebraic decomposition algorithm finds a decomposition of S in to a number of cells such that for each cell each polynomial has constant sign.-References:...

• Landau's algorithm
Landau's algorithm
In mathematics, Landau's algorithm, named after Susan Landau, is an algorithm for deciding which nested radicals can be denested.- Notes and references :*...

• Derivatives of elementary and special functions (e.g. see Incomplete Gamma function)

• Comparison of computer algebra systems
• Scientific computation
• Statistical package
• Algebraic algorithms
• Symbolic computation
Symbolic computation
Symbolic computation or algebraic computation, relates to the use of machines, such as computers, to manipulate mathematical equations and expressions in symbolic form, as opposed to manipulating the approximations of specific numerical quantities represented by those symbols...

• Automated theorem proving
Automated theorem proving
Automated theorem proving or automated deduction, currently the most well-developed subfield of automated reasoning , is the proving of mathematical theorems by a computer program.- Decidability of the problem :...

• Artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

• Constraint-logic programming