Simplicial Fixed Point Algorithm with 2d Integer Labels
Mikhail N. Matveev · Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki · 2019
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 2d integer labels. To achieve this goal, the paper proves new properties of triangulation K1 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.