![]() | ||
Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real solutions.
Contents
The algorithm is named after Joseph Fourier and Theodore Motzkin.
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
The original system is thus equivalent to
Elimination consists in producing a system equivalent to
The inequality
is equivalent to
We have therefore transformed the original system into another system where
Complexity
Running an elimination step over
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
Suppose that the variables
A non-redundant inequality has the property that its history is minimal.
Theorem (Imbert's first acceleration theorem). If the history
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
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-preforming 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-source software for MATLAB 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