Browse Prior Art Database

Triple Multiplication of Sparse Matrices Techniques

IP.com Disclosure Number: IPCOM000077263D
Original Publication Date: 1972-Jul-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 2 page(s) / 42K

Publishing Venue

IBM

Related People

Kugel, LE: AUTHOR

Abstract

This method provides rapid multiplication of 3 matrices A, B, C as AxBxC in which matrix B is a sparse matrix with floating-point entries, and A and C are spare ternary (-1, 0, or +1).

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

Page 1 of 2

Triple Multiplication of Sparse Matrices Techniques

This method provides rapid multiplication of 3 matrices A, B, C as AxBxC in which matrix B is a sparse matrix with floating-point entries, and A and C are spare ternary (-1, 0, or +1).

Ternary matrices A and C are stored rowwise in data vectors, having the nonzero entries stored as the column number of each nonzero entry preceded by the sign of the entry. For example, the data in matrix

(Image Omitted)

Additional pointers are used to denote the beginning and end of data in each row of the matrix.

Sparse matrix B is stored rowwise with the column numbers of each nonzero entry in a data vector and the nonzero entries in another data vector. For example

(Image Omitted)

Additional pointers are used to denote the beginning and end of each row.

The result of this triple multiplication is also a sparse matrix. This description provides a rapid means of updating the nonzero values in D, providing that only the changes that occur are the values of the nonzero entries in B.

Consider the vector of nonzero entries of B, V(B), and the vector of nonzero entries of D, V(D). Every entry in V(D) equals sums and/or differences of entries in V(B). The improvement is as follows:

Construct a ternary matrix T such that V(D) = TxV(B). The ternary matrix T can be constructed from matrix A, matrix C, and the indexing information of matrix B.

1

Page 2 of 2

2

[This page contains 4 pictures or other non-text objects]