Um Algoritmo Sistólico para Decomposição LU

• Kunio Okuda USP

DOI: https://doi.org/10.5753/sbac-pad.1992.22716

Abstract

In this work we present a systolic algorithm for LU decomposition of a dense n x n matrix. The execution time is 3n steps while the algorithm proposed by Kung e Leiserson uses 4n steps. The way it works is the inverse of the systolic system for matrix multiplication by the same author. The proposed system uses a meshconnected layout of the basic cells which is totally modular, using only one type of cell, while the algorithm of Kung e Leiserson uses two types of cells. After a detailed description of the proposed system, we also present a proof of its correctness.

References

Kung,H.T. Why Systolic Architecture? Computer 15,1 (Jan,1982)

Kung,H.T. & Leiserson,C.E. Systolic Array for VLSI in Duff,I.S.e Stewart,G. W.(ed.), Sparse Matrix Proceeding 1978,SIAM,1979.

Moldovan,D.I. On the Design of Algorithm for VLSI Systolic Array Proceding of the IEEE Vol.71 No.1,Jan,1983

Okuda,K. & Song,S.W. Um Algoritmo de Multiplicação de Matrizes para Implementação em VLSI, Anais do I Congresso da Sociedade Brasileira de Microeletrônica,Campinas, Julho,1986.

Okuda,K. Desenvolvimento Formal de Algoritmos Paralelos Sistólicos dissertação de mestrado, MAC,IME,USP,1989

Robert. Y. The Impact of Vector and Parallel Architecture on the Gaussian Elimination Algorithm Manchester University Press,1990

Song,S.W. Algoritmos Paralelos e Arquitetura VLSI IV Escola de Computação, São Paulo,1984

Stern,J.M. Fatoração L-U e Aplicações Relátorio tecnico RT-MAP-8606,MAP-IME-USP,1986