Special parallel processor for lu decomposition of a large‐scale sparse matrix
Hideki Asai, Mitsuo Asai, Mamoru Tanaka · Systems and Computers in Japan · 1987
Abstract The analysis of a nonlinear network is reduced to the solution of a system of equations at each step of Newton's method. In the solution by the direct method, the highspeed realization of the LU decomposition of an large‐scale sparse matrix has become important with the development of the integrated technology. In the past, the applications of the array processor and the supercomputer have been considered. However, the array processor cannot utilize the sparsity of the matrix, resulting in an impractical system with too many processor cells. The efficiency of the vectorization is a problem in the super‐computer, when it is used for the Gauss elimination only for the nonzero elements in the matrix. This paper proposes a dedicated processor for LU decomposition of a large‐scale sparse matrix, which can utilize the sparsity of the matrix and can be realized with a practical number of processors. The processor is composed of q local units, corresponding to the nonzero elements in each row of the coefficient matrix, and those units operate in parallel. In the processing of a sparse matrix, the matching of the label is required in the Gauss elimination. It is realized with a high speed by the data‐shift operation by the inter‐register transfer. Furthermore, a processor with a hierarchical memory structure is proposed which can cope with the case where the number p of nonzero elements in a row exceeds q.