From: Marco Antoniotti Subject: Sparse Matrices Summary Date: Message-ID: <s08ybc1htdh.fsf@crawdad.ICSI.Berkeley.EDU>

Hello I collected the following messages about data structures for sparse matrices. It looks like that a Common Lisp implementation might be easier than it looks. From ···@epic.com Mon Mar 3 10:16:38 1997 Delivery-Date: Mon, 03 Mar 1997 10:16:39 PST Return-Path: ···@epic.com X-organization: EPIC Design Technology, Inc. To: ·······@porsche.PATH.Berkeley.EDU Subject: Re: How to represent a LARGE sparse matrix?? From: Charlie Xiaoli Huang <···@epic.com> Date: 03 Mar 1997 10:15:45 -0800 In-Reply-To: Marco Antoniotti's message of 03 Mar 1997 09:05:32 -0800 Lines: 32 X-Mailer: Gnus v5.3/Emacs 19.33 these may be a bit dated: ==== I. S. Duff, A. M. Erisman, J. K. Reid. IDirect Methods for Sparse Matrices. Oxford University Press, 1986. G. H. Golub, C. F. V. Van Loan. IMatrix Computations. The Johns Hopkins University Press, 1983. === hxl Marco Antoniotti <·······@crawdad.icsi.berkeley.edu> writes: > > > I have been following this thread and I still have the follwing > question? > > How do you code a sparse matrix in FORTRAN, or C, or COBOL, or Java? > It seemes to me that there should be *a lot* of literature by various > numerical analysts on the subject. > > If anybody has pointers to such literature, please send me a message > and I will post a summary. > > Thanks > > -- > Marco Antoniotti - Resistente Umano > =============================================================================== From ···@epic.com Mon Mar 3 10:52:06 1997 Delivery-Date: Mon, 03 Mar 1997 10:52:08 PST Return-Path: ···@epic.com X-organization: EPIC Design Technology, Inc. Date: Mon, 3 Mar 1997 10:51:28 -0800 From: Charlie Xiaoli Huang <···@epic.com> To: Marco Antoniotti <·······@ICSI.Berkeley.EDU> Subject: Re: How to represent a LARGE sparse matrix?? In-Reply-To: <·····················@crawdad.Berkeley.EDU> References: <··············@weber.i-have-a-misconfigured-system-so-shoot-me> <·····················@crawdad.Berkeley.EDU> Reply-To: ···@epic.com Duff's book has a chapert (chapter 2) that covers storage and representation of sparce matrices. Most of the books, this one included, follow a FORTRAN style, which is unnecessarily complicated since they use index arrays to simulate linked lists. Most of the representations are, however, quite similar. They are basically linked lists (row, column, or row/column; single, double, or circular.) Some cache pointers to the diagonal as well, since diagonal access is more frequent than others. Special matrices, such as blocked, banded, etc, may have special structures as well. In my work, I deal with large (> million x million) sparse (>99% empty) matrices and the most time consuming job is LU factorization or QR factorization. So anything short of a representation in which rows and columns both allow insertion/deletion (i.e. linked list) won't work for these purposes, I have not spent much time looking into other schemes. Hope this helps. hxl BTW: there's another book called Sparse Matrix Technology from 1984 that also may be useful. I can't recall more specifics, though. >>>>> "Marco" == Marco Antoniotti <·······@ICSI.Berkeley.EDU> writes: > Thanks. > However, I have noticed that a lot of times these numerical analysis > books do not care too much about data structures. Could you briefly > comment on them? > Cheers > Marco From ·······@math.okstate.edu Thu Mar 6 08:28:25 1997 Path: agate!newsxfer3.itd.umich.edu!howland.erols.net!feed1.news.erols.com!news.ecn.uoknor.edu!news.cis.okstate.edu!usenet From: Mark McConnell <·······@math.okstate.edu> Newsgroups: comp.lang.lisp Subject: Re: How to represent a LARGE sparse matrix?? Date: Mon, 03 Mar 1997 15:48:35 -0600 Organization: Math Dept., Oklahoma State University Lines: 31 References: <·························@207.70.66.82> <···········@news.nero.net> <··········@panix.com> <···············@crawdad.ICSI.Berkeley.EDU> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0 (X11; I; SunOS 5.5 sun4d) Marco Antoniotti wrote: > > How do you code a sparse matrix in FORTRAN, or C, or COBOL, or Java? > It seemes to me that there should be *a lot* of literature by various > numerical analysts on the subject. > > If anybody has pointers to such literature, please send me a message > and I will post a summary. One source is _Direct Methods for Sparse Matrices_, by I. S. Duff, A. M. Erisman, and J. K. Reid, in "Monographs on Numerical Analysis", Clarendon Press, Oxford, 1986 [corrected 1989]. Or: "Data Structures, Algorithms, and Software for Sparse Matrices," Iain S. Duff, in _Sparsity and its Appl'ns_, ed. David J. Evans, Camb. U. Press, 1985, pp. 13-15. Duff and Reid have been big names in this field for several decades. [Apologies to other big names I'm not naming--I don't know this field]. I have missed any parts of this thread that dealt with the Lisp aspects. Since 1987 I personally have used a certain kind of sparse matrix data structure adapted to Lisp. I use only *integer* matrices, which means I can't use much of what's in the numerical analysis literature. I need fast access to both row and column operations, and have tried to write a sparse data structure that provides it, with partial success. You can look at my Lisp code in http://www.math.okstate.edu/~mmcconn/shh0297/sparsezmat.lisp -- Marco Antoniotti - Resistente Umano ===============================================================================

- Re: Sparse Matrices Summary
**John Watton** - Re: Sparse Matrices Summary
**Gareth McCaughan**

From: John Watton Subject: Re: Sparse Matrices Summary Date: Message-ID: <uwwrkk25t.fsf@atc.alcoa.com>

Just another 2 cents on this topic. A book which may be more accessable is "C: The Complete Reference", 2nd edition by Herbert Schildt. He has a a chapter 21 titled "Sparse Arrays". It has the following sections: The linked-list sparse array The binary-tree approach to sparse arrays The pointer-array approach to sparse arrays Hashing Choosing an approach He uses a spreadsheet application as an example.

From: Gareth McCaughan Subject: Re: Sparse Matrices Summary Date: Message-ID: <86913xq1k4.fsf@g.pet.cam.ac.uk>

John Watton wrote: > Just another 2 cents on this topic. A book which may be more accessable > is "C: The Complete Reference", 2nd edition by Herbert Schildt. He has a > a chapter 21 titled "Sparse Arrays". It has the following sections: > > The linked-list sparse array > The binary-tree approach to sparse arrays > The pointer-array approach to sparse arrays > Hashing > Choosing an approach > > He uses a spreadsheet application as an example. Um. Herbert Schildt is infamous for writing books about C that purport to be "complete" but that actually expose his remarkable ignorance of the language. (See e.g. http://solutions.solon.com/~seebs/faqs/c/c_tcr.html for some comments on "C: The Complete Reference". This may not say anything about his competence with data structures, which is really what this is all about. But, on the basis of what I've read about Schildt's C books, I would not be inclined to trust him on any technical matter at all. -- Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics, ·····@dpmms.cam.ac.uk Cambridge University, England.