A New Parallel Algorithm For Linear Least-square Problems

In this paper,we consider a new parallel algorithm for linear Least-square problems.This algorithm can be described as follows: In the n-dimensional space,we choose any n + 1 points which are regarded as vertexes can compose of a simplex and execute exact line search in every vertex to centroid of simplex linking lines. Then we can obtain n + 1 new points which can also compose of a new simplex, we repeat the above steps until the centroid of simplex satisfy ||Vf(x)|| < e. We state that this algorithm is parallel simplex method. In order to accelerate the convergence,we combine conjugate gradient method and parallel simplex method to form parallel conjugate gradient simplex method, Which sub-ject to improve parallel simplex method. Two methods can exert the character of parallel computer because they have parallel logic themselves.In this paper, we also discuss the theory of the parallel simplex method. Undej the 2-dimensional space case, we present that simplex seriary have some properties, but we adopt some repairing measures. We proof the convergence of the parallel algorithm. At last, We give some numerical examples to indicate that the new idea is sometimes useful and helpful.