TITLE:
Solution Building for Arbitrary System of Linear Inequalities in an Explicit Form
AUTHORS:
Demetrius V. Shapot, Alexander M. Lukatskii
KEYWORDS:
Linear Inequalities; Convolution; Variable Elimination; Orthogonal Projection Method; Fourier Algorithm; Chernikov Rules; Dependent Inequalities; Redundant Inequalities; Almost Dependent Inequalities; Matrix Cleanup; Coarsening
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.2 No.1,
March
21,
2012
ABSTRACT: The known Fourier-Chernikov algorithm of linear inequality system convolution is complemented with an original procedure of all dependent (redundant) inequalities deletion. The concept of “almost dependent” inequalities is defined and an algorithm for further reducing the system by deletion of these is considered. The concluding algorithm makes it possible to hold actual-time convolution of a general inequality system containing up to 50 variables with the rigorous method of dependent inequalities deletion and up to 100 variables with the approximate method of one. The main application of such an approach consists in solving linear inequality system in an explicit form. These results are illustrated with a series of computer experiments.