home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17440 < prev    next >
Encoding:
Internet Message Format  |  1992-12-27  |  1.9 KB
  1. Xref: sparky sci.math:17440 sci.engr:2421
  2. Path: sparky!uunet!spool.mu.edu!umn.edu!gaia.ucs.orst.edu!news.cs.indiana.edu!nstn.ns.ca!psinntp!psinntp!kepler1!andrew
  3. From: andrew@rentec.com (Andrew Mullhaupt)
  4. Newsgroups: sci.math,sci.engr
  5. Subject: Re: Question about "sparsity" of matrices
  6. Message-ID: <1434@kepler1.rentec.com>
  7. Date: 27 Dec 92 16:19:43 GMT
  8. References: <24DEC199211261595@ariel.lerc.nasa.gov>
  9. Followup-To: sci.math
  10. Organization: Renaissance Technologies Corp., Setauket, NY.
  11. Lines: 27
  12.  
  13. In article <24DEC199211261595@ariel.lerc.nasa.gov> ecaxron@ariel.lerc.nasa.gov (Ron Graham) writes:
  14. >I ask your pardon if this question is too simple, or if the subject has
  15. >been discussed already.  I am posting this question to two newsgroups,
  16. >one of which I do not currently subscribe to.
  17. >
  18. >Is there a measure for the "sparsity" (or maybe I should say "sparseness"?)
  19. >of a matrix?  We know that a sparse matrix has a lot of zeroes in it.  But
  20. >who decides when the matrix is sparse?  Are there degrees of sparseness?
  21.  
  22. A matrix may be usefully considered sparse if so many of it's elements
  23. are zero that it pays to keep track of the nonzero elements only, and this
  24. obviously depends on what kind of operations you are doing. A simple measure
  25. closely related to this is the fraction of nonzero elements, and another
  26. similarly notion of sparsity is for families of matrices, i.e. some people
  27. consider a family of matrices to be sparse when the fraction of nonzero
  28. elements tends to zero as the size of the matrix tends to infinity.
  29.  
  30. There are other important exploitable structures for matrices, which can
  31. be observed in sparse matrices. Most important are polydiagonal and band
  32. matrices, and then block polydiagonal matrices. Special algorithms and
  33. data structures are used to exploit sparseness in each case.
  34.  
  35. So the bottom line is that _you_ get to decide what sparseness is by
  36. showing how to exploit it. 
  37.  
  38. Later,
  39. Andrew Mullhaupt
  40.