High Efficient Algorithm Designing Based On Bisection Technique And Its Applications

With the development of the computational methods, almost all the subjects are quantitiristic and preciseristic, which stimulates the emergence of many computational sciences such as computational mathematics, computational physics and computational bioinformatics et al. The development of the computational science accelerates the subjects'interimpactting and intercrossing with each other, which lead to the development of various subjects, while the characteristcs of complexity and non-linearity in all of the subjects are more and more obvious. So the studies of the complexity science and the complex system have become a hot topic. The evolutionary analization is the basic means to explore the complexity science. Proffesor Nengchao Wang's works show that the bisection technique can describe the character and mechanism of the natural's evolution, and it is the basic pattern of evolutionary analization and the powerful flat to design high efficient algorithms. The thesis in this paper lies to discuss how to apply bisection technique to complexity science and high efficient algorithm design, for this motivation, three important complex systems are discussed, which are Walsh function system, fractal geometry and bioinformatics.The theory of Walsh function system is studied, fast algorithms for 2D Walsh transform are presented, which are faster than the traditional row-column algorithm. Three algorithms for spacefilling curves are designed as geometry algorithm, algebra algorithm and the mixed algorithm. According to the evolutionary concept, the geometry algorithm uses three steps as the definition, transformation and combination for basic units to draw the Peano's spacefilling curves. The algebra algorithm makes the Hilbert curve numberistic, and uses the matrix copy method to draw the curve, and moreover applies the concept to the coding and decoding algorithms based on the Hilbert curve, and these algorithms have the lower time complexity and the wider application bounds compared to the exist algorithms. The mixed algorithm considers the geometry character of Hilbert curve, and uses an algebra matrix to draw the cuve, and this algorithm is roughly one times faster than the L system algorithm.By the reconstruction of the coefficients of the affined transformation of iterated function systems with probability vector, this makes the dynamic iterated question a static one, and makes it a typical one rank linear recurrence question. With the example of the chaos game, a parallel algorithm is designed for this kind of recurrence question by bisection method.To improve the performances of Saitou and Nei's algorithm (SN) and Studier and Kepler's improved algorithm (SK) for constructing the Neighbor-Joining phylogenetic trees, reducing the time complexity of the computation, a fast algorithm has been developed. The experimental results show that the proposed algorithm is from tens to hundreds times faster than SN and roughly two times faster than SK when N increases. Gusfield's star based algorithm for MSA has been improved in the time and space complexity, a parallel algorithm is designed on a cluster structure machine and the experimental results shows that the algorithm can achieve high speedup ratio.