Keywords: linear system of equations, iterative algorithms, genetic algorithms, parallel algorithm.

For solving linear system of equations there are several algorithms. Iteration algorithms are recommended for large linear systems with sparse matrix. But in the case of general non-symmetrical or matrices the classic iterative algorithms are not applicable with a few exceptions. The algorithm presented here, based on the minimization of square of residuum of the approximate solution, has some genetic character and can be highly parallel. We describe a parallel version of the proposed algorithm and give its theoretical analysis.

Let A be a general matrix. The basic problem is to solve the following linear system of equations:

where and are the solution and the given right hand side vector respectively. One of the most effective family of algorithms for (82) with symmetrical matrix A is the preconditioned conjugate gradient (CG) type algorithms see [2]. These iterative algorithms can be applied for general non-symmetrical linear systems too if we solve the normal system instead of the original one. It is known, that the most of the iterative algorithms for the solution of linear systems based on some minimization algorithm [2], that is the following problem:

where is the residual belonging to the vector x. One possible algorithm can be obtained from the observation formulated by the following theorem.

Theorem: Let and be an arbitrary matrix and vector respectively. Moreover let , arbitrary, but such different vectors for which , if and where K is an arbitrary but a given number. Let us introduce the following notations: , and

and similar expressions for the vectors , where , . Then there exists some solution of the constrained minimization problem of (83) in the subspace spanned by vectors . If the vector system is linearly independent, this solution is unique and there is the vector with , where the vector c is the solution of the following linear system , where the elements of the matrix B and the components of the vector can be calculated knowing the residuals. For the resulting vector it is fulfilled that:

Using the results of the theorem we can formulate a parallel algorithm, which generates an approximate solution sequence x_k, and in parallel its residuals, , .

The algorithm suggested based on the minimization of square of the residuum of the approximate solution in arbitrarily chosen dimension subspaces in parallel. Coupling of these parallel processes can be made, because the algorithm has got some genetic character. The fact, that the subspace dimension is freely chosen offers a scaling possibility for the algorithm and simple methods for different load balancing techniques.

1

G. Molnárka and B. Török, "Residual Elimination Algorithm for Solving Linear Equations and Application to Sparse Systems", Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM), Issue 1. Numerical Analysis, Scientific Computing, Computer Science. pp. 485-486, 1996.

2

G. Golub, A. Greenbaum, M. Luskin, eds., "Recent Advances is Iterative Methods", The IMA Volumes in Math. and its Applications, Vol.60., Springer Verlag, 1994.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)