Browse Prior Art Database

EXACT GENERALIZED INVERSION AND OTHER OPERATIONS ON SPARSE MATRICES

IP.com Disclosure Number: IPCOM000128695D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 15 page(s) / 36K

Publishing Venue

Software Patent Institute

Related People

T. Mahadeva Rao: AUTHOR [+4]

Abstract

Single-modulus residue arithmetic is used to compute the Moore-Penrose inverse of a large sparse matrix. Only the non-zero elements of a sparse matrix are stored (in an array called the co-ordinate representation matrix.) Fundamental matrix operations are developed for co-ordinate representation matrices using residue arithmetic.

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

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

EXACT GENERALIZED INVERSION AND OTHER OPERATIONS ON SPARSE MATRICES

. T. Mahadeva Rao R.T. Gregory

CS-78-30 August 78

ABSTRACT

Single-modulus residue arithmetic is used to compute the Moore-Penrose inverse of a large sparse matrix. Only the non-zero elements of a sparse matrix are stored (in an array called the co-ordinate representation matrix.) Fundamental matrix operations are developed for co- ordinate representation matrices using residue arithmetic.

1. Introduction

A matrix is defined to be sparse if it contains mainly zero elements and "only a few" non zero elements. Ther eis no strict definition as to what percentage of the elements of a sparse matrix must be zero, but a generally accepted view is that it should be at least 90%. Sparse matrices arise in a variety of applications such as the application of finite difference methods to the numerical solution of partial differential equations.

In this paper we develop special techniques for the addition and multiplication of sparse matrices which utilize the coordinate representation of the matrix elements. Both the additiona and multiplication subroutines accept the coordinate representation of the matrix elements as input and produce the coordinate representation of the results as output. Three algorithms for matrix multiplication and one algorithm for matrix addition are developed. We also develop algorithms for other matrix operations such as finding the transpose and finding the trace. We use the method of Stallings and Boullion [4] to compute the generalized inverse.

We assume that the matrix elements are integers because a digital computer is capable of storing only rational numbers and, by proper scaling, a matrix whose elements are rational numbers can be converted into a matrix whose elements are integers. With this in mind, we have chosen to do our calculations using residue (or modular) arithmetic in order to avoid rounding errors. An introduction to residue arithmetic is presented in the next section.

2. Residue Arithmetic

We shall consider single modulus residue arithmetic (as opposed to multiple modulus reside arithmetic) in this section. We select our modulus to be any odd integer

(Equation Omitted)

University of Tennessee Page 1 Dec 31, 1978

Page 2 of 15

EXACT GENERALIZED INVERSION AND OTHER OPERATIONS ON SPARSE MATRICES

(usually a prime). Associated with p are the two sets of integers

(Equation Omitted)

and

(Equation Omitted)

The set

(Equation Omitted)

is the set of standard residues modulo p and the set

(Equation Omitted)

is the set of semmetric residues modulo p. The mapping

(Equation Omitted)

maps any integer a onto its standard residue r, that is,

(Equation Omitted)

where

(Equation Omitted)

and

(Equation Omitted)

. The maping

(Equation Omitted)

maps any integer a onto its symmetric residue s, that is,

(Equation Omitted)

where

(Equation Omitted)

and

(Equation Omitted)

It is important to obse...