Geodesic
Fast method for verifying Chernikov rules in Fourier–Motzkin elimination
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 1, pp. 165-172 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of eliminating unknowns from a system of linear inequalities is considered. A new fast technique for verifying Chernikov rules in Fourier–Motzkin elimination is proposed, which is an adaptation of the “graph” test for adjacency in the double description method. Numerical results are presented that confirm the effectiveness of this technique. 
@article{ZVMMF_2015_55_1_a14,
     author = {S. I. Bastrakov and N. Yu. Zolotykh},
     title = {Fast method for verifying {Chernikov} rules in {Fourier{\textendash}Motzkin} elimination},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {165--172},
     year = {2015},
     volume = {55},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a14/}
}
TY  - JOUR
AU  - S. I. Bastrakov
AU  - N. Yu. Zolotykh
TI  - Fast method for verifying Chernikov rules in Fourier–Motzkin elimination
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 165
EP  - 172
VL  - 55
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a14/
LA  - ru
ID  - ZVMMF_2015_55_1_a14
ER  - 
%0 Journal Article
%A S. I. Bastrakov
%A N. Yu. Zolotykh
%T Fast method for verifying Chernikov rules in Fourier–Motzkin elimination
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 165-172
%V 55
%N 1
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a14/
%G ru
%F ZVMMF_2015_55_1_a14
S. I. Bastrakov; N. Yu. Zolotykh. Fast method for verifying Chernikov rules in Fourier–Motzkin elimination. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 1, pp. 165-172. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_1_a14/

[1] Chernikov S. N., Lineinye neravenstva, Nauka, M., 1968

[2] Ziegler G., Lectures on Polytopes, Springer-Verlag, New York, 1998

[3] Chernikov S. N., “Svertyvanie sistem lineinykh neravenstv”, Dokl. AN SSSR, 131:3 (1960), 518–521

[4] Chernikov S. N., “Svertyvanie konechnykh sistem lineinykh neravenstv”, Zh. vychisl. matem. i matem. fiz., 5:1 (1965), 3–20

[5] Motskin T. S., Raifa Kh., Tompson D. L., Troll R. M., “Metod dvoinogo opisaniya”, Matrichnye igry, Fizmatgiz, M., 1961

[6] Fukuda K., Prodon A., “Double description method revisited”, Combinatorics and Computer Science, Springer-Verlag, 1996, 91–111 | DOI

[7] Zolotykh N. Yu., “Novaya modifikatsiya metoda dvoinogo opisaniya dlya postroeniya ostova mnogogrannogo konusa”, Zh. vychisl. matem. i matem. fiz., 51:1 (2012), 153–163

[8] Lukatskii A. M., Shapot D. V., “Konstruktivnyi algoritm svertyvaniya sistem lineinykh neravenstv vysokoi razmernosti”, Zh. vychisl. matem. i matem. fiz., 48:7 (2008), 1167–1180

[9] Deza M., Loran M., Geometriya razrezov i metrik, MTsNMO, M., 2001