 Sparse MatricesRichard L. Branham
Chapter Chapter 3 in Scientific Data Analysis, 1990, pp 34-66 from Springer Abstract: Abstract A matrix is sparse if a high percentage of its elements are zero. “High”, of course, is a relative term, but if about 50% or more of the elements are zero the matrix may be considered sparse. With this percentage of null elements, use of data structures other than the standard two-dimensional array may result in a substantial saving of space or execution time, space because the storage of the zero elements is suppressed and time because we do no operations with them. Consider scahng the columns of an n x n matrix A. Mathematically, we do this by postmultiplying A by a diagonal matrix S of scale factors, 3.1 $$A' = A \cdot S \cdot$$ But no sane programmer would store S as an n x n matrix. He would store it as a vector, thus using only n memory locations. Likewise, he would not use a matrix multiplication routine for the product A· S. He would multiply all of the elements in the first column of A by the first scale factor, the second column by the second scale factor, and so forth. In this way only n2 arithmetic operations, rather than n3 as with matrix multiphcation, would be needed. Keywords: Hash Table; Triangular Matrix; Sparse Matrix; Sparse Matrice; Linear Search (search for similar items in EconPapers) There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3362-6_3 Ordering information: This item can be ordered from DOI: 10.1007/978-1-4612-3362-6_3 Access Statistics for this chapter More chapters in Springer Books from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.