Research of Algorithms in terms of Information Geometry Structure and Discrete Time Integrable Systems

点击翻译按钮获取中文摘要

Nakamura formulated the arithmetic-harmonic mean (AHM) algorithm which converges to the square of a given positive matrix by using a successive use of arithmetic mean and harmonic mean operations on the space of positive matrices. From the viewpoint of information geometry the AHM algorithm plots the midpoints of mutually dual geodesics which connect 2-points on the space. Ohara generalized the space of positive matrices to that of symmetric cones and made clear the information geometry structure of the generalized space, for example, these mean operations determine midpoints of geodesics on it.When the positivity is lost, the AHM algorithm does not converge in general. Kondo and Nakamura found that the n-th terms of the recurrence relation takes a determinantal form. The solvable logistic map has a similar property. Based on the determinantal expression and solvability it is shown that the corresponding Lyapunov exponent of the recurrence relation is positive without using invariant measure and computation of integrations.Nakamura and Tsujimoto started to investigate parallel computing by the discrete-time Toda equation (the qd algorithm), a prototype of discrete-time integrable systems which work as numerical algorithms. They construct a parallel computer system with a dispersive memory and two CPUs. Decomposing the qd table from side to side they computed two pieces by each CPU. Then it is shown that the computation time of a tri-diagonal matrix eigenvalue problem decreases to almost 60 percent of that of one CPU case. Moreover by decomposing the qd table aslant they showed that the parallel computation rate becomes better.These results will be useful for designing new numerical algorithms in terms of discrete-time integrable systems.