Fast parallel iterative aggregation methods for simulation of dynamical systems Conference Paper uri icon


  • A novel iterative aggregation algorithm for the numerical simulation of dynamic systems is proposed and analyzed. The algorithm exploits the special structure of the linear equation problem resulting from the discretization of the dynamic system and of the aggregation/disaggregation procedures. The algorithm has a time complexity of (I(q) + 2M(q) + 3)log N in solving linear systems with q states for N discrete-time instants using O(qN) processors, where I(q) is the parallel time complexity for inverting a q × q matrix and M(q) is the parallel time complexity for matrix multiplication of two q × q matrices. The competing parallel cyclic reduction method for the same problem has a time complexity of I(q) + 3M(q) + 4)log N. Thus the proposed algorithm has a definite speed advantage.

author list (cited authors)

  • Tsai, W. K., Huang, G., & Wei, L.

publication date

  • December 1989