Talk:Sparse matrix

Vertex reordering

While the Cuthill-McKee algorithm is a fine algorithm, it was first shown that the Reverse Cuthill-McKee algorithm was often better by A. George in 1971. There have been many arguably better algorithms in the last 30 years.

I added some [incomplete, sketchy] remarks.

-- User:Nahaj 2005-08-28

Cholesky factorization

Cholesky factorization usually only shows up (in my experience) for large sparse matrices in solutions of least squares problems via Normal Equations.

There have been many many alternatives since the 1960's and Householders work. [Lawson and Hanson, 1973] covered several, for example. Reference: Lawson, Charles L. and Hanson, Richard J. 1974, "Solving Least Squares Problems" Prentice-Hall.

The article seems, to me, to have a very old fashioned bias in my opinion. I added some remarks against that bias.

-- User:Nahaj 2005-08-28

My first sentence shows how small an area I play in. In Tim Davis' note below under "too much emphasis on band matrices" he corrects this, and in email has sent me a pointer to his http://www.cise.ufl.edu/research/sparse/matrices which has lots and lots of symmetric positive definite matrices that arise in non least squares contexts and for which Cholesky factorization would be appropriate. Nahaj 14:54, 27 September 2007 (UTC)[reply]

References

A pointer to one guy's implimentation does not make for an reasonable reference list. There are many many good books on the subject.

I added one.

-- User:Nahaj 2005-08-28

Sparse polynomials?

in algebraic geometry sometimes sparse (multivariate) polynomials are mentoined, although I do not know an explicit definition. Assuming somebody here knows a bit about this, it could be a nice topic to add..

guest, 2005-09-14

Well, looking forward to seeing a sparse polynomial article! :) I know nothing of the topic, so I can't help. Oleg Alexandrov 21:10, 14 September 2005 (UTC)[reply]

too much emphasis on band matrices

This article has too much emphasis on band matrices.

"Band" matrices are often thought of as arising from the discretization of a 2D mesh. These are not truly "banded" matrices, however, since the optimal ordering (nested dissection) results in a matrix that is far from banded. Bandwidth reducing orderings are not suitable for a matrix arising from the discretization of a 2D or 3D square mesh (for example).

For example, a n-by-n matrix arising from an s-by-s 2D mesh can be factorized in O(s^3) time, where n = s^2, and with only O (n log n) entries in the factor L, or about O(s^2 log s).

On the other hand, if the "natural" ordering is used (the one that "looks banded"), the time taken is O(n^2), or O(s^4). That's quite a bit higher. The number of entries in the factor is O(n times sqrt(n)), or O(s^3).

Cholesky factorization arises in more problems than the Normal Equations (using Cholesky factorization for the Normal Equations is usually a bad idea; QR factorization is more accurate).

-- Tim Davis, Univ. of Florida

I agree it is a bad idea... but it is still being promoted in current Surveying texts, and still used by the National Geodetic Survey for the national adjustments. So I see it a lot. Nahaj 15:02, 27 September 2007 (UTC)[reply]

Row Bandwidth def'n incorrect

I don't have a reference in front of me, but I think the definition of row bandwidth is wrong. Something like n-m, where m is the minimizer, is within 1 of the lower bandwidth. But it doesn't appear to capture upper bandwidth. Jonas August 16:20, 30 April 2007 (UTC)[reply]

Yes, the definition was rather strange; thanks for bringing that to our attention. I replaced it by another one. Let me know if the new one doesn't make sense to you either. -- Jitse Niesen (talk) 02:00, 1 May 2007 (UTC)[reply]

Banker's algorithm

I removed the link to a "Banker's algorithm" since it points to another algorithm of the same name, not Dr. Snay's algorithm. Nahaj 14:52, 27 September 2007 (UTC)[reply]

Orthogonal List?

As I remember, Orthogonal List (or a similar name) is a common data structure to store a sparse matrix. Is it correct? Btw, I can't even find any info about Orthogonal List in wikipedia. Could anyone more knowledgeable on this issue write some stuff? Took 05:10, 9 November 2007 (UTC)[reply]