New algorithms to S&T decomposition

Abstract

Resumo: Este trabalho tem como maior objetivo fazer uma nova análise e propor novos algoritmos para a Decomposição ST (Symmetric Triangular Decomposition) desenvolvido por Golub e Yuan em 2000. A decomposição ST decompõem uma matriz A quadrada e não singular (em geral, não simétrica) em um produto de matrizes A = ST onde T é uma matriz triangular e S é uma matriz simétrica e definida positiva. Em seus trabalhos Golub e Yuan apresentam dois algoritmos que fazem a decomposição ST em blocos; são necessários para isso armazenar a matriz A e resolver três sistemas lineares a cada passo da decomposição. Em nossa nova análise descobrimos que a decomposição ST pode ser feita por linhas e isso apresenta uma grande vantagem, pois não precisamos armazenar a matriz A porque utilizamos apenas uma linha de A e resolvemos dois sistemas lineares a cada passo do processo. Desenvolvemos dois novos algoritmos que apresentam um menor custo computacional e melhores resultados numéricos. Nossos resultados foram comparados com: Decomposição ST, Decomposição MST (ST Modificado), Decomposição LU sem pivotiamento, Decomposição Cholesky e Decomposição QR

Abstract: The main objective of this work is to propose new algorithms of the ST Decomposition (Symmetric-Triangular Decomposition) developed by Golub and Yuan in 2000. The decomposition ST decomposes a square and nonsingular (in general, nonsymmetric) matrix A into a matrix product A = ST where T is triangular, and S is symmetrical and positive definite. Golub and Yuan present two algorithms to obtain the decomposition ST in block-wise. Then it is necessary to store the matrix A and to solve three linear systems to each step of the decomposition. In our new algorithms, we discover that the decomposition ST can be attained by row-wise which needs just a row of A and solver of two linear systems at each step. By this way we can save multiplication and storage requirements. We develop two new algorithms that are cheaper and more stable. Our results are compared to: ST Decomposition, MST Decomposition (Modified ST), LU Decomposition without pivoting, Cholesky Decomposition, and QR Decomposition for several types of test matrices