Browse Prior Art Database

Matrix Reducibility Algorithm (MRA)

IP.com Disclosure Number: IPCOM000074977D
Original Publication Date: 1971-Jul-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 4 page(s) / 54K

Publishing Venue

IBM

Related People

Willoughby, RA: AUTHOR

Abstract

This algorithm determines if a nxn matrix, A = (a(ij)), is reducible, and, if it is, to specify the reordering which will achieve a block lower triangular form for the matrix. The square diagonal blocks are irreducible.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 4

Matrix Reducibility Algorithm (MRA)

This algorithm determines if a nxn matrix, A = (a(ij)), is reducible, and, if it is, to specify the reordering which will achieve a block lower triangular form for the matrix. The square diagonal blocks are irreducible.

It is assumed that a(jj) not = 0 for 1</-j</-n. In many applications, this is already the case, but, if not, then one first applies to A an Assignment Algorithm >1|, which is a special part of the general field of network flows >2|. Previous MRA's >3-6| also assumed a(jj) not =0. Sparseness structure information means, whether the elements are or are not zero. For notational convenience, Boolean matrices and vectors are referred to, where one means not zero. In the computer program, threaded index lists with pointers are used. The novel part of the present algorithm makes use of the sparseness structure information for L and U, where A = LU, to obtain original page 434.

Column counts for L and row counts for U can be made a biproduct of the symbolic factorization program, which generates the sparseness structure for C. If A is reducible by test (1) then the irreducible blocks can be determined by repeated use of test (3). If Ax = e(k) the x(j) = a/I/(jk) for 1</-j</-n, and if z/T/A = e/T/(k) then z(j) = a/I/(kj). The diagonal elements in the irreducible block associated with a(kk) are the a(jj)'s such that x(j) . z(j) not = 0. To obtain x, we solve Ly = e(k) for y by forward substitution and for x in Ux = y by backward substitution. The word "solve" means here "find the sparseness structure" for the vectors involved. In z/T/A = e/T/(k) we deal with w/T/U = e/T/(k) and z/T/L = w/T/.

The sparseness structure of certain components of the various vectors are either known a priori or are irrelevant to subsequent calculations. For example,
(2) provides a priori information, and if an irreducible block has been found, the sparseness structure information associated with the indices in the block is irrelevant to the determination of subsequent irreducible blocks. Thus, index skip lists can be generated during the algorithm and utilized to bypass unnecessary operations.

Finding the irreducible blocks for A means partitioning S={1,2,...n} into equivalence classes R ={R(1), R(2),...R(p)} such that i,j epsilon R(k) if and only if a(ii) and a(jj) belong to the same irreducible block of A.

Given the partition R, the reordering of A into block lower triangular form is standard. For example, one can create a pxp Boolean matrix, M, where m(micron upsilon) = 1 if and only if, for some i epsilon R(micron) and some j epsilon R(upsilon), a(ij) not = 0. M is reordered to achieve lower triangular form by successive symbolic Gaussian reduction, using at each step as pivot the unique nonzero element in a singleton row. In the case where (1,1) element is pivot, the reduction is given by original page 435. where alpha = q(11) not = 0. If c=0 or b=0, then Q'=D so reduction is trivial in this case. The...