Browse Prior Art Database

Making Matrices Sparsest

IP.com Disclosure Number: IPCOM000047137D
Original Publication Date: 1983-Sep-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Hoffman, AJ: AUTHOR [+2]

Abstract

Given a mxn matrix A1, of rank m, this article describes an algorithm for finding a nonsingular mxm matrix T such that TA is as sparse as possible (i.e., has as many zeroes as possible). The algorithm is optimum if A has the property that (*) for every submatrix B of A, rank B is the largest number of nonzeroes in B no two of which have the same row or column. When (*) is not satisfied, the algorithm should be interpreted as a heuristic. The algorithm is: For each i = 1,...,m. Step i: Let B be the submatrix of A formed by these columns where row i is 0. Find the smallest number of rows and columns of B which together contain all nonzeroes of B; of all such, find the maximal (its unique) set of rows in such a collection of rows and columns; let U be the complementary (except for row i) set of rows.

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

Page 1 of 1

Making Matrices Sparsest

Given a mxn matrix A1, of rank m, this article describes an algorithm for finding a nonsingular mxm matrix T such that TA is as sparse as possible (i.e., has as many zeroes as possible). The algorithm is optimum if A has the property that (*) for every submatrix B of A, rank B is the largest number of nonzeroes in B no two of which have the same row or column. When (*) is not satisfied, the algorithm should be interpreted as a heuristic. The algorithm is: For each i = 1,...,m. Step i: Let B be the submatrix of A formed by these columns where row i is 0. Find the smallest number of rows and columns of B which together contain all nonzeroes of B; of all such, find the maximal (its unique) set of rows in such a collection of rows and columns; let U be the complementary (except for row i) set of rows. Standard network flow algorithms, in fact, furnish U. Step i': If U is not empty, choose a nonsingular ¯U¯x¯U submatrix M from the rows U of A, and choose multiplier gu so that row i of A g' M is O in the positions corresponding to the columns of M. Replace row i of A by itself + g' where N is the submatrix of A corresponding to rows of U.

1