Matrix Inversion Using Parallel Processing

ABSTRACT

Two general methods of matrix inversion, Gauss's algorithm and the method of bordering, are analyzed from the viewpoint of their adaptability for parallel computation. The analysis is not based on any specific type of parallel processor; its purpose is rather to see if parallel capabilities could be used effectively in matrix inversion. It is shown that both methods are indeed able to make effective use of parallel capability. With reasonable assumptions on the parallelism that is available, the speeds of the two methods are roughly comparable. The two methods, however, make use of different kinds of parallelism. To implement Gauss's algorithm we would like to have (a) parallel transfer capability for n numbers, if the matrix is n X n, (b) the capability for parallel multiplication of the accessed numbers by a common multiplier, and (c) parallel additive read-in capability. For the method of bordering, we need, primarily, the capability of forming the Euclidean inner product of two n-dimensional real vectors. The latter seems somewhat harder to implement, but, because it is an operation that is fundamental to linear algebra in general, it is one that might be made available for other purposes. If so, then the method of bordering becomes of interest.

REFERENCES

• 1: PEASE, M. C, Meshed of Matrix Algebra Academic Press, New York, 1965. (This is a good source for geerM matrix theory.)
• 2: GANTHAMACHER, F. R., The Theory of Matrices (2 vols.). Chelsea, New York, 1960. (This is a good source for genera{ mrix theory,)
• 3: CHANE, B. A,, uo GITHENS, J. A. Balk processing in distributed logic memory. IEEE Tras EC46, 2 (April 1965), 186-I96.
• 4: FADDERVA, V. N, Computational Methods of Linear Algebra. Dover, New York, 1959.
• 5: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Performance, Theory