Sparse matrix: Difference between revisions

Revision as of 03:14, 14 January 2025

Latest revision as of 17:12, 16 July 2025

(6 intermediate revisions by 5 users not shown)

Line 25:

===Banded===

{{main article|Band matrix}}

AnA important[[band matrix]] is a special typeclass of sparse matricesmatrix where the non-zero elements are concentrated near the main diagonal. A band matrix is characterised by its lower and upper bandwidths, which refer to the number of diagonals below and above (respectively) the [[bandmain matrixdiagonal]], definedbetween aswhich followsall of the non-zero entries are contained.

Formally, Thethe [[lower bandwidth of a matrix]] {{math|'''A'''}} is the smallest number {{math|''p''}} such that the entry {{math|''a''_''i'',''j''}} vanishes whenever {{math|''i'' > ''j'' + ''p''}}. Similarly, the [[Band matrix#upper bandwidth|upper bandwidth]] is the smallest number {{math|''p''}} such that {{math|1=''a''_''i'',''j'' = 0}} whenever {{math|''i'' < ''j'' − ''p''}} {{harv|Golub|Van Loan|1996|loc=§1.2.1}}. For example, a [[tridiagonal matrix]] has lower bandwidth {{math|1}} and upper bandwidth {{math|1}}. As another example, the following sparse matrix has lower and upper bandwidth both equal to 3. Notice that zeros are represented with dots for clarity.

<math display="block">\begin{bmatrix}

X & X & X & \cdot & \cdot & \cdot & \cdot & \\

Line 41 ⟶ 43:

====Diagonal====

A verydiagonal efficientmatrix structureis for anthe extreme case of banda matricesbanded matrix, thewith zero upper and lower bandwidth. A ''[[diagonal matrix]]'', iscan be stored efficiently toby storestoring just the entries in the [[main diagonal]] as a [[one-dimensional array]], so a diagonal {{math|''n'' × ''n''}} matrix requires only {{math|''n''}} entries in memory.

===Symmetric===

Line 205 ⟶ 207:

==Further reading==

{{refbegin}}

* {{cite journal | title = A comparison of several bandwidth and profile reduction algorithms | journal = ACM Transactions on Mathematical Software | year = 1976 | volume = 2 | issue = 4 | pages = 322–330 | url = http://portal.acm.org/citation.cfm?id=355707 | doi = 10.1145/355705.355707 | last1 = Gibbs | first1 = Norman E. | last2 = Poole | first2 = William G. | last3 = Stockmeyer | first3 = Paul K. | s2cid = 14494429 | url-access = subscription }}

* {{cite journal | title = Sparse matrices in MATLAB: Design and Implementation | journal = SIAM Journal on Matrix Analysis and Applications | year = 1992 | volume = 13 | issue = 1 | pages = 333–356 | url = http://citeseer.ist.psu.edu/gilbert91sparse.html | doi = 10.1137/0613024 | last1 = Gilbert | first1 = John R. | last2 = Moler | first2 = Cleve | last3 = Schreiber | first3 = Robert | citeseerx = 10.1.1.470.1054 }}

* [http://faculty.cse.tamu.edu/davis/research.html Sparse Matrix Algorithms Research] at the Texas A&M University.