Um Algoritmo Sistólico para Decomposição LU

• Kunio Okuda USP

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

Resumo

Neste trabalho apresentamos um algorítmo sistólico para decomposição LU de uma matriz densa n x n. O tempo de execução é de 3n passos enquanto o algoritmo proposto por Kung e Leiserson é de 4n. O seu funcionamento é inverso ao sistema sistólico para multiplicação de matrizes do mesmo autor. O sistema proposto usa uma disposição em forma de matriz quadrada de células básicas e é totalmente modular, usando apenas um tipo de célula, ao passo que o de Kung e Leiserson usa dois tipos de célula. Após a descrição detalhada do sistema proposto, apresentamos também uma prova da sua correção.

Referências

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