A solver is a piece of

mathematical software Mathematical software is software used to mathematical model, model, analyze or calculate numeric, symbolic or geometric data. Evolution of mathematical software Numerical analysis and symbolic computation had been in most important place of the ...

, possibly in the form of a stand-alone

computer program A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. It is one component of software, which also includes software documentation, documentation and other intangibl ...

or as a

software library In computing, a library is a collection of resources that can be leveraged during software development to implement a computer program. Commonly, a library consists of executable code such as compiled functions and classes, or a library can ...

, that 'solves' a mathematical problem. A solver takes problem descriptions in some sort of generic form and calculates 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.

Solver types

Types of problems with existing dedicated solvers include: *

Linear In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a '' function'' (or '' mapping''); * linearity of a '' polynomial''. An example of a linear function is the function defined by f(x) ...

and non-linear equations. In the case of a single equation, the "solver" is more appropriately called a

root-finding algorithm In numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function is a number such that . As, generally, the zeros of a function cannot be computed exactly nor ...

. *

Systems of linear equations In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variables. For example, : \begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three equations in ...

. *

Nonlinear system In mathematics and science, a nonlinear system (or a non-linear system) is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathem ...

s. *

Systems of polynomial equations A system of polynomial equations (sometimes simply a polynomial system) is a set of simultaneous equations where the are polynomials in several variables, say , over some field . A ''solution'' of a polynomial system is a set of values for the ...

, which are a special case of non linear systems, better solved by specific solvers. * Linear and non-linear optimisation problems * Systems of

ordinary differential equation In mathematics, an ordinary differential equation (ODE) is a differential equation (DE) dependent on only a single independent variable (mathematics), variable. As with any other DE, its unknown(s) consists of one (or more) Function (mathematic ...

s * Systems of

differential algebraic equation In mathematics, a differential-algebraic system of equations (DAE) is a system of equations that either contains differential equations and algebraic equations, or is equivalent to such a system. The set of the solutions of such a system is a ...

s *

Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

s, including

SAT solver In computer science and formal methods, a SAT solver is a computer program which aims to solve the Boolean satisfiability problem (SAT). On input a formula over Boolean data type, Boolean variables, such as "(''x'' or ''y'') and (''x'' or not ''y'' ...

s * Quantified boolean formula solvers *

Constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical questions 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 const ...

s *

Shortest path problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between t ...

s *

Minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...

problems *

Combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...

* ''Game solvers'' for problems in

game theory Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...

Three-body problem In physics, specifically classical mechanics, the three-body problem is to take the initial positions and velocities (or momenta) of three point masses orbiting each other in space and then calculate their subsequent trajectories using Newton' ...

The

General Problem Solver General Problem Solver (GPS) is a computer program created in 1957 by Herbert A. Simon, J. C. Shaw, and Allen Newell ( RAND Corporation) intended to work as a universal problem solver machine. In contrast to the former Logic Theorist project, ...

(''GPS'') is a particular computer program created in 1957 by Herbert Simon, J. C. Shaw, and

Allen Newell Allen Newell (March 19, 1927 – July 19, 1992) was an American researcher in computer science and cognitive psychology at the RAND Corporation and at Carnegie Mellon University's School of Computer Science, Tepper School of Business, and D ...

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 that separated its knowledge of problems (in the form of domain rules) from its strategy of how to solve problems (as a general search

engine An engine or motor is a machine designed to convert one or more forms of energy into mechanical energy. Available energy sources include potential energy (e.g. energy of the Earth's gravitational field as exploited in hydroelectric power ge ...

). General solvers typically use an architecture similar to the GPS to decouple a problem's definition from the strategy used to solve it. The advantage in this decoupling is that the solver does not depend on the details of any particular problem instance. The strategy utilized by general solvers was based on a general algorithm (generally based on

backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...

) with the only goal of completeness. This induces an exponential computational time that dramatically limits their usability. Modern solvers use a more specialized approach that takes advantage of the structure of the problems so that the solver spends as little time as possible backtracking. For problems of a particular class (e.g., systems of non-linear equations) multiple algorithms are usually available. Some solvers implement multiple algorithms.

References

{{DEFAULTSORT:Solver (Computer Science) Numerical software Formal methods tools

Solver types

See also

Lists of solvers

References