Solving Updated Systems of Linear Equations in Parallel
P. Blaznik, Jurij Franc Tasič · 1995
In this paper, updating algorithms for solving linear systems of equations are presented using a systolic array model. First, a parallel algorithm for computing the inverse of rankone modified matrix using the Sherman-Morrison formula is proposed. This algorithm is then extended to solving the updated systems of linear equations on a linear systolic array. Finally, the generalisation to the updates of higher rank is shown. Keywords: Matrix updating, Linear systems, Systolic arrays 1 Introduction In many signal processing applications, we need to solve a sequence of linear systems in which each successive matrix is closely related to the pervious matrix. For example, we have to solve a recursive process where the matrix is modified by low-rank, typically rank-one, updates at each iteration, i.e., A k = A k\\Gamma1 + u k\\Gamma1 v T k\\Gamma1 : Clearly, we should like to be able to solve the system A k x k = b by modifying A k\\Gamma1 and x k\\Gamma1 without computing a complete refacto...