Computer algebra system

Encyclopedia

A

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

In the above, the word

Some include:

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

.

s in multiple variables; standard functions of expressions (sine

, exponential

, etc.); various special functions (Γ

, ζ, erf

, Bessel function

s, etc.); arbitrary functions of expressions; optimization; derivatives, integrals, simplifications, sums, and products of expressions; truncated series

with expressions as coefficients, matrices

of expressions, and so on. Numeric domains supported typically include real

, complex, interval

, rational, and algebraic.

.

A prime example for the first development was the pioneering work conducted by the later Nobel Prize laureate in physics Martin Veltman

, who designed a program for symbolic mathematics, especially High Energy Physics, called Schoonschip

(Dutch for "clean ship") in 1963.

Using LISP

as the programming basis, Carl Engelman created MATHLAB

in 1964 at MITRE

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

-Emulations of the PDP-10. MATHLAB ("

("

, accidentally named rather similarly.

The first popular computer algebra systems were muMATH

, Reduce

, Derive (based on muMATH), and Macsyma

; a popular copyleft

version of Macsyma called Maxima is actively being maintained. As of today, the most popular commercial systems are Mathematica

and Maple

, 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

introduced the first hand held calculator CAS with the HP-28 series

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

The Texas Instruments

company in 1995 released the TI-92 calculator with an advanced CAS based on the software Derive

. 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

's calculator-permitted tests, including the SAT

, some SAT Subject Tests

and the AP

Calculus

, Chemistry

, Physics

, and Statistics

exams.

**computer algebra system**(**CAS**) is a software programApplication 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 formCanonical formGenerally, 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 factorizationFactorizationIn 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 satisfactionConstraint satisfactionIn 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 functionTrigonometric functionIn 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 integrationIntegralIntegration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...

(see symbolic integrationSymbolic integrationIn 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 differentialDifferential equationA 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 limitLimit of a functionIn 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 mathematicsExperimental mathematicsExperimental 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.## Additional capabilities

Many also include:- a programming languageProgramming languageA 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 expressionsFormula editorA 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 plotsGraph of a functionIn 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
- APIsApplication programming interfaceAn 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 mathematicsApplied mathematicsApplied 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 physicsPhysicsPhysics 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 computationComputational physicsComputational physics is the study and implementation of numerical algorithms to solve problems in physics for which a quantitative theory already exists...

Some include:

- graphicComputer graphicsComputer 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 processingSignal processingSignal 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 processingImage processingIn 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 polynomialPolynomial

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 intelligenceArtificial 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 ("

**math**ematical**lab**oratory") should not be confused with MATLABMATLAB

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,...

("

**mat**rix**lab**oratory") which is a system for numerical computation built 15 years later at the University of New MexicoUniversity 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

Advanced Placement Program

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 integrationSymbolic integrationIn calculus symbolic integration is the problem of finding a formula for the antiderivative, or indefinite integral, of a given function f, i.e...

- Risch algorithmRisch algorithmThe 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 algorithmGosper's algorithmIn 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 computationLimit (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 factorizationPolynomial factorizationIn 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 algorithmBerlekamp's algorithmIn 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 divisorGreatest common divisorIn 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 algorithmEuclidean algorithmIn 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 eliminationGaussian eliminationIn 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 basisGröbner basisIn 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 algorithmBuchberger's algorithmIn 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é approximantPadé approximantPadé 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 theoremChinese remainder theoremThe 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 equationDiophantine equationIn 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 eliminationQuantifier eliminationQuantifier 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 decompositionCylindrical algebraic decompositionGiven 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 algorithmLandau's algorithmIn 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)

## See also

- Comparison of computer algebra systems
- Scientific computation
- Statistical package
- Algebraic algorithms
- Symbolic computationSymbolic computationSymbolic 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 provingAutomated theorem provingAutomated 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 intelligenceArtificial intelligenceArtificial 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

## External links

- Definition and workings of a computer algebra system
- Curriculum and Assessment in an Age of Computer Algebra Systems - From the Education Resources Information CenterEducation Resources Information CenterERIC - the Education Resources Information Center - is an online digital library of education research and information. ERIC is sponsored by the Institute of Education Sciences of the U.S. Department of Education...

Clearinghouse for Science, Mathematics, and Environmental Education, Columbus, OhioColumbus, OhioColumbus is the capital of and the largest city in the U.S. state of Ohio. The broader metropolitan area encompasses several counties and is the third largest in Ohio behind those of Cleveland and Cincinnati. Columbus is the third largest city in the American Midwest, and the fifteenth largest city...

. - Richard J. Fateman. "Essays in algebraic simplification". Technical report MIT-LCS-TR-095, 1972.
*(Of historical interest in showing the direction of research in computer algebra. At the MIT LCS web site: http://www.lcs.mit.edu/publications/specpub.php?id=663)* - The STACK computer aided assessment system.
- A collection of computer algebra systems