NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/sci/engr/2442

Internet Message Format | 1993-01-04 | 5.8 KB

Xref: sparky sci.engr:2442 sci.math:17639
Newsgroups: sci.engr,sci.math
Path: sparky!uunet!usc!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!spool.mu.edu!agate!usenet.ins.cwru.edu!eagle!ariel.lerc.nasa.gov!ecaxron
From: [e-mail] (Ron Graham)
Subject: Matrix sparsity question - the summary!
Message-ID: <[e-mail]>
News-Software: VAX/VMS VNEWS 1.41
Sender: [e-mail]
Nntp-Posting-Host: ariel.lerc.nasa.gov
Organization: NASA Lewis Research Center
Date:  4 Jan 1993 10:12 EST
Lines: 122

Here is the original question:

**********************************************************************

Is there a measure for the "sparsity" (or maybe I should say "sparseness"?)
of a matrix?  We know that a sparse matrix has a lot of zeroes in it.  But
who decides when the matrix is sparse?  Are there degrees of sparseness?

The answer to this question will help us determine a test plan for a
matrix inversion algorithm we are currently testing in an engineering
application.

**********************************************************************

The following are the responses, condensed.  Thanks to all for the help.

RG

From: [e-mail] (M. J. Saltzman)
Subject: Re: Question about "sparsity" of matrices

The measure is just nz/n^2 (and the common term is "sparsity").  What
the cutoff is between a sparse matrix and a dense matrix is depends
heavily on the application and the machine.  It's either the point at
which a sparse storage format takes less space than a dense format, or
(more to the point) the point below which your code runs faster for
the sparse storage format than for the dense storage format
(considering the overhead necessary to take advantage of sparsity).
There's no universal number that people agree on as a cutoff (I know a
sparse matrix when I see one!).  If you're factoring, I'd guess that
between 10% and 20% is getting dense, but it varies a lot depending on
other aspects of the matrix structure (where the nonzeros are is as
important as how many--the factor can be much denser than the original
matrix).

There's lots and lots of literature--high-performance sparse matrix
methods are one of the hottest topics in computational linear algebra
(as you might guess).  See George and Liu's 1981 book, or Duff,
Erisman and Reid's book (1984?) for starters.

Then there's the whole area of iterative methods for sparse problems
(mostly preconditioned conjugate gradient methods).

From: "V. Phaniraj" <[e-mail]>
Subject: Re: Question about "sparsity" of matrices

One common measure of "sparsity" used in my area (electric power systems)
is the "fill-in", the number of non-zero non-diagonal entries, as a
percentage of the total size of the array.

A lot of work has been done in re-odering the matrix rows and columns
to preserve sparsity after a matrix inversion, and for handling
perturbations in the original element values.

references

tinney and walker, proc IEEE, nov 1967, pp 1801-1809, "direct
solution of sparse network equations by optimally ordered triangular
factorization" ( this is a classic in my area)

stott & hobson, proc IEEE, jan 1971, "solution of large
networks by ordered elimination- comparison of ordering schemes"

newer work that may be of interest

chan and brandwajn, "partial matrix refactorization", IEEE
transactions on power systems, feb 1986, pp 193-200.

tinney, chan and brandwajn, "sparse vector methods", IEEE transactions
on power apparatus and systems, Feb 1985, pp 295-301.

From: [e-mail]
Subject: Re: Question about "sparsity" of matrices

A closely related idea is the "block" dimension,  log(N)/log(n), where
N is the number of non-zero elements in the nXn matrix.  Note that for
the identity matrix, the dimension is 1, and for a matrix with no zero
elements the dimension is 2.

This idea comes up in the study of fractals.  The book by Falconer might
be a good place to look.

From: [e-mail] (Navid Haddadi)
Subject: Re: Question about "sparsity" of matrices

I have never seen a definition. But every sparse matrix that I have seen
has the property that it has O(N) non-zero elements and O(N^2) zeros.
For example, a tridiagonal matrix is sparse (or a block tridiag). But
a circular or Toeplitz is not sparse despite the fact that multiplications
and inverses can be computed in O(nlogn) and O(n^2), resp.

From: [e-mail]
Subject: Re: Question about "sparsity" of matrices

I do not think that there exists an official definition of spasity.
A rule of the thumb could be <= 10 % nonzero elts. or so.

Sparse matrices used to be a hot topic in power systems and in
other network-flow problems. I think there is a book by Brameller
in a power system contex.

Ask numerical analysts before you code - many things exist already,
there is a Yale package for sparse matrices.

From: [e-mail] (Andrew Mullhaupt)
Subject: Re: Question about "sparsity" of matrices

A matrix may be usefully considered sparse if so many of its elements
are zero that it pays to keep track of the nonzero elements only, and this
obviously depends on what kind of operations you are doing. A simple measure
closely related to this is the fraction of nonzero elements, and another
similarly notion of sparsity is for families of matrices, i.e. some people
consider a family of matrices to be sparse when the fraction of nonzero
elements tends to zero as the size of the matrix tends to infinity.

There are other important exploitable structures for matrices, which can
be observed in sparse matrices. Most important are polydiagonal and band
matrices, and then block polydiagonal matrices. Special algorithms and
data structures are used to exploit sparseness in each case.

So the bottom line is that _you_ get to decide what sparseness is by
showing how to exploit it.