home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / pascal / 4544 < prev    next >
Encoding:
Internet Message Format  |  1992-07-24  |  1.7 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!yale.edu!ira.uka.de!chx400!sicsun!elia.epfl.ch
  2. From: guglielmetti@elia.epfl.ch (Philippe Guglielmetti)
  3. Newsgroups: comp.lang.pascal
  4. Subject: Re: Sparse matrices
  5. Message-ID: <3371@sicsun.epfl.ch>
  6. Date: 24 Jul 92 13:41:44 GMT
  7. References: <BrsxF5.DIw@news.cso.uiuc.edu>
  8.      <1992Jul22.234424.3870@usenet.ins.cwru.edu>
  9. Sender: news@sicsun.epfl.ch
  10. Organization: Institut d'Automatique IA-DME-EPFL
  11. Lines: 23
  12. X-UserAgent: Nuntius v1.0
  13.  
  14. Another approach is to use a kind of hash-table. 
  15. each non-zero element is implemented as an index (i*columns+j for
  16. example) and the value itself.All these elements are kept sorted in an
  17. array. When you want to retrieve element (i,j), compute (number of
  18. non-zero elements) *(i*columns+j)/(rows*columns) that's roughly the place
  19. of the element you're looking for in the table. Look if you find it...
  20. it'll be quick and won't use much memory...
  21. I've done something like this using Turbo Vision TCollection object which
  22. allows efficient dynamic size changing and gives lot of useful methods to
  23. implement the hash-table...
  24.  
  25. The proposed hashing  method is efficient for very sparse matrix with
  26. randomly distributed non-zero elements, but you could use a different
  27. hash method if the elements are grouped along the diagonal to reduce the
  28. number of hash-code collisions.
  29.  
  30. Philippe Guglielmetti     |  ***                *
  31. Institut d'Automatique    | *                   *
  32. Ecole Polytechnique       | *  **   ***   *  *  *   *  *
  33. Federale de Lausanne      | *   *  *   *  *  *  *   *  *
  34. 1015 Lausanne             |  ***    ***    ***   *   ***      
  35. SWITZERLAND               |
  36. guglielmetti@elia.epfl.ch | SMILE ! Tomorrow will be worse.
  37.