Fourier–Motzkin elimination, also known as the FME method, is a mathematical
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for eliminating variables from a
system of linear inequalities. It can output
real solutions.
The algorithm is named after
Joseph Fourier
Jean-Baptiste Joseph Fourier (; ; 21 March 1768 – 16 May 1830) was a French mathematician and physicist born in Auxerre, Burgundy and best known for initiating the investigation of Fourier series, which eventually developed into Fourier analys ...
who proposed the method in 1826 and
Theodore Motzkin
Theodore Samuel Motzkin (; 26 March 1908 – 15 December 1970) was an Israeli- American mathematician.
Biography
Motzkin's father Leo Motzkin, a Ukrainian Jew, went to Berlin at the age of thirteen to study mathematics. He pursued university ...
who re-discovered it in 1936.
Elimination
The elimination of a set of variables, say ''V'', from a system of relations (here linear inequalities) refers to the creation of another system of the same sort, but without the variables in ''V'', such that both systems have the same solutions over the remaining variables.
If all variables are eliminated from a system of linear inequalities, then one obtains a system of constant inequalities. It is then trivial to decide whether the resulting system is true or false. It is true if and only if the original system has solutions. As a consequence, elimination of all variables can be used to detect whether a system of inequalities has solutions or not.
Consider a system
of
inequalities with
variables
to
, with
the variable to be eliminated. The linear inequalities in the system can be grouped into three classes depending on the sign (positive, negative or null) of the coefficient for
.
* those inequalities that are of the form
; denote these by
, for
ranging from 1 to
where
is the number of such inequalities;
* those inequalities that are of the form
; denote these by
, for
ranging from 1 to
where
is the number of such inequalities;
* those inequalities in which
plays no role, grouped into a single conjunction
.
The original system is thus equivalent to
:
.
Elimination consists in producing a system equivalent to
. Obviously, this formula is equivalent to
:
.
The inequality
:
is equivalent to
inequalities
, for
and
.
We have therefore transformed the original system into another system where
is eliminated. Note that the output system has
inequalities. In particular, if
, then the number of output inequalities is
.
Example
Consider the following system of inequalities:
[ Pages 81–104.]
:
Since all the inequalities are in the same form (all less-than or all greater-than), we can examine the coefficient signs for each variable.
Eliminating x would yield 2*2 = 4 inequalities on the remaining variables, and so would eliminating y. Eliminating z would yield only 3*1 = 3 inequalities so we use that instead.
:
which gives the 3 inequalities:
:
Simplifying:
:
This system uses only 2 variables instead of 3. Examining the coefficient signs for each variable yields all-positive for y, so we can immediately say that the system is unbounded in y: since all y coefficients are positive and all inequalities are less-than-or-equal, setting y to negative infinity (or any sufficiently large negative number) would satisfy the reduced system, therefore there exist corresponding x and z for the larger systems as well, and there are infinitely many such solutions. E.g. setting y = -1000000, x = 0, z = -2222222 satisfies the original system as well as the reduced ones.
Complexity
Running an elimination step over
inequalities can result in at most
inequalities in the output, thus naively running
successive steps can result in at most
, a double exponential complexity. This is due to the algorithm producing many redundant constraints implied by other constraints.
McMullen's
upper bound theorem states that the number of non-redundant constraints grows as a single exponential. A single exponential implementation of Fourier-Motzkin elimination and complexity estimates are given in.
Linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
is well-known to give solutions to inequality systems in polynomial time, favoring it over Fourier-Motzkin elimination.
Imbert's acceleration theorems
Two "acceleration" theorems due to Imbert permit the elimination of redundant inequalities based solely on syntactic properties of the formula derivation tree, thus curtailing the need to solve linear programs or compute matrix ranks.
Define the ''history''
of an inequality
as the set of indexes of inequalities from the initial system
used to produce
. Thus,
for inequalities
of the initial system. When adding a new inequality
(by eliminating
), the new history
is constructed as
.
Suppose that the variables
have been ''officially'' eliminated. Each inequality
partitions the set
into
:
*
, the set of ''effectively eliminated'' variables, ''i.e.'' on purpose. A variable
is in the set as soon as at least one inequality in the history
of
results from the elimination of
.
*
, the set of ''implicitly eliminated'' variables, ''i.e.'' by accident. A variable is implicitly eliminated when it appears in at least one inequality of
, but appears neither in inequality
nor in
*
, all remaining variables.
A non-redundant inequality has the property that its history is ''minimal''.
[Jean-Louis Imbert]
''Fourier Elimination: Which to Choose?''
Theorem (Imbert's first acceleration theorem). If the history
of an inequality
is minimal, then
.
An inequality that does not satisfy these bounds is necessarily redundant, and can be removed from the system without changing its solution set.
The second acceleration theorem detects minimal history sets:
Theorem (Imbert's second acceleration theorem). If the inequality
is such that
, then
is minimal.
This theorem provides a quick detection criterion and is used in practice to avoid more costly checks, such as those based on matrix ranks. See the reference for implementation details.
Applications in information theory
Information-theoretic achievability proofs result in conditions under which the existence of a well-performing coding scheme is guaranteed. These conditions are often described by linear system of inequalities. The variables of the system include both the transmission rates (that are part of the problem's formulation) and additional auxiliary rates used for the design of the scheme. Commonly, one aims to describe the fundamental limits of communication in terms of the problem's parameters only. This gives rise to the need of eliminating the aforementioned auxiliary rates, which is executed via Fourier–Motzkin elimination. However, the elimination process results in a new system that possibly contains more inequalities than the original. Yet, often some of the inequalities in the reduced system are redundant. Redundancy may be implied by other inequalities or by
inequalities in information theory (a.k.a. Shannon type inequalities). A recently developed open-sourc
software for MATLABref> performs the elimination, while identifying and removing redundant inequalities. Consequently, the software's outputs a simplified system (without redundancies) that involves the communication rates only.
Redundant constraint can be identified by solving a linear program as follows. Given a linear constraints system, if the
-th inequality is satisfied for any solution of all other inequalities, then it is redundant. Similarly, STIs refers to inequalities that are implied by the non-negativity of information theoretic measures and basic identities they satisfy. For instance, the STI
is a consequence of the identity
and the non-negativity of conditional entropy, i.e.,
. Shannon-type inequalities define a
cone
In geometry, a cone is a three-dimensional figure that tapers smoothly from a flat base (typically a circle) to a point not contained in the base, called the '' apex'' or '' vertex''.
A cone is formed by a set of line segments, half-lines ...
in
, where
is the number of random variables appearing in the involved information measures. Consequently, any STI can be proven via linear programming by checking if it is implied by the basic identities and non-negativity constraints. The described algorithm first performs Fourier–Motzkin elimination to remove the auxiliary rates. Then, it imposes the information theoretic non-negativity constraints on the reduced output system and removes redundant inequalities.
See also
*
Farkas' lemma – can be proved using FM elimination.
*
Real closed field
In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.
Def ...
– the cylindrical algebraic decomposition algorithm performs quantifier elimination over ''polynomial'' inequalities, not just linear.
*
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...
- a similar method, but for equations rather than inequalities.
References
Further reading
*
*
*
External links
Chapter 1 of Undergraduate Convexity textbook by Niels Lauritzen at
Aarhus University
Aarhus University (, abbreviated AU) is a public research university. Its main campus is located in Aarhus, Denmark. It is the second largest and second oldest university in Denmark. The university is part of the Coimbra Group, the Guild, and Ut ...
.
FME software for Information theory open-source code in MATLAB by Ido B. Gattegno, Ziv Goldfeld and Haim H. Permuter.
Symbolic Fourier-Motzkin elimination open-source code in Python implementing the two Imbert acceleration theorems.
{{DEFAULTSORT:Fourier-Motzkin elimination
Optimization algorithms and methods
Real algebraic geometry