Volume 11 number 1
Pages: 61-66
An Optimal Linear Estimation Approach to the Parallel Solution of Linear Algebraic Systems of Equations
Atair Rios Neto(1) e Wilson Rios Neto(2)
| Resumo: | Estimação linear ótima estocástica de parâmetros é utilizada para gerar um novo método iterativo, para a solução paralela de sistemas algébricos de equações. No limite, a abordagem proposta leva a algoritmos iterativos que resolvem em paralelo sistemas lineares, variável por variável. É mostrado, tanto no caso de sistemas determinados como no de sistemas indeterminados, que o método iterativo de solução paralela desenvolvido é equivalente, em cada iteração, a se aplicar a uma função objetivo quadrática, e definida positiva, um método de Newton modificado, com convergência garantida. A motivação é se ter um método que explore as possibilidades oferecidas por processamento paralelo, que pode ser útil na solução eficiente de sistemas de larga escala, especialmente aqueles envolvendo matrizes de coeficientes esparsas.É mostrado também que a abordagem mais geral por estimação estocástica leva a um método que generaliza e que, em consequência, se espera ter melhor desempenho que o método usual de Jacobi. Embora sejam apresentados exemplos numéricos, este trabalho não trata do aspecto de testes e avaliação de desempenho numérico e está focado no desenvolvimento heurístico e na verificação de convergência do método proposto. |
| Palavras Chave: | Sistemas Lineares, Solução Paralela de Sistemas Lineares, Método Generalizado de Jacobi. |
| Abstract: | Stochastic optimal linear estimation of parameters is used to generate a new iterative method for the parallel solution of systems of linear algebraic equations. In the limit the approach proposed leads to iterative algorithms which in parallel can solve linear systems, variable by variable. It is shown, for both determined and undetermined systems, that the parallel iterative method developed is in each iteration equivalent to apply to a quadratic positive definite functional a modified Newton method, with guaranteed convergence. The motivation is to have a method which explores the possibilities offered by parallel processing and that can be useful in the efficient solution of large scale systems, especially those with sparse coefficient matrices. It is shown also that the more general stochastic approach taken leads to a method which generalizes and which as a consequence is expected to perform better than the usual Jacobi method. Though numerical examples are presented, this paper does not yet address the aspect of testing and evaluation of numerical performance and is focused in presenting the heuristic development and verification of convergence of the proposed method. |
| Keywords: | Algebraic linear systems; Parallel solution of linear systems; Generalized Jacobi method. |
PDF copy (77 kbytes)
Click here to obtain
|
Last modifications: by jro |