DEPENDENCY-BASED ALGORITHMS FOR VECTOR PROCESSING OF SPARSE-MATRIX FORWARD-BACKWARD SUBSTITUTIONS

In this paper two algorithms for forward/backward substitutions and th eir implementation on vector computers are considered. A dependency-ba sed substitution algorithm (DBSA) is proposed and compared with the we ll known W-matrix method. According to DBSA, the non-zero entries of t he factor matrices are rearranged in groups of elements (slices) leadi ng to independent operations. In the implementation of the W-matrix me thod, the non-zero elements of the inverse factors are grouped in sets (pseudocolumns) to overcome the problem of dependency between additio n operations. Test cases, performed on a CRAY X-MP2/216 and a CRAY Y-M P8/464 vector computer, are taken from real life power system problems and consist in the solution of linear systems with up to 12,000 equat ions. The maximum speed-ups achieved (with respect to a code based on standard sparsity programming) are near to 7 for complex arithmetic an d to 11 for real arithmetic.