Talk:Sparse matrix
From Wikipedia, the free encyclopedia
Contents |
[edit] 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
[edit] 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
[edit] 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
[edit] 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)
[edit] 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
