A parallel algorithm for evaluating general linear recurrence equations Academic Article uri icon


  • A block parallel partitioning method for evaluating general linear mth order recurrence equations is presented and applied to solve the eigenvalues of symmetric tridiagonal matrices. The algorithm is based on partitioning, in a way that ensures load balance during computation. This method is applicable to both shared memory and distributed memory MIMD systems. The algorithm achieves a speedup of O(p) on a parallel computer with p-fold parallelism, which is linear and is greater than the existing results, and the data communication between processors is less than that required for other methods. For solving symmetric tridiagonal eigenvalue problems, our method is faster than the best previous results. The results were tested and evaluated on an MIMD machine, and were within 79% to 96% of the predicted performance for the second order linear recurrence problem.

published proceedings


author list (cited authors)

  • Lu, M., Qiao, X. Z., & Chen, G. R.

citation count

  • 0

complete list of authors

  • Lu, M||Qiao, XZ||Chen, GR

publication date

  • January 1, 1996 11:11 AM