Geodesic
Simplicial fixed point algorithm with $2^d$ integer labels
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 1, pp. 127-144

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

Simplicial fixed point algorithms can be based on either integer or vector labels. An apparent advantage of the algorithms with integer labels is their simplicity and stability under round-off errors due to the discrete nature of integer labels. At the same time, the application of all existing algorithms with integer labels is limited by some rigidness of their construction, in particular, in the $d$-dimensional space they can bear only from $d+1$ to $2d$ labels. The numbers of labels comparable with the dimension of space make these algorithms not very fast, especially in high-dimensional tasks. This paper overcomes this rigidness and builds a new simplicial fixed point algorithm with $2^d$ integer labels. To achieve this goal, the paper proves new properties of triangulation $K_1$ and separates all approximations of fixed points into weak and strong ones. This separation, which has never been used until this moment, is caused by the high number of labels of the new algorithm.
Mots-clés : triangulations, fans
Keywords: polytopes, simplicial algorithms, fixed point algorithms. 
@article{UZKU_2019_161_1_a9,
     author = {M. N. Matveev},
     title = {Simplicial fixed point algorithm with $2^d$ integer labels},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {127--144},
     publisher = {mathdoc},
     volume = {161},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a9/}
}
TY  - JOUR
AU  - M. N. Matveev
TI  - Simplicial fixed point algorithm with $2^d$ integer labels
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2019
SP  - 127
EP  - 144
VL  - 161
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a9/
LA  - ru
ID  - UZKU_2019_161_1_a9
ER  - 
%0 Journal Article
%A M. N. Matveev
%T Simplicial fixed point algorithm with $2^d$ integer labels
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2019
%P 127-144
%V 161
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a9/
%G ru
%F UZKU_2019_161_1_a9
M. N. Matveev. Simplicial fixed point algorithm with $2^d$ integer labels. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 1, pp. 127-144. http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a9/