Matrix inversion by systolic rank annihilation

Abstract

The sysiolic principle is applied to ihe inversion of matrices by the methods of rank annihilation. The systolic arrays presented are particularly effective for computing ihe inverse of a matrix which differs only partially from a matrix with a known inverse. It is shown that the RANK-1and RANK-2 annihilation schemes compete favourably with existing systolic schemes for arbitrary matrix inversion, by trading basic inner product cells for simple delay registers which consume less area. For Rank-1 annihilation we show that the computation time is , and for Rank-2 where n is ihe order of the matrix and r the number of applications of the annihilation formula.

The technique generalises to arbitrary matrix inversion resulting in 0(n ²) computational schemes but unfortunately they do not compete with the systolic Gaussian Eliminalion methods which are of 0(n). However they provide a more general architecture applicable to non-linear problems where partial changes in matrices can easily be constructed with a relatively small amount of hardware.

Keywords:

• Systolic control ring (SCR)
• sysiolic rank annihilation
• OCCAM program simulation

C.R. Categories: