A solver is a piece of

mathematical software Mathematical software is software used to 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 subject, but other ki ...

, 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 execute. Computer programs are one component of software, which also includes documentation and other intangible components. A computer program ...

or as a

software library In computer science, a library is a collection of non-volatile resources used by computer programs, often for software development. These may include configuration data, documentation, help data, message templates, pre-written code and subr ...

, 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 Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...

and

non-linear equation In mathematics and science, a nonlinear 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, mathematicians, and many othe ...

s. In the case of a single equation, the "solver" is more appropriately called a

root-finding algorithm In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...

. *

Systems of linear equations In mathematics, a system of linear equations (or linear system) is a collection of one 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 the ...

. *

Nonlinear system In mathematics and science, a nonlinear 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, mathematicians, and many other ...

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

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

optimisation Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

problems * Systems of

ordinary differential equation In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast w ...

s * Systems of

differential algebraic equation In electrical engineering, a differential-algebraic system of equations (DAEs) is a system of equations that either contains differential equations and algebraic equations, or is equivalent to such a system. In mathematics these are examples of ``d ...

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) is the problem of determining if there exists an interpretation that satisfie ...

s, including

SAT solver The SAT ( ) is a standardized test widely used for college admissions in the United States. Since its debut in 1926, its name and scoring have changed several times; originally called the Scholastic Aptitude Test, it was later called the Schola ...

s *

Quantified boolean formula In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified ( ...

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

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

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

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

* ''Game solvers'' for problems in

game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...

Three-body problem In physics and classical mechanics, the three-body problem is the problem of taking the initial positions and velocities (or momenta) of three point masses and solving for their subsequent motion according to Newton's laws of motion and Newton's ...

The

General Problem Solver General Problem Solver (GPS) is a computer program created in 1959 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, the GP ...

(''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 a 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 Department ...

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 Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function * Do ...

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

). 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

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

s) 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