Browse Prior Art Database

Square Sparse Boolean Matrix Representation

IP.com Disclosure Number: IPCOM000074661D
Original Publication Date: 1971-May-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Christ, DM: AUTHOR [+2]

Abstract

A square Boolean matrix containing a small number of 1's is considered "sparse" and "wastes" core space if represented in its usual form. The following example shows a way to represent a sparse matrix in a manner that not only efficiently uses core space but also facilitates accessing the matrix, particularly if it is a large one. Given the following order 4 matrix: 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0. Rows and columns are consecutively numbered beginning at the top left. This matrix can be represented by the following series of numbers: Row Series -2, -1, 3, -3, -1 Column Series -2, 4, -1, -2, 3, 0 Row Vector 1, 2, 4, 5 Column Vector 1, 3, 4, 6. The row series is gotten by scanning the rows from left to right. If a row is all 0's, a 0 is placed in the series.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 58% of the total text.

Page 1 of 1

Square Sparse Boolean Matrix Representation

A square Boolean matrix containing a small number of 1's is considered "sparse" and "wastes" core space if represented in its usual form. The following example shows a way to represent a sparse matrix in a manner that not only efficiently uses core space but also facilitates accessing the matrix, particularly if it is a large one. Given the following order 4 matrix: 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0
0. Rows and columns are consecutively numbered beginning at the top left. This matrix can be represented by the following series of numbers: Row Series -2, -1, 3, -3, -1 Column Series -2, 4, -1, -2, 3, 0 Row Vector 1, 2, 4, 5 Column Vector 1, 3, 4, 6. The row series is gotten by scanning the rows from left to right. If a row is all 0's, a 0 is placed in the series. Each 1 in a row is assigned the column number and either a positive or negative sign. The column number assigned to the first 1 encountered in a row is made negative and any additional column numbers for additional 1's are positive.

The column series is obtained in a similar manner by scanning consecutive columns and assigning row numbers to the 1's.

Note that the matrix can be represented by either the row series only or by the column series only. By using either representation, a fast matrix addition can be obtained. By using both row and column series representations, a fast multiplication can be obtained.

To speed access to these series, row and column vectors are...