Grouping and Order Reducing Algorithm for Solving Toeplitz Type Circular Tri-diagonal Liner Algebraic Equation Systems

  • LI Wenqiang;LIU Xiao
  • College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, Henan Province, China

Received date: 2011-09-19

  Revised date: 2012-01-09

  Online published: 2012-02-18


Based on the idea of the divide and conquer method, as is commonly adopted in parallel algorithms, a grouping and order reducing sequence algorithm is proposed for solving the Toeplitz type circular tri-diagonal linear algebraic equation systems in this paper. Compared with the traditional algorithm for the same problem, the advantage of this grouping and order reducing algorithm is that the computation cost and the computer memory requirement can be reduced. The whole algorithm includes three steps. The first step is grouping and order reducing of the original system. To put it better, the coefficient matrix and the right hand side of a Toeplitz type circular tri-diagonal system of order n=μm is divided into μ subgroups. Consequently, the order of each subgroup is . The second step is the formation of the parameter equations. That is to say, according the characteristics of the tri-diagonal coefficient matrix, the relations between subgroups are obtained, and the solution components, which do not belong to the subgroups, are taken as parameters. Then, a parameter equation is formed based on the equation that includes the parameters. The third step is to solve the parameter equation. And then, the original system is solved by substituting the parameters into the corresponding subgroups. As for the tri-diagonal system, the grouping and order reducing algorithm can also reduce the requirement for the computer memory and increase the order of the system, but at the same time , increase the computation cost. Numerical experiments show that, on one hand, there is an optimal number for grouping in saving the computation cost if the order of the system is fixed. On the other hand, the optimal number for groupings increases with the increase of the order of the system.

Cite this article

LI Wenqiang;LIU Xiao . Grouping and Order Reducing Algorithm for Solving Toeplitz Type Circular Tri-diagonal Liner Algebraic Equation Systems[J]. Science & Technology Review, 2012 , 30(5) : 43 -48 . DOI: 10.3981/j.issn.1000-7857.2012.05.006