[稀疏矩阵]——稀疏矩阵转置

[稀疏矩阵]——稀疏矩阵转置 [稀疏矩阵]——稀疏矩阵转置 篇一 : ——稀疏矩阵转置 矩阵是线性代数中的一个知识，刚开始学习的时候可能感觉不到它有什么用处，最初的感觉就是对二维数据的操作。,)其实现实生活中矩阵的用处太大了，领域相当的广泛。在此只讨论稀疏矩阵的转置问题; 可能看到矩阵就会想到二维数组，比如这样一个矩阵: 你可能会想到用二维数组来存放此矩阵中的元素，就像这样:int text[][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}}; 这样好像也没有什么不好。我们再来看看这个矩阵，五行五列，可以包含二十五个元素，但是此矩阵只有七个元素。但是我们在存放数据的时候分配了二十五块int单元。这样是不是有点太浪费了。如果我们只存储这七个元素我想会节省一部分内存空间。但是如果我们只存储矩阵中的元素还是不行的，因为只有元素我们就无法还原矩阵，我们还需要此元素的行列值。这样就好办了。我们声明一个结构体来表示一个元素。就像这样: 1 typedef struct juzhen2 {3 int row; //行4 int col; //列5 int value; //元素值6 }; 这样存储一个元素就会用到三个存储单元，七个就是二十一个 存储单元，可能与二十五个没多大差别，但是如果矩阵的行列是一个 很大的值，而且又是稀疏矩阵，这样做就可以节省很大的空间。这种 存储结构只限于稀疏矩阵。 解决了存储结构，就开始矩阵的转置吧～～～ 首先我们需要一个矩阵，就按照上图给的矩阵好了，按照此矩 阵做一个二维数组: 1 int text[][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}}; 就像这样;我们需要定义一个数组来表示稀疏矩阵，并赋值; 1 #define MAX_TERM 15 2 3 struct juzhen a[MAX_TERM]; //存放矩阵中元素数值不为零的元素 4 5 int chushi //初 始化稀疏矩阵 6 { 7 int count_value = 0; //统计矩阵中元素数 值不为零的元素的总和 8 int i,j; 9 int count_a = 1;10 for11 {12 for13 {14 if15 {16 a[count_a].row = i;17 a[count_a].col = j;18 a[count_a].value = text[i][j];19 count_a++;20 }21 }22 }23 a[0].col = 5; //矩阵的总列数24 a[0].row = 5; //矩阵的总行数25 a[0].value = --count_a; //矩阵中的元素个数26 27 return count_a;28 } 在初始化矩阵数组的时候为了方便转置矩阵时的操作，我们把 数组的第一个元素设置为矩阵的列数，行数和元素总数; 矩阵有了，存放矩阵元素的数组也有了。接下来就是转置矩阵 的函数了。 我们在转置矩阵的时候会需要一个数组来保存转置后的矩阵， 定义为: struct juzhen b[MAX_TERM];//转置后的矩阵 主要思想，两层循环，第一层循环控制矩阵的行，第二层循环 控制数组a的行。由于转置矩阵即把矩阵中元素的列行对换一下，并 且按照行排序;所以我们在第二层循环中做一个判断，if 如果为真 值则执行: b[count_b].row = a[j].col; b[count_b].col = a[j].row; b[count_b].value = a[j].value; 整个函数如下: void zhuanzhi_1 //转置矩阵方法一{ int i,j; int count_b = 1; //b的当前元素下标 b[0].row = a[0].col; b[0].col = a[0].row; b[0].value = a[0].value; for { for { if //有种排序效果 { b[count_b].row = a[j].col; b[count_b].col = a[j].row; b[count_b].value = a[j].value; count_b++; } } }} 用此方法可以有效的转置矩阵，我们来看一下此函数的时间复 杂度:O——矩阵的列*矩阵的元素总和; 如果元素很多就会浪费很多的时间。有没有办法让两层循环变 成一层循环呢,付出空间上的代价，换取时间效率; 我们只用一层循环来遍历数组a中所有元素，并把该元素放到 指定的位置。这样我们就需要一个数组star来存放第i个元素所在位 置。在定义这个数组之前，我们还需要一个数组term来实现统计矩 阵第i行元素的数量。这样我们才能更方便的知道第i个元素应该存 放的位置。 int term[N],star[N]; //保存转置矩阵第i行元素的数量 保存第i行开始位置 int n = a[0].value; int i,j,k; int b_star; for term[i] = 0; for term[a[j].col]++; star[0] = 1; for star[k] = star[k - 1] + term[k - 1]; 第一个循环初始化term，每个元素都为零。第二个循环是为了 统计第i行元素的数量。第三个循环是设置第i个元素所在的位置。 因为数组a的第一个元素是存放行列和元素的总数，因此第三个循环 要从k = 1开始。此时两个数组的元素为: 下一步就是遍历a中的所有元素，然后根据a[i].col的值来把 a[i].value放到指定的位置。 b[0].col = a[0].col; b[0].row = a[0].row; b[0].value = a[0].value; for { b_star = star[a[i].col]++; b[b_star].col = a[i].row; b[b_star].row = a[i].col; b[b_star].value = a[i].value; } 扩展:数据结构稀疏矩阵转置 / 数据结构稀疏矩阵 / 数据结构矩阵转置 需要注意的是b的第一个元素与a中的第一个元素是同样的。 b_star = star[a[i].col]++;因为当term[1] = 2;而star[1] = 3;就是a[i].col = 1时有两个元素，第一个元素的位置是star[a[i].col];而第二个元素的 位置就是star[a[i].col] + 1所以在此用star[a[i].col]++。为下一个元素 设置相应的位置; 完整函数: void zhuanhuan_2{ int term[N],star[N]; //保存转置矩 阵第i行元素的数量 保存第i行开始位置 int n = a[0].value; int i,j,k; int b_star; for term[i] = 0; for term[a[j].col]++; star[0] = 1; for star[k] = star[k - 1] + term[k - 1]; b[0].col = a[0].col; b[0].row = a[0].row; b[0].value = a[0].value; for { b_star = star[a[i].col]++; b[b_star].col = a[i].row; b[b_star].row = a[i].col; b[b_star].value = a[i].value; }} 此函数每个循环体的执行次数分别为cols cols elements elements 时间复杂度为O和O相差好多，尤其是clos 和 elements 很大的时候; 完整的测试程序: 完整代码 1 #include 2 #define N 5 3 #define MAX_TERM 15 4 5 typedef struct juzhen 6 { 7 int row; //行 8 int col; //列 9 int value; //元素值 10 }; 11 12 int text[][5] = {{0,5,6,0,4},{0,0,0,0,0},{1,0,0,0,0},{1,0,0,0,0},{0,2,0,0,1}}; 13 struct juzhen a[MAX_TERM]; //存放矩阵中元素数值不为零的元素 14 struct juzhen b[MAX_TERM]; //转置后的矩阵 15 16 int chushi //初始化稀疏矩阵 17 { 18 int count_value = 0; //统计矩阵中元素数值不为零的元素的总和 19 int i,j; 20 int count_a = 1; 21 for 22 { 23 for 24 { 25 if 26 { 27 a[count_a].row = i; 28 a[count_a].col = j; 29 a[count_a].value = text[i][j]; 30 count_a++; 31 } 32 } 33 } 34 a[0].col = 5; //矩阵的总列数 35 a[0].row = 5; //矩阵的总行数 36 a[0].value = --count_a; //矩阵中的元素个数 37 38 return count_a; 39 } 40 41 void showjuzhen //显示稀疏矩阵 42 { 43 int i,j; 44 int text = 1; 45 for 46 { 47 for 48 { 49 if 50 { 51 printf; 52 text++; 53 } 54 else 55 printf; 56 } 57 printf; 58 } 59 60 } 61 62 void showjuzhen_2 //显示稀疏矩阵方法二 63 { 64 int i; 65 printf; 66 for 67 { 68 printf; 69 } 70 } 71 72 73 void zhuanzhi_1 //转置矩阵方法一 74 { 75 int i,j; 76 int count_b = 1; //b的当前元素下标 77 b[0].row = a[0].col; 78 b[0].col = a[0].row; 79 b[0].value = a[0].value; 80 for 81 { 82 for 83 { 84 if 85 { 86 b[count_b].row = a[j].col; 87 b[count_b].col = a[j].row; 88 b[count_b].value = a[j].value; 89 count_b++; 90 } 91 } 92 } 93 } 94 95 96 void zhuanhuan_2 97 { 98 int term[N],star[N]; 99 int n = a[0].value;100 int i,j,k;101 int b_star;102 103 for 104 term[i] = 0;105 106 for107 term[a[j].col]++;108 109 star[0] = 1;110 for111 star[k] = star[k - 1] + term[k - 1];112 113 b[0].col = a[0].col;114 b[0].row = a[0].row;115 b[0].value = a[0].value;116 for117 {118 b_star = star[a[i].col]++;119 b[b_star].col = a[i].row;120 b[b_star].row = a[i].col;121 b[b_star].value = a[i].value;122 }123 124 125 for126 printf;127 128 }129 130 int main131 {132 int count_a;133 count_a = chushi;134 showjuzhen;135 showjuzhen_2;136 printf;137 zhuanhuan_2;138 //zhuanzhi_1;139 //showjuzhen;140 //showjuzhen_2;141 //return 0;142 } 扩展:数据结构稀疏矩阵 转置 / 数据结构稀疏矩阵 / 数据结构矩阵转置 扩展:数据结构稀疏矩阵转置 / 数据结构稀疏矩阵 / 数据结 构矩阵转置 篇二 : R_构造稀疏矩阵 sparseMatrix1、首先来看一下问题的起源: 我有的数据是: a ## a b## 1 1 3##,, 2 1 3## 3 1 3## 4 1 2## 5 1 3## 6 1 3 我 希望对分组变量统计，组内取值的频率。 我使用了tapply函数: c ## $`1`## ## 1 2 3 4 ## 25 15 31 29 ## ## $`2`## ## 1 2 3 4 ## 13 36 28 23 ## ## $`3`## ## 1 2 3 4 ## 20 27 28 25 ## ## $`4`## ## 1 2 3 4 ## 29 32 21 18 ## ## $`5`## ## 1 2 3 4 ## 22 31 17 30 ## ## $`6`## ## 1 2 3 4 ## 18 29 23 30 可 以看出得到了，我想要的数据。但是tapply的输出是列表，我不太会 将其转化为 data.frame 接下来使用Matrix包中的sparseMatrix得到了我想要的结果 library## Warning: package „Matrix? was built under R version 3.0.3id ## id X1 X2 X3 X4## 1 1 25 15 31 29## 2 2 13 36 28 23## 3 3 20 27 28 25## 4 4 29 32 21 18## 5 5 22 31 17 30## 6 6 18 29 23 30 由此产生了我需要的数据格式。 2、sparseMatrix函数的学习i ## 8 x 10 sparse Matrix of class “dgCMatrix”## ## [1,] . 7 . . . . . . . .## [2,] . . . . . . . . . .## [3,] . . . . . . . . 14 .## [4,] . . . . . 21 . . . .## [5,] . . . . . . 28 . . .## [6,] . . . . . . . 35 . .## [7,] . . . . . . . . 42 .## [8,] . . . . . . . . . 49summary## 8 x 10 sparse Matrix of class “dgCMatrix”, with 7 entries ## i j x## 1 1 2 7## 2 4 6 21## 3 5 7 28## 4 6 8 35## 5 3 9 14## 6 7 9 42## 7 8 10 49str## Formal class „dgCMatrix? [package “Matrix”] with 6 slots## ..@ i : int [1:7] 0 3 4 5 2 6 7## ..@ p : int [1:11] 0 0 1 1 1 1 2 3 4 6 ...## ..@ Dim : int [1:2] 8 10## ..@ Dimnames:List of 2## .. ..$ : NULL## .. ..$ : NULL## ..@ x : num [1:7] 7 21 28 35 14 42 49## ..@ factors : list, c, x = 7 * , dims = c))## 10 x 20 sparse Matrix of class “dgCMatrix”## ## [1,] . 7 . . . . . . . . . . . . . . . . . .## [2,] . . . . . . . . . . . . . . . . . . . .## [3,] . . . . . . . . 14 . . . . . . . . . . .## [4,] . . . . . 21 . . . . . . . . . . . . . .## [5,] . . . . . . 28 . . . . . . . . . . . . .## [6,] . . . . . . . 35 . . . . . . . . . . . .## [7,] . . . . . . . . 42 . . . . . . . . . . .## [8,] . . . . . . . . . 49 . . . . . . . . . .## [9,] . . . . . . . . . . . . . . . . . . . .## [10,] . . . . . . . . . . . . . . . . . . . .summary #dims可以比最大的 行或列指标大## 10 x 20 sparse Matrix of class “dgCMatrix”, with 7 entries ## i j x## 1 1 2 7## 2 4 6 21## 3 5 7 28## 4 6 8 35## 5 3 9 14## 6 7 9 42## 7 8 10 49set.seed)## [1] 2 3 6 4 1 7 5) #i,j,x可以在任意位置## 8 x 10 sparse Matrix of class “dgCMatrix”## ## [1,] . 7 . . . . . . . .## [2,] . . . . . . . . . .## [3,] . . . . . . . . 14 .## [4,] . . . . . 21 . . . .## [5,] . . . . . . 28 . . .## [6,] . . . . . . . 35 . .## [7,] . . . . . . . . 42 .## [8,] . . . . . . . . . 49stopifnot), j = c, x = c))## i j x## 1 1 2 7## 2 3 9 14## 3 4 6 21## 4 5 7 28## 5 6 8 35## 6 7 9 42## 7 8 10 49## 8 1 2 2) #行列索引有重复位置的时候，相加## 8 x 10 sparse Matrix of class “dgCMatrix”## ## [1,] . 9 . . . . . . . .## [2,] . . . . . . . . . .## [3,] . . . . . . . . 14 .## [4,] . . . . . 21 . . . .## [5,] . . . . . . 28 . . .## [6,] . . . . . . . 35 . .## [7,] . . . . . . . . 42 .## [8,] . . . . . . . . . 49))) #最后一个## 8 x 10 sparse Matrix of class “dgCMatrix”## ## [1,] . 2 . . . . . . . .## [2,] . . . . . . . . . .## [3,] . . . . . . . . 14 .## [4,] . . . . . 21 . . . .## [5,] . . . . . . 28 . . .## [6,] . . . . . . . 35 . .## [7,] . . . . . . . . 42 .## [8,] . . . . . . . . . 49dn ## 3 x 5 sparse Matrix of class “dgCMatrix”## a b c d e## A . 2 . . 6## B . . 4 . 5## C 1 . 3 . .str## Formal class „dgCMatrix? [package “Matrix”] with 6 slots## ..@ i : int [1:6] 2 0 1 2 0 1## ..@ p : int [1:6] 0 1 2 4 4 6## ..@ Dim : int [1:2] 3 5## ..@ Dimnames:List of 2## .. ..$ : chr [1:3] “A” “B” “C”## .. ..$ : chr [1:5] “a” “b” “c” “d” ...## ..@ x : num [1:6] 1 2 4 3 6 5## ..@ factors : list篇 三 : 稀疏矩阵 稀疏矩阵 如果在矩阵中，多数的元素为0，称此矩阵为稀疏矩 阵。 定义 矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，则称该矩阵为稀疏矩阵;与之相区别的是，如果非零元素的分布存在规律，则称该矩阵为特殊矩阵。 优点 稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的一个突出的优点. 假设矩阵A,B中的矩阵一样.计算2*A需要一百万次的浮点运算,而计算2*B只需要2 0 0 0次浮点运算. 因为M AT L A B不能自动创建稀疏矩阵,所以要用特殊的命令来得到稀疏矩阵. 前面章节中的算术和逻辑运算都适用于稀疏矩阵. 对于一个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节.但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间，可以只存储其中的非0元素. 对于矩阵Amn的每个元素aij,知道其行号i和列号j就可以确定其位置.因此对于稀疏矩阵可以用一个结点来存储一个非0元素.该结点可以定义如下: [i,j,aij] 该结点由3个域组成,i:行号,j:列号;aij元素值.这样的结点被称为三元组结点.矩阵的每一个元素Qij,由一个三元组结点唯一确定. 例如稀疏矩阵A: 50 0 0 0 10 0 20 0 0 0 0 0 -30 0 -60 5 其对应的三元组表为: 1 1 50 2 1 10 2 3 20 4 1 -30 4 3 -60 4 4 5 存储空间 高斯一个稀疏矩阵中有许多元素等于零,这便于矩阵的计算和保存.如果Matlab把一个矩阵当作稀疏矩阵,那么只需在m×3的矩阵中存储m个非零项.第1列是行下标,第2列是列下标,第3列是非零元素值,不必保存零元素.如果存储一个浮点数要8个字节,存储每个下标要4个字节,那么整个矩阵在内存中存储需要16×m个字节. A = e y e ; 得到一个1 0 0 0×1 0 0 0的单位矩阵,存储它需要8Mb空间.如果使用命令: B = s p e y e ; 用一个1 0 0 0×3的矩阵来代表,每行包含有一个行下标,列下标和元素本身.只需1 6 K b的空间就可以存储1 0 0 0×1 00 0的单位矩阵,它只需要满单位矩阵的0 . 2 %存储空间.对于许多的广义矩阵也可这 样来作. 创建转换 在M AT L A B中,用命令s p a r s e来创建一个稀疏矩阵. 命令集8 7创建稀疏矩阵 s p a r s e 由非零元素和下标建立稀疏矩阵A.如果A已是一个稀疏矩阵,则返回A本身. s p a r s e 生成一个m×n的所有元素都是0的稀疏矩阵. s p a r s e 生成一个由长度相同的向量u,v和a定义的稀疏矩阵.其中u和v是整数向量,a是一个实数或者复数向量.对应值ai,如果a中有零元素,则将这个元素排除在外. 稀疏矩阵的大小为m a x ×m a x . s p a r s e 生成一个m×n的稀疏矩阵,对应值ai.向量u,v和a必须长度相同. s p a r s e vi)对应值ai.n z m ax的值必须大于或者等于向量u和v的长度. f i n d 返回向量x中非零元素的下标.如果x=X是一稀疏矩阵个矩阵,那么X的向量就作为一个长向量来考虑. [ u , v ] = f i n d 返回矩阵A中非零元素的下标. [ u , v , s ] = f i n d 返回矩阵A中非零元素的下标.用向量s中元素的值及u和v中相应的下标,实际上就是向量u,v和s作为命令s p a r se的参数. s p c o n v e r t 将一个有三列的矩阵转换成一个稀疏矩阵.D中 的第1列作为行的下标,第2列作为列的下标,最后一列作为元素值.而且可以使用命令f u ll将稀疏矩阵转换成一个满矩阵. 命令集8 8转换成满矩阵 f u l l 将稀疏矩阵S转换成一个满矩阵. a) 创建一个5×5的单位矩阵: A = e y e 将矩阵A转换成稀疏矩阵B: 假设M AT L A B中给出如下的向量: 这样就有了行向量,但是也可使用列向量.运行命令S ma t r i x = s p a r s e , 结果为: 其中有去掉了两个零元素.将这个矩阵转换成满矩阵,输入: F u l l m a t r i x = f u l l 得到的结果为: 注意,稀疏矩阵和得到的满矩阵的大小是分别是由i n d 1和i n d 2中最大元素值确定的,即 使相应的值是零,并且在列出的稀疏矩阵中去掉这个值. 输入命令w h o s可得到: 可以看出虽然两个矩阵的大小相同,但是其中稀疏矩阵需要的存储空间更小些. 在处理稀疏矩阵时f i n d命令很有用.命令对于稀疏矩阵或者满矩阵都返回相同的结果. 返回得到的三个向量直接用来重新创建一个稀疏矩阵.令S m a t r i x定义在中,运行命令: 得到的结果为: 用下面命令得到的矩阵和中得到的矩阵是不一样的: 运算原理简介 M AT L A B中对满矩阵的运算和函数同样可用在稀疏矩阵中.结果是稀疏矩阵还是满矩阵, 这取决于运算符或者函数及下列的操作数:稀疏矩阵的压缩存储当函数用一个矩阵作为输入参数,输出参数为一个标量或者一个给定大小的向量时,输出参数的格式总是返回一个满阵形式,如命令si z e. 当函数用一个标量或者一个向量作为输入参数,输出参数为一个矩阵时,输出参数的格式也总是返回一个满矩阵,如命令e ye.还有一些特殊的命令可以得到稀疏矩阵,如命令s p e y e. 对于单参数的其他函数来说,通常返回的结果和参数的形式是一样的,如d i a g. 对于双参数的运算或者函数来说,如果两个参数的形式一样,那么也返回同样形式的结果.在两个参数形式不一样的情况下,除非运算的需要,均以满矩阵的形式给出结果. 两个矩阵的组和[A B],如果A或B中至少有一个是满矩阵,则得到的结果就是满矩阵. 表达式右边的冒号是要求一个参数的运算符,遵守这些运算规则. 表达式左边的冒号不改变矩阵的形式. 例一 假设有: 这是一个5×5的单位满矩阵和相应的稀疏矩阵. C = 5*B,结果为: 这是一个稀疏矩阵. D = A + B,给出的结果为: 这是一个满矩阵. x = B \ h,结果为: 这是一个满向量. 有许多命令可以对非零元素进行操作. 命令集8 9矩阵的非零元素 n n z 求矩阵A中非零元素的个数.它既可求满矩阵也可求稀疏矩阵. s p y 画出稀疏矩阵A中非零元素的分布.也可用在满矩阵中,在 这种情况下,只给出非零元素的分布. s p y 用指定的颜色c s t r和在s i ze规定的范围内画出稀疏 矩阵A中非零元素的分布. n o n z e r o s 按照列的顺序找出矩阵A中非零的元素. s p o n e s 把矩阵A中的非零元素全换为1. s p a l l o c 有效地减少存储空间和提高运算速度. n z m a x 给出为矩阵A中非零元素分配的内存数.不一定和nn z 得 到的数相同;参见s p a r s e或者s p a l l o c. i s s p a r s e 如果矩阵A是稀疏矩阵,则返回1;否则返回0. s p f u n 用A中所有非零元素对函数f cn求值,如果函数不是对稀疏矩 阵定义的,同样也可以求值. s p r a n k求稀疏矩阵A的结构秩.对于所有的矩阵来说,都有 s p r a n k . 例二 用下面的命令定义稀疏矩阵: 创建一个大矩阵: 稀疏矩阵Big=kron 这个矩阵B i g是什么样子呢? K r o n e c k e r张量积给出一个大矩阵,它的元素是矩阵A的元素之间可能的乘积.因为参量都是稀疏矩阵,所以得到的矩阵也是一个稀疏矩阵.可以用命令w h o s和i s s p a r s e来确认一下. 查看矩阵B i g的结构图,可输入s p y ,结构图如右图所示. 从图中可以看出B ig是一个块双对角矩阵. 特例 MATLAB中有四个基本稀疏矩阵,它们是单位矩阵,随机矩阵,对称随机矩阵和对角矩阵. 命令集9 0单位稀疏矩阵 s p e y e 生成n×n的单位稀疏矩阵. s p e y e 生成m×n的单位稀疏矩阵. 命令speye 得到的结果和s p a r s e )是一样的,但是没有涉及到满阵的存储. 命令集9 1随机稀疏矩阵 s p r a n d 生成与A有相同结构的随机稀疏矩阵,且元素服从均匀分布. s p r a n d 生成一个m×n的服从均匀分布的随机稀疏矩阵,有d e ns×m× n个非零元素,0?d e n s?1.参数d e n s是非零元素的分布密度. s p r a n d 阵.如果rc=rc是一个长度为l?l )的向量,那么 矩阵将rci作为它l个奇异值的第一个,其他的奇异值为0. s p r a n d n 生成与A有相同结构的随机稀疏矩阵,且元素服从正态分布. s p r a n d n 一样. s p r a n d s y m 生成一个随机对称稀疏矩阵.它的下三角及主对角线部分与S的结构相同,矩阵元素服从正态分布. s p r a n d s y m 生成一个m×n的随机对称稀疏矩阵.矩阵元素服从正态分布,分布密度为de n s. s p r a n d s y m 对称分布,但不是正态分布.如果rc=rc是一个向量,则矩阵有特征值rci.也就是说,如果rc是一个正向量,则矩阵是正定矩阵. s p r a n d s y m 阵经随机J a c o b i旋转得到的,其条件数正好等于1/rc;如果k= 2,则矩阵为外积的换位和,其条件数近似等于1/rc. s p r a n d s y m 参数d e n s被忽略,但是这个参数在这个位置以便函数能确认最后两个参数的正确与否. 例三 假设有矩阵A: 输入R a n d o m = s p r a n d n ,可得到随机稀疏矩阵: 矩阵中随机数的位置和矩阵A中非零元素的位置相同. 对于中的矩阵A,输入: B = s p r a n d s y m 结果为: 这是一个用矩阵A的下三角及主对角线部分创建的对称矩阵,在非零元素的位置用随机数作为元素值. 用命令s p d i a g s可以取出对角线元素,并创建带状对角矩阵.假设矩阵A的大小为m×n, 稀疏矩阵在p个对角线上有非零元素.B的大小为mi n ×p,它的列是矩阵A的对角线.向量d的长度为p,其整型分量给定了A的对角元: di0 主对角线上的对角线 命令集9 2对角稀疏矩阵 [ B , d ] = s p d i a g s 求出A中所有的对角元,对角元保存在矩阵B中,它们的下标保存在向量d中. s p d i a g s 生成一个矩阵,这个矩阵包含有矩阵A中向量d规定的对角元. s p d i a g s 生成矩阵A,用矩阵B中的列替换d定义的对角元. A = s p d i a g s 用保存在由d定义的B中的对角元创建稀疏矩阵A. 例11 . 4给出了如何使用s p d i a g s命令来解普通微分方程组. 方程组 稀疏矩阵在许多实际应用中要保留稀疏矩阵的结构,但是在计算过程中的中间结果会减弱它的稀疏性,如LU分解.这就会导致增加浮点运算次数和存储空间.为了避免这种情况发生,在第稀疏矩阵1 2 9 M AT L A B中用命令对矩阵进行重新安排.这些命令都列在下面的命令集9 3中.通过h e l p命令 可以得到每个命令更多的帮助信息,也可见h e l p d e s k. 命令集9 3矩阵变换 c o l m m d 返回一个变换向量,使得矩阵A列的秩为最小. s y m m m d 返回使对称矩阵秩为最小的变换. s y m r c m 矩阵A的C u t h i l l - M c K e e逆变换.矩阵A的非零元素在主对角线附近. c o l p e r m 返回一个矩阵A的列变换的向量.列按非零元素升序排列.有时这是L U因式分解前有用的变换:lu).如果A是一个对称矩阵,对行和列进行排序,这有利于C h o l e s k y分解:chol). r a n d p e r m 给出正数1,2,. . .,n的随机排列,可以用来创建随机变换矩阵. d m p e r m 对矩阵A进行D u l m a g e - M e n d e l s o h n分解,输入helpdmperm可得更多信息. 例四 创建一个秩为4的变换矩阵,可输入: 一旦运行p e r m = r a n d p e r m ,就会得到: 给出的变换矩阵为: 如果矩阵A为: 输入命令: 运行结果为: 有两个不完全因式分解命令,它们是用来在解大线性方程组前进行预处理的.用he l p d e s k命令可得更多信息.命令集9 4不完全因式分解c h o l i n c 进行不完全C h o l e s k y分解,变量o p t取下列值之一: d r o p t o l指定不完全分解的舍入误差,0给出完全分解. m i c h o l如果m i c h o l = 1,则从对角线上抽取出被去掉的元素. r d i a g用s q r t ))代替上三角分 解因子中的零元素,j为零元素所在的列. [ L , U , P ]=返回矩阵X的不完全分解得到的三个矩阵L,U和P,变量o p t取 l u i n c 下列值之一: d r o p t o l指定分解的舍入误差. m i l u改变分解以便从上三角角分解因子中抽取被去掉的列元素. u d i a g用d r o p t o l值代替上三角角分解因子中的对角线上 的零元素. t h r e s h中心极限. 解稀疏线性方程组既可用左除运算符解,也可用一些特殊命令来解. 命令集9 5稀疏矩阵和线性方程组 s p p a r m s 设置稀疏矩阵算法的参数,用helpspparms可得详细信息. s p a u g m e n t 根据[ c*l A; A? 0 ]创建稀疏矩阵,这是二次线性方程组的最 小二乘问题.参见7 . 7节. s y m b f a c t 给出稀疏矩阵的C h o l e s k y和L U因式分解的符号分解因子. 用help symbfact可得详细信息. 稀疏矩阵的范数计算和普通满矩阵的范数计算有一个重要的区别.稀疏矩阵的欧几里德范数不能直接求得.如果稀疏矩阵是一个小矩阵,则用no r m )来计算它的范数;但是对于大矩阵来说,这样计算是不可能的.然而MAT L A B可以计算出欧几里德范数的近似值,在计算条件数时也是一样. 命令集9 6稀疏矩阵的近似欧几里德范数和条件数 n o r m e s t 计算A的近似欧几里德范数,相对误差为10-6. n o r m e s t 计算A的近似欧几里德范数,设置相对误差to l,而不用缺省时的1 0-6. [ n r m , n i t ] =计算近似n r m范数,还给出计算范数迭代的次数n i t. n o r m e s t c o n d e s t 求矩阵A条件数的1-范数中的下界估计值. [ c , v ]=求矩阵A的1 -范数中条件数的下界估计值c和向量v,使得 c o n d e s t | |Av| | = / c.如果给定tr,则给出计算的过程.t r= 1, 给出每步过程;t r=-1,给出商c / r c o n d . 例五 假设给出: 用n o r m A p p r o x = n o r m e s t 计算出: 用t h e N o r m = n o r m )得: 为了找到它们之间的差别,计算d i f f e r e n c e = t h e N o r m - n o r m A p p ro x,得: 在许多应用中,n o r m e s t计算得到的近似值是一个很好的近似欧几里德范数,它的计算步数要比n o r m要少得多;可参见7. 6节. 用e t r e e命令来找到稀疏对称矩阵的消元树,用向量f来描述消元树,还可用e t r e e p l ot命令画出来.元素fi是矩阵的上三角C h o l e s k y分解因子中i行上第1非零元素的列下标.如果有非零元素,则fi=0.消元树可以这样来建立: 节点i是fi的孩子,或者如果fi= 0,则节点i是树的根节点. 命令集9 7矩阵的消元树 e t r e e 求A的消元树向量f,这个命令有可选参数;输入h e l p e t r e e获取帮助. e t r e e p l o t 画出向量f定义的消元树图形. t r e e p l o t 画出指针向量p的树图形,参数c和d分别指定节点的颜色和分支数.e t r ee p l o t可以调用这个命令. t r e e l a y o u t显示树的结构,t r e e p l o t可以调用这个命令. 例六 假设有对称稀疏矩阵B: 运行命令b t r e e = e t r e e ,结果为: 开始的数字2不难理解,它是矩阵的第1列上第1个非零元素的行数,它决定了在C h o l e s ky分解因子的第1行第2列处有一个非零元素.当缩减第1列的元素时就得到第2列的数字5.B在缩减后,在位置的元素是非零的,这样消元树向量中第2个元素的值为5. s p y )给出了C h o l e s k y分解因子的结构图,如图9 - 2所示: 图9-2 Cholesky分解结构图 图9-3 矩阵B的消元树 这个向量消元树可以这样来建立:上三角中只有一行有非零元素,节点8,因此这就是树 稀疏矩阵唯一的根.节点1是节点2的孩子,节点2和3是节点5的孩子,而节点5是节点6的孩子.节点4和6是节点7的孩子,而节点7又是节点8的孩子,即根的孩子. 命令e t r e e p l o t 给出了树的结构图,如图9 - 3所示. 消元树的形状取决于列和行序,它可以用来消元过程. 用g p l o t命令可以画出坐标和矩阵元素间的联系图形.必须在 n×2的矩阵中给出n个坐标, 矩阵的每一行作为一个点.这样就创建出点点之间连接的n×n矩阵,如果点4连接到点8,则的值为1.由于是一个大矩阵,而且非零元素较少,所以它应该被建成稀疏矩阵. 这个图可以说明网络问题,如传递问题.它还包含有线性方程组中未知量之间的相关信息. 命令集9 8网络图形 g p l o t 如果矩阵A的a不为0,则将点ki连接到点kj.K是一个n× 2的坐标矩阵,A是一个n×n的关联矩阵. g p l o t 用字符串s t r给定的颜色和线型画出的同上图形.字符串s t r的 取值参见表1 3 - 1. [ X , A ] = u n m e s h 求网格边界矩阵E的L ap l a c e矩阵A和网格点的坐标矩阵X. 篇四 : 稀疏矩阵:稀疏矩阵-定义，稀疏矩阵-历史 非零元素占全部元素的百分比很小的矩阵。有的矩阵非零元素占全部元素的百分比较大，但它们的分布很有规律，利用这一特点可以避免存放零元素或避免对这些零元素进行运算，这种矩阵仍可称为稀疏矩阵。 稀疏矩阵稀疏矩阵是其元素大部分为零的矩阵。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。在使用计算机存储和操作稀疏矩阵时，经常需要修改算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。 稀疏矩阵_稀疏矩阵 -定义 非零元素占全部元素的百分比很小的矩阵。有的矩阵非零元素占全部元素的百分比较大，但它们的分布很有规律，利用这一特点可以避免存放零元素或避免对这些零元素进行运算，这种矩阵仍可称为稀疏矩阵。 给定1个N×M的稀疏矩阵A，其第n行的行带宽定义为: 稀疏矩阵 整个矩阵的带宽定义为: 稀疏矩阵 稀疏矩阵_稀疏矩阵 -历史 高斯早在20世纪，C.F.高斯、C.G.J.雅可比和其他一些人已经研究过利用矩阵稀疏性的一些办法。20世纪50年代，在线性规划和边值 问题的数值解中曾出现过一些处理稀疏问题的技术。D.M.杨和R.S.瓦尔加关于迭代法方面的研究也可看作处理高阶稀疏问题的结果。但是，现代的稀疏矩阵技术主要是在60年代以后发展起来的，以60年代初期和中期W.F.廷尼和R.A.威洛比等人关于直接法的研究作为开端。 稀疏矩阵_稀疏矩阵 -优点 稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的1个突出的优点.假设矩阵A,B中的矩阵一样.计算2*A需要一百万次的浮点运算,而计算2*B只需要2 0 0 0次浮点运算.因为M AT L A B不能自动创建稀疏矩阵,所以要用特殊的命令来得到稀疏矩阵. 对于1个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节.但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间,可以只存储其中的非0元素. 对于矩阵Amn的每个元素aij,知道其行号i和列号j即可确定其位置.因此对于稀疏矩阵可以用1个结点来存储1个非0元素.该结点可以定义如下:[i,j,aij] 该结点由三个域组成,i:行号,j:列号;aij元素值.这样的结点被称为三元组结点.矩阵的每1个元素Qij,由1个三元组结点唯一确定. 例如稀疏矩阵A: 50 0 0 0 10 0 20 0 0 0 0 0 -30 0 -60 5 其对应的三元组表为: 0 0 50 1 0 10 1 2 20 3 0 -30 3 2 -60 3 3 5 稀疏矩阵_稀疏矩阵 -线性方程组 解线性方程组的直接法的稀疏矩阵技术，根据不同领域中不同问题的特点，有各种不同稀疏解法。最常用的方法有稀疏去零消元法、等带或变带宽消元法、波阵法、子结构法、撕裂和修改技术等，它们都只不过是消元法或三角分解法在各种具体场合下的运用。 各种消元法中的关键问题都是方程式和未知数的排序问题。确切地说，就是在用某种直接法解稀疏线性方程组时，对方程式和未知数进行适当排序，使得在满足一定的稳定性要求的前提下，解方程组所需的运算量和存贮量最少。一般说来，这等价于使新产生的非零元最少。例如，对矩阵 作1步消元法，将A变成 ， 右下角子阵是满的,A的零元所在位置上产生了许多非零元，破坏了稀疏性，这就要增加许多存贮量和运算量;如果将矩阵A的第一行与最后一行,第一列与最后一列交换，这相当于重新排列方程式和未知数的次序，得矩阵 ， 对?作消元法时,不会有新的非零元产生，存贮量和运算量大大减少。 稀疏矩阵_稀疏矩阵 -存贮 与常用的算法相对应,排序问题可分为以下3类:?预先把矩阵排列成带型或变带宽型，并使带宽或剖面尽可能小;?预先把矩阵排列成块三角矩阵或其他特殊分块矩阵;?在稀疏消元法的消元过程中，根据产生添补数最少的原则来确定选主元的次序。对一般矩阵，排序问题是1个非常困难的问题，因为对1个给定的矩阵来说，所有可能的次序总数是1个巨大的数字，可以给出的排序算法只是按某一特殊准则来确定“最佳次序”的。讨论中常用图论作为工具。 稀疏矩阵的存贮并没有1种最好的方式，在各种具体情况下，最好的方式与要存贮矩阵的结构及用途有关1种好的标准是矩阵的元素容易查找而且存贮量少。存贮方式基本上采用压缩形式，使矩阵中大量的零元素不参加运算，以减少机器的运行时间，并可提高机器处理高阶矩阵问题的能力。 对于带型矩阵，只存贮带内或剖面内的元素。如对矩阵 可用等带宽存贮法，在带的左上角和右下角增添若干个任意元素x，把带内的元素存放在矩形数组 中。 对于对称带型阵 可用变带宽存贮法。它需要2个数组:?存放剖面内的元素的一维数组S={b11,b21，b22，b31，0，b33,b44，b53,0,b55,b66};?对角元数组D={1,3,6,7,10,11}，在它的第i个位置上存放对角元bii在数组S中的序号。这样,矩阵的元素bij可通过D，i，j在S中找到。对应关系为 并规定D=0。例如,由D=6,D=3,D-3 1>D，可得b31=S。 对于元素随机分布的稀疏矩阵，只存贮矩阵的非零元素和必要的检索信息。如对 可用行指针列标格式存贮，它需要3个数组:?根据按行向右的次序，存放矩阵非零元值的数组V={p11，p12，p14，p23，p31，p34，p41，p43,p44};?存放V中每一元素在原矩阵中的列标的数组C=,1,2,4,3,1,4,1,3,4,;?数组R=,1,4,5,7,10,，在它的第i个位置上存放矩阵第i行的第1个非零元在数组V中的序号,最后1个位置上的数等于矩阵非零元素个数加1。矩阵p的任意非零元素可根据R和C的值定出它在V中的位置。例如p31,先由R=5，R=7，确定第三行有2个非零元V和V，再检查V和V的列标,由C=1,C=4，可推出V=p31。 此外，还有连接表存贮法和超矩阵存贮法等。 稀疏矩阵_稀疏矩阵 -应用 稀疏矩阵 稀疏矩阵的研究已经渗入到很多领域。例如，在结构分析、网络理论、电力分配系统、化学工程、摄影测绘学以及管理科学等方面研究中，都出现了上千阶直至几百万阶的稀疏矩阵。 这里考察从1个电信总局到其各支局间的通信问题。不妨假定有5个支局，依次编为1，2，3，4，5号,而总局编为6号，在平面上分别使用?，?，…,?这6个点表示。如果规定i局和j局之间有通信关系的话，在点i和j之间用一条线连结，对应于矩阵中Aij块和Aji块非零,i局本身内部也有通信关系,对应于矩阵Aii块非零,那么，这个问题所导出的矩阵是1个双面镶边的块对角矩阵它是1个稀疏矩阵。 稀疏矩阵_稀疏矩阵 -相关词条 矩阵 微积分 迭代 存贮 稀疏矩阵_稀疏矩阵 -参考资料 [1]. 梯华森著,朱季纳译:《稀疏矩阵》，科学出版社,北京，1981。 [2].数据结构 上一篇文章:[中国作家富豪榜首富]当我们谈起中国作家富豪榜首富，谈的是江南 下一篇文章:[流星是怎么形成的]流星是怎么形成的