Mixing
稀疏矩阵
稀疏矩陣的例子 (11220000003344000000556677000000088000000099){displaystyle left({begin{smallmatrix}11&22&0&0&0&0&0\0&33&44&0&0&0&0\0&0&55&66&77&0&0\0&0&0&0&0&88&0\0&0&0&0&0&0&99\end{smallmatrix}}right)}  |
上述稀疏矩陣僅包含9個非零元素，另外包含26個零元素。其稀疏度為74%，密度為26%。 |
A sparse matrix obtained when solving a finite element problem in two dimensions. The non-zero elements are shown in black.
稀疏矩阵（英语：sparse matrix），在数值分析中，是其元素大部分为零的矩阵。反之，如果大部分元素都非零，则这个矩阵是稠密的。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。
在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。
目录
1 定义
2 例子
3 计算方法
4 參考文獻
5 延伸閱讀
定义
给定一个N×M的稀疏矩阵A，其第n行的行带宽定义为：
- bn(A):=min1≤m≤M{m∣an,m≠0}{displaystyle b_{n}(mathbf {A} ):=mathrm {min} _{1leq mleq M}lbrace mmid a_{n,m}neq 0rbrace }
整个矩阵的带宽定义为：
- B(A):=max1≤n≤Nbn(A){displaystyle B(mathbf {A} ):=mathrm {max} _{1leq nleq N}b_{n}(mathbf {A} )}
例子
- 一幅双色图像以位图方式存储，若其中一种颜色的像素远远多于另一种颜色的像素（比如手写签名的扫描图像），就可以将其按稀疏矩阵编码：仅保存其少数像素的行列信息。
数值法求解偏微分方程（比如差分法和有限元法）时通常会出现稀疏矩阵。比如最简单的差分法的五点模板（5-point-stencil）求解泊松方程或薛定谔方程会出现稀疏矩阵。
计算方法
稀疏矩阵的「注入元」是指执行算法是从初始的零值变为非零值的那些元素。为减少内存要求和算术操作的次数，我们经常通过交换某些行或某些列来尽量减少注入元。符号柯列斯基分解可以用来在做实际的柯列斯基分解之前计算最坏情况下注入元的数目。与此类似，我们可以用符号QR分解在做实际的QR分解之前计算最坏情况下注入元的数目。
消去树（elimination tree）法是一种用于高斯消元法或LU分解中的系统处理如何减少注入元的方法。与此相关的一种称为巢狀解剖的方法，可以看成是它的一个特例。
參考文獻
.mw-parser-output .refbegin{font-size:90%;margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{list-style-type:none;margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li,.mw-parser-output .refbegin-hanging-indents>dl>dd{margin-left:0;padding-left:3.2em;text-indent:-3.2em;list-style:none}.mw-parser-output .refbegin-100{font-size:100%}
Golub, Gene H.; Van Loan, Charles F. Matrix Computations 3rd. Baltimore: Johns Hopkins. 1996. ISBN 978-0-8018-5414-9.
Stoer, Josef; Bulirsch, Roland. Introduction to Numerical Analysis 3rd. Berlin, New York: Springer-Verlag. 2002. ISBN 978-0-387-95452-3.
Tewarson, Reginald P. Sparse Matrices (Part of the Mathematics in Science & Engineering series). Academic Press Inc. May 1973. (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).
Bank, Randolph E.; Douglas, Craig C. Sparse Matrix Multiplication Package (PDF).
Pissanetzky, Sergio. Sparse Matrix Technology. Academic Press. 1984.
Snay, Richard A. Reducing the profile of sparse symmetric matrices. Bulletin Géodésique. 1976, 50 (4): 341. doi:10.1007/BF02521587. Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.
延伸閱讀
Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. A comparison of several bandwidth and profile reduction algorithms. ACM Transactions on Mathematical Software. 1976, 2 (4): 322–330. doi:10.1145/355705.355707.
Gilbert, John R.; Moler, Cleve; Schreiber, Robert. Sparse matrices in MATLAB: Design and Implementation. SIAM Journal on Matrix Analysis and Applications. 1992, 13 (1): 333–356. doi:10.1137/0613024. 已忽略未知参数|citeseerx=(帮助)
Sparse Matrix Algorithms Research at the University of Florida, containing the UF sparse matrix collection.
SMALL project A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.
| |||||||||||||||||||||||||||||||||||||
Comments
Post a Comment