Research On Matrix Chain Product

Matrix is a basic concept in numerical value algebra. Many scientific computing problems come down to the operations of the matrices. In many applications, a long chain of matrices are used, such as robotics, machine control and computer animation. The different sequences of the matrices can affect the amount of multiplications and the computing efficiency, so how to evaluate a chain of matrices efficiently is very important for scientific computing.So far, many scholars have proposed many kinds of sequential and parallel algorithms to solve the matrix chain problem,and new algorithms will be proposed in the future. There are two kinds of matrix chain problem, the matrix chain ordering problem and the matrix chain scheduling problem. The algorithms that have been proposed are basically based on PRAM model. The proposing and solving of the MCSP make the evaluating of the matrix chain on parallel computers more efficiently. After studying the algorithms that have been proposed to solve the matrix chain problem, we creatively proposed three new algorithms:1,The parallel algorithms that have been proposed to solve the MCOP are mainly based on PRAM model. In this paper, a parallel dynamic programming algorithm solving the MCOP is proposed on 2D mesh. The 2D mesh structure is more realistic than the PRAM model. According to the characteristic of the sequential algorithm, the new algorithm runs on an upper triangular structure of a 2D mesh in O(n2) time,while the sequential algorithm in O(n3) time.2,If all the processors evaluate the matrix products one by one, according to the solution of the MCOP, the time used may not be the least. We should also consider how to schedule all the processors to work efficiently. In this paper, the matrix chain scheduling problem and two discrete processor allocation algorithms are introduced. The algorithm which was proposed by Heejo lee is described. At last, a new greedy algorithm is proposed using the method of the bottom-up merging sort, which costs less time and make good use of the processors. The new algorithm costs O(n+plogn) time, while the algorithm proposed by Heejo lee costs O(n2+np).3,As the parallel computers develop towards MIMD structure, some scholars have proposed the algorithms solving the MCOP on MIMD computers. But there hasn't been an algorithm that allocate the tasks among the processors.In this paper, an algorithm solving the matrix chain ordering problem on MIMD computer is described and analyzed. In order to solve the task allocation problem among the computers, a new algorithm costing O(n) time is proposed and analyzed. The allocating algorithm first computes the total task, then allocates it to the processors. At last, the algorithms proposed in this paper are compared and analysed.