Optimal Banded Triangular Solvers on k-Dimensional Torus Networks

E.E. Santos and E.S. Santos (USA)


banded triangular solvers, kdimensional torus networks, parallel algorithms and complexity, linear algebra


We consider the problem of determining parallel complexity of solving banded triangular linear systems using substitution on a k-dimensional torus network. We present lower bounds on execution time for solving these systems, taking into account communication costs. Furthermore, optimal algorithms are designed.

Important Links:

Go Back