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
===============================================================================
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.
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.