Browse Prior Art Database

Permuting Matrices Stored in Sparse Format

IP.com Disclosure Number: IPCOM000079413D
Original Publication Date: 1973-Jun-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 4 page(s) / 19K

Publishing Venue

IBM

Related People

Gustavson, FG: AUTHOR

Abstract

The following algorithm calculates a sparse row-wise representation* of matrix B = PAQ/-1/. Input to the algorithm is permutation vectors p, q (representing the permutation matrices P,Q), and matrix A in sparse row-wise representation.

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 58% of the total text.

Page 1 of 4

Permuting Matrices Stored in Sparse Format

The following algorithm calculates a sparse row-wise representation* of matrix B = PAQ/-1/. Input to the algorithm is permutation vectors p, q (representing the permutation matrices P,Q), and matrix A in sparse row-wise representation.

The new algorithm alpha is based on being able to compute (PA)/T/ in O(N) operations, where T denotes transpose. In fact, the algorithm HALFP performs that operation in 2N passes over the matrix
A. The algorithm alpha consists of applying algorithm HALFP twice, first with P and A, then with O and A/T/P/T/. Then, since R/-1/ = R/T/ for all permutation matrices R, (QA/T/P/T/) = PAQ/-1/ = B is obtained. Description of Algorithm alpha.

Step 1: Apply HALFP on permutation p and matrix A to get result (PA)/T/.

Step 2: Apply HALFP on permutation q and matrix (PA)/T/ to get result [Q(PA)/T/]/T/ = PAQ/-1/

Description of Algorithm HALFP

HALFP 1: Determine column counts of matrix A in vector IAT. (Note: column counts of PA = column count of A.) HALFP 2: Calculate row pointers of (PA)/T/ from the column counts obtained in HALFP 1. Place these row pointers

in IAT in locations 2 to s+1. (Assume matrix A is

rxs.)

HALFP 3: Calculate column indices in array JAT and numerical values in array AT of (PA)/T/, using the row pointers

obtained in HALFP 2. Specifically: Let j(1)...,j(k)

be the column indices, v(1),... v(k) be the numerical

values of row i of PA. Then

FOR i = 1,...,r DO

FOR l = 1,...,k DO

JAT(IAT(j(l) + 1))<i

AT(IAT(j(l) + 1))<v(l)

IAT(J(l) + 1)<IAT(J(l) + 1) + 1. *A sparse row-wise representation of a matrix A is given by three one dimensional arrays. Two arrays list the column indices of the nonzero matrix entries and their numerical values. The arrangement of these elements is row-wise. The third array is a set of address pointers, and the i/th/ element of the array is the address of the column index and numerical value of the first nonzero element of the i/th/ row of


A.

HALFP 4: Set IAT(1) = 1.

To get PAQ/-1/ from Q and (PA)/T/ it is not necessary to perform step 1 of HALFP. Instead, it can be obtained directly from p and the row pointers of A. Then the algorithm costs about 3N.

1

Page 2 of 4

This procedure generalizes to the problem of sorting r lists of positive integers, whose values range from 1,...,s. Using this method these lists can be sorted in O(N) operations where

(Image Omitted)

and Upsilon(i) is the number of elements in the i(th) list. The i/th/ list of integers can be considered as the column indices of row i of the sparse matrix A. Now set p and q equal to identity permutations of order r and s and apply algorithm alpha. The result of algorithm alpha leaves the r...