Solver
Encyclopedia
A solver is a generic term indicating a piece of mathematical software
, possibly in the form of a stand-alone computer program
or as a software library, that 'solves' a mathematical problem. A solver takes problem descriptions in some sort of generic form and calculate their solution. In a solver, the emphasis is on creating a program or library that can easily be applied to other problems of similar type.
Types of problems with existing dedicated solvers include:
The General Problem Solver
(GPS) is a particular computer program created in 1957 by Herbert Simon, J.C. Shaw, and Allen Newell intended to work as a universal problem solver, that theoretically can be used to solve every possible problem that can be formalized in a symbolic system, given the right input configuration. It was the first computer program which separated its knowledge of problems (in the form of domain
rules) from its strategy of how to solve problems (as a general search engine
).
General solvers typically use an architecture similar to the GPS to decouple a problem's definition from the strategy used to solve it. While the strategy utilized by GPS was a general algorithm with the only goal of completeness, modern solvers tend to use a more specialized approach tailored to the specific problem class which the solver aims for. The advantage in this decoupling is that the solver doesn't depend on the details of any particular problem instance.
For problems of a particular class (e.g., systems of non-linear equations) there are usually a wide range of different algorithms available; sometimes a solver implements multiple algorithms, but sometimes just one.
Mathematical software
Mathematical software is software used to model, analyze or calculate numeric, symbolic or geometric data.-Computer algebra systems:Many mathematical suites are computer algebra systems that use symbolic mathematics. They are designed to solve classical algebra equations and problems in human...
, possibly in the form of a stand-alone computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
or as a software library, that 'solves' a mathematical problem. A solver takes problem descriptions in some sort of generic form and calculate their solution. In a solver, the emphasis is on creating a program or library that can easily be applied to other problems of similar type.
Types of problems with existing dedicated solvers include:
- LinearLinear equationA linear equation is an algebraic equation in which each term is either a constant or the product of a constant and a single variable....
and non-linear equations. In the case of a single equation, the "solver" is more appropriately called a root-finding algorithmRoot-finding algorithmA root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
. - Systems of linear equations.
- Nonlinear systems.
- Systems of polynomial equationsSystems of polynomial equationsA system of polynomial equations is a set of simultaneous equations f1 = 0, ..., fh = 0 where the fi are polynomials in several variables, say x1, ..., xn, over some field k....
, which are a special case of non linear systems, better solved by specific solvers. - Linear and non-linear optimisationOptimization (mathematics)In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
problems - Systems of ordinary differential equationOrdinary differential equationIn mathematics, an ordinary differential equation is a relation that contains functions of only one independent variable, and one or more of their derivatives with respect to that variable....
s - Systems of differential algebraic equations
- Logic/satisfiabilityBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
problems - Constraint satisfaction problemConstraint satisfaction problemConstraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
s - Shortest path problemShortest path problemIn graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
s - Minimum spanning treeMinimum spanning treeGiven a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
problems - Search algorithmSearch algorithmIn computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
s
The General Problem Solver
General Problem Solver
General Problem Solver was a computer program created in 1959 by Herbert Simon, J.C. Shaw, and Allen Newell intended to work as a universal problem solver machine. Any formalized symbolic problem can be solved, in principle, by GPS. For instance: theorems proof, geometric problems and chess...
(GPS) is a particular computer program created in 1957 by Herbert Simon, J.C. Shaw, and Allen Newell intended to work as a universal problem solver, that theoretically can be used to solve every possible problem that can be formalized in a symbolic system, given the right input configuration. It was the first computer program which separated its knowledge of problems (in the form of domain
Problem domain
A problem domain is the area of expertise or application that needs to be examined to solve a problem. A problem domain is simply looking at only the topics you are interested in, and excluding everything else. For example, if you were developing a system trying to measure good practice in...
rules) from its strategy of how to solve problems (as a general search engine
Software engine
In computer science, a software engine refers to the core of a computer program. Software engines drive the functionality of the program, and are distinct from peripheral aspects of the program, such as look and feel.- Elucidation :...
).
General solvers typically use an architecture similar to the GPS to decouple a problem's definition from the strategy used to solve it. While the strategy utilized by GPS was a general algorithm with the only goal of completeness, modern solvers tend to use a more specialized approach tailored to the specific problem class which the solver aims for. The advantage in this decoupling is that the solver doesn't depend on the details of any particular problem instance.
For problems of a particular class (e.g., systems of non-linear equations) there are usually a wide range of different algorithms available; sometimes a solver implements multiple algorithms, but sometimes just one.
See also
- Mathematical softwareMathematical softwareMathematical software is software used to model, analyze or calculate numeric, symbolic or geometric data.-Computer algebra systems:Many mathematical suites are computer algebra systems that use symbolic mathematics. They are designed to solve classical algebra equations and problems in human...
for other types of mathematical software. - Problem Solving EnvironmentProblem Solving EnvironmentA Problem Solving Environment is a specialized computer software for solving one class of problems, combining automated problem-solving methods with human-oriented tools for guiding the problem resolution....
: a specialized software combining automated problem-solving methods with human-oriented tools for guiding the problem resolution. - Satisfiability Modulo TheoriesSatisfiability Modulo TheoriesIn computer science, the Satisfiability Modulo Theories problem is a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality...
for solvers of logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality.