| Popis: |
In this paper, we present a new algorithm based on Modified Gram-Schmidt (MGS) orthogonal matrix factorization for parallel solution of linear equations Ax = b. Unlike the existing methods, the proposed algorithm using a new technique called two-sided elimination unifies both the triangularization and back-substitution phases to produce the complete solution vector x. The new algorithm replaces the back-substitution phase in the existing methods, which requires O(N) steps using O(N) processors or O(log2 2N) steps using O(N3) processors, by only one step division. Being based on the MGS method, the new algorithm is numerically stable. Finally, we study the performance of the algorithm on hypercube multiprocessor systems. |
