当前位置：文档库 › 稀疏矩阵的存储及运算

稀疏矩阵的存储及运算

存储

什么是稀疏矩阵？人们无法给出确切的定义，它只是一个凭人们的直觉来了解的概念。假若在m*n的矩阵中，非零元个数num<

存储稀疏矩阵时，往往只存放其中的非零元。稀疏矩阵的三元组表法是顺序存储方法的一种。采用这种方法时，线性表中的每个结点对应稀疏矩阵的一个非零元素，其中包括3个字段，分别为该元素的行下标、列下标和值，结点间的次序按矩阵的行优先顺序排列。另外，用第0行的三个元素分别存储矩阵的行数、列数和非零元数目。例如，矩阵A：

50 0 7

0 1 0 0

10 0 0 可以用三元组表示为： 3 4 4

1 1 5

1 4 7

2 2 1

3 1 1

在具体编程过程中，往往可以用一个简单的n*3二数组来表示此三元组。即稀疏矩阵A可以用数组a[5][3]={{3,4,4},{1,1,5},{1,4,7},{2,2,1},{3,1,1}} 来表示。

运算

1）矩阵转置（带回溯）

由于稀疏矩阵中的元素的存储是按行优先存储的，因此三元组中数据的行下标递增有序，行下标相同时列下标递增有序。存储转置后的矩阵，只要将三元组a的第一行依次将a中的列值由小到大进行选择，将选中的三元组元素行列值互换后放入三元组b，直到三元组a中的元素全部放入b中为止。

2）不带回溯的转置

不带回溯的转置要解决的关键问题是要预先确定好矩阵的每一列第一个非

零元素在三元组b中应有的位置。为了确定这些位置，转置前必须求得三元组a 中每一列非零元的个数，从而得到每列第一个元素在三元组b中（行）的位置。用pot数组来记录。

pot[1]=1；

pot[col]=pot[col-1]+第col-1列非零元的个数（pot[col]）

3）矩阵相加 C = A + B

稀疏矩阵相加采用的算法思想是：依次扫描 A和B的行号和列号，如果A 的当前项的行号等于B的当前项的行号，则比较其列号，将较小的项存入C。若

列号也相等，则将对应的元素相加后存入C；若A的当前项的行号小于B的，则将A的项存入C，否则将B的项存入C。

[注]：if a[i][0]= = b[i][0]&& a[i][1]< b[i][1] 表明该位置上B矩阵为零而A矩阵的元素不为零，相加后的C矩阵的该位置元素应为A矩阵的该元素，故将较小者存入C。

4）矩阵相乘C = A * B

矩阵的乘法涉及到两矩阵不同行，列之间的运算，情况相对复杂。稀疏矩阵的乘法采用普通矩阵相乘的基本方法，关键是通过给顶的行号和列号找出原矩阵对应的元素值。这里设计一个函数value，当在三元组表示中找到时返回其元素值，找不到时，说明该位置为0，因此返回0。然后利用该函数计算出C的行号i和列号j 处的元素值，若该值不为0，则存入其三元组表示的矩阵，否则不存入。

完整的参考C程序如下:

#include

#define max 20

convert(int a[max][3],int a1[max][3])

{int p,q,col;

a1[0][0]=a[0][1];

a1[0][1]=a[0][0];

a1[0][2]=a[0][2];

if(a1[0][2]!=0)

{q=1;

for(col=1;col<=a[0][1];col++)

for(p=1;p<=a[0][2];p++)

if(a[p][1]==col)

{a1[q][1]=a[p][0];

a1[q][0]=a[p][1];

a1[q][2]=a[p][2];

q++;

}

add(int a[max][3],int b[max][3],int c[max][3]) //error!!

{int i=1,j=1,k=1;

while(i<=a[0][2]&&j<=b[0][2])

{if(a[i][0]==b[j][0])

{if(a[i][1]

{c[k][0]=a[i][0];

c[k][1]=a[i][1];

c[k][2]=a[i][2];

k++;

i++;

}

else if(a[i][1]>b[j][1]) {c[k][0]=b[j][0];

c[k][1]=b[j][1];

c[k][2]=b[j][2];

k++;

j++;

}

else

{c[k][0]=b[j][0];

c[k][1]=b[j][1];

c[k][2]=a[i][2]+b[j][2]; k++;

i++;

j++;

}

else if(a[i][0]

c[k][1]=a[i][1];

c[k][2]=a[i][2];

k++;

i++;

}

else

{c[k][0]=b[j][0];

c[k][1]=b[j][1];

c[k][2]=b[j][2];

k++;

j++;

}

c[0][0]=a[0][0];

c[0][1]=a[0][1];

c[0][2]=k-1;

}

int value(int c[max][3],int i,int j)

{int k=1;

while(k<=c[0][2]&&!(c[k][0]==i&&c[k][1]==j)) k++;

if(c[k][0]==i&&c[k][1]==j)

return(c[k][2]);

else return(0);

}

multi(int a[max][3],int b[max][3],int c[max][3]) {int i,j,p,s,q;

p=1;

for(i=1;i<=a[0][0];i++)

for(j=1;j<=b[0][1];j++)

{s=0;

for(q=1;q<=a[0][1];q++)

s=s+value(a,i,q)*value(b,q,j);

if(s!=0)

{c[p][0]=i;

c[p][1]=j;

c[p][2]=s;

p++;

}

c[0][0]=a[0][0];

c[0][1]=b[0][1];

c[0][2]=p-1;

}

print(int a[max][3])

{int i,j;

for(i=0;i<=a[0][2];i++)

{for(j=0;j<=2;j++)

printf(" %d",a[i][j]);

printf("/n");

}

main()

{int a[max][3],b[max][3],a1[max][3],b1[max][3],c[max][3],d[max][3]; int i,y;

printf("输入稀疏方阵A的行数，列数和非零元个数：");

scanf("%d,%d,%d",&a[0][0],&a[0][1],&a[0][2]);

for(i=1;i<=a[0][2];i++)

{

printf("输入第%d个非0元素的行数，列数和值:",i);

scanf("%d,%d,%d",&a[i][0],&a[i][1],&a[i][2]);

}

printf("输出A的三元组表示：/n");

print(a);

printf("/n输入稀疏方阵B的行数，列数和非零元个数：");

scanf("%d,%d,%d",&b[0][0],&b[0][1],&b[0][2]);

for(i=1;i<=b[0][2];i++)

{

printf("输入第%d个非0元素的行数，列数和值:",i);

scanf("%d,%d,%d",&b[i][0],&b[i][1],&b[i][2]);

}

printf("输出B的三元组表示：/n");

print(b);

printf("/n");

printf("============= 菜单==============/n");

printf(" 1 A矩阵转置/n");

printf(" 2 B矩阵转置/n");

printf(" 3 C = A + B/n");

printf(" 4 D = A * B/n");

printf("======================================/n/n");

loop: printf("请选择相应操作的序号:");

scanf("%d",&y);

switch(y)

{case 1: convert(a,a1);

printf("输出A转置的三元组表示：/n");

print(a1);

printf("/n");

goto loop;

case 2: convert(b,b1);

printf("输出B转置的三元组表示：/n");

print(b1);

printf("/n");

goto loop;

case 3: add(a,b,c);

printf("输出C=A+B的三元组表示：/n");

print(c);

printf("/n");

goto loop;

case 4: multi(a,b,d);

printf("输出D=A*B的三元组表示：/n");

print(d);

printf("/n");

goto loop;

}

哪个提问。。记不住了。。

补充：

#include

using namespace std;

class Matrix

{private:

int row,col;

double **mx;

public:

Matrix(){}

~Matrix();

Matrix(Matrix &m);

Matrix(int n,int m);

friend Matrix operator*(Matrix &,Matrix &);

friend istream & operator >>(istream &,Matrix &); friend ostream & operator <<(ostream &,Matrix &); friend Matrix operator+(Matrix &,Matrix &);

friend Matrix operator-(Matrix &,Matrix &);

friend Matrix operator!(Matrix &);

};

Matrix::Matrix(Matrix &m)

{

int i,j;

row=m.row;

col=m.col;

mx=new double *[row];

for(i=0;i

mx[i]=new double[col];

for(i=0;i

for(j=0;j

mx[i][j]=m.mx[i][j];

}

Matrix::~Matrix()

{

int i;

for(i=0;i

delete [] mx[i];

delete []mx;

}

Matrix::Matrix(int n,int m)

{

int i,j;

row=n;

col=m;

mx=new double *[row];

for(i=0;i

mx[i]=new double[col];

for(i=0;i

for(j=0;j

mx[i][j]=0;

}

istream& operator>>(istream &input,Matrix &m) {

int i,j;

for(i=0;i

for(j=0;j

input>>m.mx[i][j];

return input;

}

Matrix operator+(Matrix &m1,Matrix &m2)

{

Matrix m(m1.row,m1.col);

int i,j;

for(i=0;i

for(j=0;j

m.mx[i][j]=m1.mx[i][j]+m2.mx[i][j];

return m;

}

Matrix operator*(Matrix &m1,Matrix &m2)

{

if(m1.col!=m2.row)throw 1;

Matrix m(m1.row,m2.col);

int i,j,t=0,s,l=0;

for(i=0;i

{

for(j=0,s=0;j

m.mx[t][l]+=m1.mx[t][j]*m2.mx[s][l];

}

if((i+1)%m.col==0) {t++;l=0;}

else l++;

}

return m;

}

ostream& operator<<(ostream &output,Matrix &m) {

int i,j;

for(i=0;i

for(j=0;j

{

output<

if(j==m.col-1) cout<

}

return output;

}

Matrix operator-(Matrix &m1,Matrix &m2)

{

Matrix m(m1.row,m1.col);

int i,j;

for(i=0;i

for(j=0;j

m.mx[i][j]=m1.mx[i][j]-m2.mx[i][j];

return m;

}

Matrix operator!(Matrix &m1)

{

int i,j;

Matrix m(m1.col,m1.row);

for(i=0;i

for(j=0;j

m.mx[j][i]=m1.mx[i][j];

return m;

}

int main()

{

int n,m;

int n1,n2;

cout<<"**********加法与减法**********"<

cin>>n>>m;

Matrix m1(n,m);

cout<<"输入第一个矩阵："<

cin>>m1;

Matrix m2(n,m);

cout<<"输入第二个矩阵："<

cin>>m2;

Matrix m3(m1+m2);

cout<<"两矩阵相加后："<

cout<

cout<<"两矩阵相减后："<

Matrix m31(m1-m2);

cout<

cout<<"**********乘法*********"<

cout<<"请输入第一个矩阵的行与列：";

cin>>n>>m;

Matrix m4(n,m);

cout<<"输入第一个矩阵："<

cin>>m4;

cout<<"请输入第二个矩阵的行与列：";

cin>>n1>>n2;

Matrix m5(n1,n2);

cout<<"输入第二个矩阵："<

cin>>m5;

try{

Matrix m6(m4*m5);

cout<<"两矩阵相乘后："<

cout<

}

catch(int)

{

cout<<"第一个矩阵的列数不等于第二个矩阵的行数，所以不能相乘！"<

}

cout<<"**********转置**********"<

cout<<"请输入矩阵的行与列：";

cin>>n>>m;

Matrix m7(n,m);

cout<<"输入一个矩阵："<

cin>>m7;

Matrix m8(!m7);

cout<<"转置后："<

cout<

return 0;

}

-----------------------------------------------------------------------

S P A R S K I T V E R S I O N 2.

-----------------------------------------------------------------------

Latest update : Tue Mar 8 11:01:12 CST 2005

-----------------------------------------------------------------------

Welcome to SPARSKIT VERSION 2. SPARSKIT is a package of FORTRAN subroutines for working with sparse matrices. It includes general sparse matrix manipulation routines as well as a few

iterative

solvers, see detailed description of contents below.

SPARSKIT is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation [version 2.1 of the License, or any later version.]

A copy of the licencing agreement is attached in the file LGPL. For additional information contact the Free Software Foundation Inc., 59 Temple Place - Suite 330, Boston, MA 02111, USA or visit the web-site

https://www.wendangku.net/doc/9612980133.html,/copyleft/lesser.html

DISCLAIMER

----------

SPARSKIT is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

For more information contact saad@https://www.wendangku.net/doc/9612980133.html,

---------------------------------------------------

S P A R S K I T VERSION 2

---------------------------------------------------

In this directory you will find all relevant subdirectories and the Unix makefile which will compile all the modules and make a unix library libskit.a. Please read the makefile. Making the library should be the first thing to do when starting to use the package. Some of the objects will be linked into a library

called

libskit.a. Others will not be linked but can be used by other makefiles for test problems provided in the subdirectories. You can then link to libskit.a by default instead of the

individual

modules. (Please report any compilation problems or (even minor) warnings immediatly to saad@https://www.wendangku.net/doc/9612980133.html,). Once this is done, it is recommended to run the test problems provided. There are various test suites in each of the subdirectories and makefiles are available for each. See explanations in the README files in each individual subdirectory.

You may also make and run the test programs using the dotests script provided in this directory. Output from this script may be redirected into a file and compared to the sample output files out.xxx. There is an additional script called sgrep which is useful for looking for tools in all the subdirectories. Read the sgrep file

for

instructions.

-----------------------------------------------------------------------

Here is some information on the SPARSKIT sub-directories.

BLASSM : Basic linear algebra with sparse matrices.

contains two modules: blassm.f and matvec.f

DOC : contains the main documentation of the package

INFO : information routine (new one) . Info2 (spectral

information) not available yet.

FORMATS: Contains the Format Conversion routines in

formats.f and the manipulation routines in

unary.f

INOUT : input output routines. contains the module inout.f

ITSOL : contains the iterative solution package. Various

iterative solvers and preconditioners are provided.

MATGEN : matrix generation routines.

contains the module genmat.f and several subroutines

called by it. Also contains zlatev.f (contributed

by E. Rothman, from Cornell).

ORDERINGS:

still in the works. But contains a few coloring routines

and level-set related orderings -- (e.g., cuthill Mc Kee, etc.)

UNSUPP : various `unsupported' routines and drivers.

(misc. routines includind routines for

plotting.. BLAS1 is also added for completeness)

See the file "logfile" for a complete revision history.

Report any problems, suggestions, etc.. to

Yousef Saad.

saad at cs dot umn dot edu

-----------------------------------------------------------------------

稀疏矩阵运算器（纯C编写

#include "string.h"

#include "ctype.h"

#include "malloc.h"

#include "stdio.h"

#include "stdlib.h"

#include "conio.h"

#include "mem.h"

#include "alloc.h"

#define OK 1

#define ERROR 0

#define MAXSIZE 100

#define MAXRC 20

typedef int Status;

typedef int ElemType;

typedef struct

{

int i,j;

ElemType e;

}Triple;

typedef struct

{

Triple data[MAXSIZE+1]; /* 非零元三元组表,data[0]未用 */ int rpos[MAXRC+1]; /* 各行第一个非零元素的位置表*/

int mu,nu,tu; /* 矩阵的行数、列数和非零元个数*/

}RLSMatrix;

typedef struct OLNode

{

int i,j;

ElemType e;

struct OLNode *right,*down;

}OLNode,*OLink;

typedef struct

{

OLink *rhead,*chead;

int mu,nu,tu;

}CrossList;

Status CreateSMatrix(RLSMatrix *M);

void DestroySMatrix(RLSMatrix *M);

void PrintSMatrix(RLSMatrix M);

Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T);

int menu_select();

Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C);

Status Exchange(RLSMatrix M,CrossList *N);

Status Show(CrossList N);

Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M);

Status DestoryCrossList(CrossList *M);

void About();

main()

{

RLSMatrix A,B,C;

CrossList N;

clrscr();

About();

for(;;)

{

switch(menu_select()) /*调用主菜单函数，返回值做开关语句的条件*/

{

case 1:clrscr();

printf("\n\n\n\t-------------Create Sparse Matrix A-----------------"); CreateSMatrix(&A); break;

case 2:clrscr();

printf("\n\n\n\t-------------Create Sparse Matrix B-----------------"); CreateSMatrix(&B); break;

case 3:

Operate(A,B,&C);

break;

case 4:Change(A,B,C,&N); break;

case 5:About();break;

case 6:

DestroySMatrix(&A);

DestroySMatrix(&B);

DestroySMatrix(&C);

DestoryCrossList(&N);

exit(0);

}

int menu_select()

{

char *menu[]={

"",

" +--------------MENU--------------+", /*定义菜单字符串数组*/ " | |",

" | 1.Create Sparse Matrix A |",

" | 2.Create Sparse Matrix B |",

" | 3.Operate |",

" | 4.Change into CrossList |",

" | 5.About... |",

" | 6.Quit |",

" | |",

" +--------------------------------+",

" By Zacard",

" 06 07 10",};

char s[3]; /*以字符形式保存选择号*/

int c,i; /*定义整形变量*/

gotoxy(1,25);

printf("Any key to enter menu......\n");

getch();

clrscr();

for(i=0;i<16;i++) /*输出主菜单数组*/

{ gotoxy(10,i+1);

cprintf("%s",menu[i]);

}

window(1,1,80,25); /*恢复原窗口大小*/

gotoxy(10,21);

do{printf("\n Enter your choice(1~6):");

scanf("%s",s);

c=atoi(s); /*将输入的字符串转化为整形数*/

}while(c<1||c>6);

return c; /*返回选择项，主程序根据该数调用相应的函数*/

}

Status CreateSMatrix(RLSMatrix *M) /* 创建稀疏矩阵M */

{

int i; /*用于暂存data域内容*/

Triple T;

int flag=0,mis; /*标志，输入正确为0*/

printf("\nPlease input the row,col,and nonzero element number of the Sparse Matrix.");

printf("\nForm:row num,col num,nonzero element num\n");

scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);

(*M).data[0].i=0; /* 为以下比较做准备 */

for(i=1;i<=(*M).tu;i++)

{ mis=0;

{

if(flag)

{

printf("ERROR INPUT!\n");

flag=0;

mis++;}

if(mis==3)

{

printf("Fail Create !");

return OK;}

printf("Please input the row,col and value of the %dth nonzero element:",i);

scanf("%d,%d,%d",&T.i,&T.j,&T.e);

if(T.i<1||T.i>(*M).mu||T.j<1||T.j>(*M).nu) /* 行或列超出范围 */

flag=1;

if(T.i<(*M).data[i-1].i||T.i==(*M).data[i-1].i&&T.j<=(*M).data[i-1].j) /* 没有按顺序输入非零元素 */ flag=1;

}while(flag); /* 当输入有误,重新输入 */

(*M).data[i]=T;

}

for(i=1;i<=(*M).tu;i++) /* 计算rpos[] */

for(T.i=0;T.i<(*M).data[i].i-(*M).data[i-1].i;T.i++) /* (*M).data[i]为第一个非0元素 */

(*M).rpos[(*M).data[i].i-T.i]=i;

for(i=(*M).data[(*M).tu].i+1;i<=(*M).mu;i++) /* 给最后没有非零元素的几行赋值 */

(*M).rpos[i]=(*M).tu+1;

PrintSMatrix(*M);

return OK;

}

void PrintSMatrix(RLSMatrix M) /* 输出稀疏矩阵M */

{

int i,j,k;

printf("\n ");

for(i=1,k=1;i<=M.mu;i++)

{

for(j=1;j<=M.nu;j++)

{

if(M.data[k].i==i&&M.data[k].j==j)

{printf("%d\t",M.data[k].e); k++;}

else printf("0\t");

while(j==M.nu)

{printf("\n ");break;}

}

Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /* 求稀疏矩阵的和Q=M+N */

{

int k,p,q;

if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;

(*Q).mu=M.mu;

(*Q).nu=M.nu;

(*Q).tu=0;

M.rpos[M.mu+1]=M.tu+1; /* 为方便后面的while循环临时设置 */

N.rpos[N.mu+1]=N.tu+1;

for(k=1;k<=M.mu;++k) /* 对于每一行，k指示行号 */

{

(*Q).rpos[k]=(*Q).tu+1;

p=M.rpos[k]; /* p指示M矩阵第k行当前元素的序号 */

q=N.rpos[k]; /* q指示N矩阵第k行当前元素的序号 */

/* 当某一行不存在非零元素时，它对应的非零位置表的值为下一个非零元素的位置*/

while(p

if(M.data[p].j==N.data[q].j) /* M矩阵当前元素和N矩阵当前元素的列相同 */

{

(*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e; /* 位置相同*/

if((*Q).data[(*Q).tu+1].e!=0) /* 相加结果为0?*/

{

++(*Q).tu;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

}

++p;

++q;

}

else if(M.data[p].j

{ /* M矩阵当前元素的列

++(*Q).tu;

(*Q).data[(*Q).tu].e=M.data[p].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

++p;

}

else /* M矩阵当前元素的列>N矩阵当前元素的列 */

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=N.data[q].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=N.data[q].j;

++q;

}

while(p

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=M.data[p].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

++p;

}

while(q

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=N.data[q].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=N.data[q].j;

++q;

}

return OK;

}

Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /* 求稀疏矩阵的差Q=M-N */ {

int i;

if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;

for(i=1;i<=N.tu;++i) /* 对于N的每一元素,其值乘以-1 */

N.data[i].e*=-1;

ADD(M,N,Q); /* Q=M+(-N) */

return OK;

}

Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /* 求稀疏矩阵乘积Q=M＊N*/ {

int arow,brow,p,q,ccol,ctemp[MAXRC+1]; /* ctemp[MAXRC+1]为列元素累加器*/

if(M.nu!=N.mu) return ERROR; /* 矩阵M的列数应和矩阵N的行数相等 */

(*Q).mu=M.mu; /* Q初始化 */

(*Q).nu=N.nu;

(*Q).tu=0;

M.rpos[M.mu+1]=M.tu+1; /* 为方便后面的while循环临时设置 */

N.rpos[N.mu+1]=N.tu+1;

if(M.tu*N.tu!=0) /* M和N都是非零矩阵 */

{

for(arow=1;arow<=M.mu;++arow)

{ /* 从M的第一行开始，到最后一行，arow是M的当前行 */

for(ccol=1;ccol<=(*Q).nu;++ccol)

ctemp[ccol]=0; /* Q的当前行的各列元素累加器清零 */

(*Q).rpos[arow]=(*Q).tu+1; /* Q当前行的第1个元素位于上1行最后1个元素之后 */ for(p=M.rpos[arow];p

{ /* 对M当前行中每一个非零元 */

brow=M.data[p].j; /* 找到对应元在N中的行号(M当前元的列号) */

for(q=N.rpos[brow];q

{

ccol=N.data[q].j; /* 乘积元素在Q中列号 */

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}

} /* 求得Q中第arow行的非零元 */

for(ccol=1;ccol<=(*Q).nu;++ccol) /* 压缩存储该行非零元 */

if(ctemp[ccol])

{

if(++(*Q).tu>MAXSIZE) return ERROR;

(*Q).data[(*Q).tu].i=arow;

(*Q).data[(*Q).tu].j=ccol;

(*Q).data[(*Q).tu].e=ctemp[ccol];

}

return OK;

}

Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T)

{

int col,p,q,t,num[MAXRC+1],cpot[MAXRC+1];

(*T).mu=M.nu; /* num[]存M每列非0元个数 */

(*T).nu=M.mu; /* cpot[]存每列第一个非0元序号 */

(*T).tu=M.tu;

if((*T).tu){

for(col=1;col<=M.nu;++col) num[col]=0;

稀疏矩阵的计算概论

#include #include #include typedef int ElemType;// 稀疏矩阵的十字链表存储表示 typedef struct OLNode { int i,j; // 该非零元的行和列下标 ElemType e; // 非零元素值 struct OLNode *right,*down; // 该非零元所在行表和列表的后继链域}OLNode, *OLink; typedef struct// 行和列链表头指针向量基址,由CreatSMatrix_OL()分配{ OLink *rhead, *chead; int mu, nu, tu; // 稀疏矩阵的行数、列数和非零元个数 }CrossList; // 初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错) int InitSMatrix(CrossList *M) { (*M).rhead=(*M).chead=NULL; (*M).mu=(*M).nu=(*M).tu=0; return 1; } // 销毁稀疏矩阵M int DestroySMatrix(CrossList *M) { int i; OLNode *p,*q; for(i=1;i<=(*M).mu;i++) // 按行释放结点 { p=*((*M).rhead+i); while(p) { q=p; p=p->right; free(q); } } free((*M).rhead); free((*M).chead); (*M).rhead=(*M).chead=NULL; (*M).mu=(*M).nu=(*M).tu=0; return 1; }

第3章矩阵及其运算

第3章矩阵及其运算 3.1 基本要求、重点难点基本要求： 1．1．掌握矩阵的定义. 2．2．掌握矩阵的运算法则. 3．3．掌握伴随矩阵的概念及利用伴随矩阵求逆矩阵的方法. 4．4．掌握矩阵秩的概念及求矩阵秩的方法. 5．5．掌握初等变换和初等矩阵的概念，能够利用初等变换计算矩阵的秩，求可逆矩阵的逆矩阵. 6．6．掌握线形方程组有解得判定定理及其初等变换解线形方程组的方法. 重点难点：重点是矩阵定义，矩阵乘法运算，逆矩阵的求法，矩阵的秩，初等变换及线性方程组的解. 难点是矩阵乘法，求逆矩阵的伴随矩阵方法. 3.2 基本内容 3.2.1 3.2.1 重要定义定义3.1 由n m ?个数)2,1;,2,1(n j m i a ij ==组成的m 行n 列的数表成为一个m 行n 列矩阵，记为 ????????????mn m m n n a a a a a a a a a 2122221 11211 简记为A n m ij a ?=)(，或A )(ij a =,n m A ?,mn A 注意行列式与矩阵的区别：（1）（1）行列式是一个数，而矩阵是一个数表. （2）（2）行列式的行数、列数一定相同，但矩阵的行数、列数不一定相同. （3）（3）一个数乘以行列式，等于这个数乘以行列式的某行（或列）的所有元素，而一个数乘以矩阵等于这个数乘以矩阵的所有元素. （4）（4）两个行列式相等只要它们表示的数值相等即可，而两个矩阵相等则要求两个矩阵对应元素相等. （5）（5）当0||≠A 时，||1A 有意义，而A 1 无意义.

n m =的矩阵叫做阶方阵或m 阶方阵.一阶方阵在书写时不写括号，它在运算中可看做一个数. 对角线以下（上）元素都是0的矩阵叫上（下）三角矩阵，既是上三角阵，又是下三角的矩阵，也就是除对角线以外的元素全是0的矩阵叫对角矩阵.在对角矩阵中，对角线上元素全一样的矩阵叫数量矩阵；数量矩阵中，对角线元素全是1的n 阶矩阵叫n 阶单位矩阵，常记为n E （或n I ），简记为E （或I ），元素都是0的矩阵叫零矩阵，记为n m 0?，或简记为0. 行和列分别相等的两个矩阵叫做同型矩阵，两个同型矩阵的且对应位置上的元素分别相等的矩阵叫做相等矩阵. 设有矩阵A =n m ij a ?)(，则A -n m ij a ?-=)(称为A 的负矩阵. 若A 是方阵，则保持相对元素不变而得到的行列式称为方针A 的行列式，记为||A 或A Det . 将矩阵A 的行列式互换所得到的矩阵为A 的转置矩阵，记为T A 或A '. 若方阵A 满足A A T =，则称A 为对称矩阵，若方阵A 满足A A T -=，则称A 为反对称矩阵. 若矩阵的元素都是实数，则矩阵称为实矩阵.若矩阵的元素含有复数，则称矩阵为复矩阵，若A =n m ij a ?)(是复矩阵，则称矩阵n m ij a ?)(（其中ij a 为ij a 的共轭矩阵，记为A n m ij a ?=)(. 定义3.2 对于n 阶矩阵A ，如果存在n 阶矩阵B ，使得E BA AB ==，则称方阵A 可逆，B 称为A 的逆矩阵，记做1-=A B . 对于方阵A n m ij a ?=)(，设ij a 的代数余子式为ij A ，则矩阵 *A ????????????=nm n n n n A A A A A A A A A 2122212 12111 称为A 的伴随矩阵，要注意伴随矩阵中元素的位置. 定义3.3 设有矩阵A ，如果：（1）（1）在A 中有一个r 阶子式D 不为零.

MATLAB数值计算功能(向量、矩阵、数组、稀疏矩阵)

数值计算功能向量及其运算 1、向量生成（1)、直接输入向量元素用“［］”括起来，用空格或逗号生成行向量，用分号生成列向量 a１=［１１1４1７1８] ａ2＝[１1,14,１７,１8] a2=[１1;1４;1７;1８] %列向量用“’”可以进行向量转置 a1＝[11 14 １７１８] a4=ａ1'??%a1行向量，a4列向量也可以用组合方法： A=[１ 2 3]； B=［7 8 9]; Ｃ=［A ４onｅｓ(1,2)B］ (2)、等差元素向量生成冒号生成法：Vec＝Vｅｃ0:ｎ：Ｖｅcn,其中Ｖec表示生成的向量，Veｃ０表示第一个元素，ｎ表示步长，Vecn表示最后一个元素使用ｌiｎｅspａce函数：Vec＝ｌinesｐacｅ(Vｅc０,n,Vecn），其中Ｖｅc表示生成的向量，Vec0表示第一个元素,n表示生成向量元素个数(默认n＝100)，Vｅcn表示最后一个元素 veｃ1=10:5：５0 veｃ2=50：-5:1０ vｅc3＝linspace(１0,50,６) ２、向量的基本运算（1）、向量与数的四则运算向量中每个元素与数的加减乘除运算(除法运算时,向量只能作为被除数,数只能作为除数）vec1＝liｎspａcｅ(10,5０，６） vec1+10０ vec2=lｏｇspace(0,10,6)??％对数等分向量ｖｅｃ2／100 (2)、向量与向量之间的加减运算向量中的每个元素与另一个向量中相对应的元素的加减运算 veｃ１=lｉnsｐace(10,５0,6) ｖec2=lｏgspaｃe（０,２,6) vec３＝vｅc1+vec2 (3）、点积、叉积和混合机点积：dｏt函数，注意向量维数的一致性 x1=［11 22 33 44] x2=[1 2 3 4]

矩阵的秩与行列式的几何意义

矩阵的秩与行列式的几何意义这里首先讨论一个长期以来困惑工科甚至物理系学生的一个数学问题，即，究竟什么是面积，以及面积的高维推广（体积等）？ 1 关于面积：一种映射大家会说，面积，不就是长乘以宽么，其实不然。我们首先明确，这里所讨论的面积，是欧几里得空间几何面积的基本单位：平行四边形的面积。平行四边形面积的定义，几何上说是相邻两边边长乘以他们之间的夹角的正弦。然而为了应对更一般情形和更高维度的数理问题，我们有必要把面积的定义推广开来。注意到以下事实：面积是一个标量，它来自于（构成其相邻边）两个矢量。因此，我们可以将面积看成一个映射：其中V就是一个矢量，V*V代表两个矢量的有序对；f就是面积的值。下面我们将说明这个映射是一个线性映射。从最简单的例子出发。如果第一个矢量是（1，0），第二个矢量是（0，1）；也就是说，两个矢量分别是X和Y轴上的单位正向量，那么由这两个矢量张成的四边形就是一个正方形，其面积根据定义，就是长乘以宽=1*1=1。因此有：

如果我们把第一个矢量”缩放“a倍，面积将会相应是原来的a倍；把第二个矢量“缩放”b倍，面积也会成为原来的b倍。如果同时缩放，很显然，面积将会变成原面积的ab倍。这表明，面积映射对于其两个操作数（矢量）的标量积是各自线性的，如下：最后，我们要说明，面积映射对于其操作数（矢量）的矢量加法也是线性的。因为矢量加法操作的本身是线性的，那么其面积映射理应对此也是一个线性映射。这里我们打算从几个实际的例子出发，说明映射的加法线性性的后果。显然（两个共线矢量所张成的平行四边形还是一条线，因此面积为0）：假定面积映射是一个关于矢量加法的线性映射，那么我们有：注意计算过程中用到了上面的结论。这说明：

数据结构稀疏矩阵基本运算实验报告

课程设计课程：数据结构题目：稀疏矩阵4 三元组单链表结构体(行数、列数、头) 矩阵运算重载运算符优班级：姓名：学号：设计时间：2010年1月17日——2010年5月XX日成绩：指导教师：楼建华

一、题目二、概要设计 1.存储结构 typedef struct{ int row,col;//行，列 datatype v;//非0数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行，n 列，t 非0数个数 … … 2.基本操作 ⑴istream& operator >>(istream& input,Matrix *A)//输入 ⑵ostream& operator <<(ostream& output,Matrix *A){//输出 ⑶Matrix operator ~(Matrix a,Matrix b)//转置 ⑷Matrix operator +(Matrix a,Matrix b)//加法 ⑸Matrix operator -(Matrix a,Matrix b)//减法 ⑹Matrix operator *(Matrix a,Matrix b)//乘法 ⑺Matrix operator !(Matrix a,Matrix b)//求逆三、详细设计（1）存储要点 position[col]=position[col-1]+num[col-1]; 三元组表(row ，col ，v) 稀疏矩阵（（行数m ，列数n ，非零元素个数t ），三元组，...，三元组） 1 2 3 4 max-1

矩阵数值算法

计算实习报告一实习目的（1）了解矩阵特征值与相应特征向量求解的意义，理解幂法和反幂法的原理，能编制此算法的程序，并能求解实际问题。（2）通过对比非线性方程的迭代法，理解线性方程组迭代解法的原理，学会编写Jacobi 迭代法程序，并能求解中小型非线性方程组。初始点对收敛性质及收敛速度的影响。（3）理解 QR 法计算矩阵特征值与特征向量的原理，能编制此算法的程序，并用于实际问题的求解。二问题定义及题目分析 1. 分别用幂法和幂法加速技术求矩阵 2.5 2.5 3.00.50.0 5.0 2.0 2.00.50.5 4.0 2.52.5 2.5 5.0 3.5-?? ?- ?= ?-- ?--?? A 的主特征值和特征向量． 2. 对于实对称矩阵n n ?∈A R ，用Jacobi 方法编写其程序，并用所编程序求下列矩阵的全部特征值． 1515 4 1141144114114?-?? ?-- ? ?- ?= ? ?- ?-- ? ?-??A 3. 对于实矩阵n n ?∈A R ，用QR 方法编写其程序，并用所编程序求下列矩阵的全部特征值: 111 21 113,4,5,62311111n n n n n n ? ???? ?????==+? ????? ??+??A 三概要设计（1）幂法用于求按模最大的特征值及其对应的特征向量的一种数值算法，

它要求矩阵 A 的特征值有如下关系： 12n ...λλλ>≥≥ ，对于相应的特征向量。其算法如下： Step 0：初始化数据0,, 1.A z k = Step 1：计算1k k y A z +=。 Step 2：令 k k m y ∞=。 Step 3：令 k k k z y m = ；如果1k k m m +≈或1k k z z +≈，则 goto Step 4；否则， k = k + 1 ，goto Step 1。 Step 4：输出结果算法说明与要求输入参数为实数矩阵、初始向量、误差限与最大迭代次数。输出参数为特征值及相对应的特征向量。注意初始向量不能为“0”向量。（2）迭代法的原理如果能将方程 Ax =b 改写成等价形式：x=Bx+f 。如果B 满足：ρ(B )<1，则对于任意初始向量 x (0) ，由迭代 x ( k + 1) = Bx (k ) + f 产生的序列均收敛到方程组的精确解。迭代法中两种最有名的迭代法就是Jacobi 迭代法，它的迭代矩阵 B 为： 1()J D L U -=-+,1 f D b -= 其中，D 为系数矩阵 A 的对角元所组成对角矩阵，L 为系数矩阵 A 的对角元下方所有元素所组成的下三角矩阵，U 为系数矩阵 A 的对角元上方所有元素所组成的上三角矩阵。算法如下： Step 0：初始化数据 00,,,,k A b x δ=和ε。 Step 1：计算D,L,U,J 或G, 得到迭代矩阵B. Step 2：:1k k =+ 0x B x f * =+ 0x x = 如果0x x δ-<或()f x ε≤，goto Step 3?否则 goto Step ２。 Step 3：输出结果。程序说明与要求

稀疏矩阵的运算课程设计

数据结构课程设计说明书题目: 稀疏矩阵的运算院系：计算机科学与工程学院专业班级：计算机10-**班学号： 201030**** 学生姓名： ****** 指导教师： ****** 2011年 12 月 28 日

安徽理工大学课程设计（论文）任务书计算机科学与工程学院 2011年 11 月 8 日

安徽理工大学课程设计（论文）成绩评定表

目录 1 问题描述 (1) 2 需求分析 (1) 3 总体设计 (2) 3.1 Matrix结构的定义 (2) 3.2 系统流程图 (3) 4 详细设计 (4) 4.1 “菜单”界面 (4) 4.2 建立矩阵 (4) 4.3 显示矩阵 (6) 4.4 矩阵的转置 (7) 4.5 矩阵的加法运算 (8) 4.6 矩阵的减法运算 (9) 4.7 矩阵的乘法运算 (9) 5 程序运行 (11) 5.1 输入矩阵 (11) 5.2 矩阵转置 (11) 5.3 矩阵加法 (12) 5.4 矩阵减法 (12) 5.5 矩阵乘法 (12) 5.6 退出及错误提示 (13) 6 总结 (13) 参考文献 (14)

1 问题描述 (1)题目内容：设计稀疏矩阵运算系统实现两个稀疏矩阵的加法、减法、乘法以及转置操作。 (2)基本要求： ①存储结构选择三元组存储方式； ②实现一个稀疏矩阵的转置运算； ③实现两个稀疏矩阵的加法运算； ④实现两个稀疏矩阵的减法运算； ⑤实现两个稀疏矩阵的乘法运算。 (3)设计目的：通过本次课程设计，了解稀疏矩阵的一些基本运算操作，并通过相关的程序代码实现。 2 需求分析经过本次的课程设计，我认为稀疏矩阵运算系统主要实现的功能如下：(1)建立矩阵：只有先建立了矩阵，才能够对矩阵进行运算操作，包括建立矩阵 A和矩阵B； (2)转置运算操作：对矩阵A或者矩阵B进行转置运算，输出相应的转置矩阵； (3)四则运算操作：该步骤由两个矩阵同时参与，对其进行加法运算(A+B)、减法运算(A-B)以及乘法运算(A*B和B*A)； (4)退出：当做完矩阵的运算操作之后，就可以点击它退出该界面。在这次设计中用到了一些变量和函数，例如：void Display(Matrix M)；int Max(int i,int j)；Matrix Zero(Matrix M)等，下面会做进一步详细的介绍。

矩阵的秩的相关不等式的归纳小结

矩阵的秩的相关不等式的归纳小结 -标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII

矩阵的秩的相关不等式的归纳小结林松（莆田学院数学系，福建，莆田）摘要：利用分块矩阵，证明一些矩阵的秩的相关不等式，观察矩阵在运算后秩的变化，归纳出常见的有关矩阵的秩的不等式，由此引出等式成立的条件。关键词：矩阵的秩，矩阵的初等变换引言：矩阵的秩是指矩阵中行（或列）向量组的秩，与之等价的说法通常是指矩阵中不为零的子式的最高阶数，是矩阵最重要的数字特征之一。利用分块矩阵，把子式看成元素，可将高阶矩阵的运算化为较低阶矩阵的运算，也为矩阵的秩的一些常见不等式的证明带来了方便。本文将讨论矩阵的秩的一些常见不等式，并由此引出一些秩的不等式等号成立的等价条件。一基本的定理 1 设A是数域P上n m ?矩阵，于是 ?矩阵，B是数域上m s 秩（AB）≤min [秩（A），秩（B）]，即乘积的秩不超过个因子的秩 2设A与B是m n ?矩阵，秩（A±B）≤秩（A）+秩（B）二常见的秩的不等式 1 设A与B为n阶方阵，证明若AB = 0，则 r(A) + r(B) ≤ n 证：设r(A) = r,r(B )= s,则由AB = 0，知，B的每一列向量都是以A为系数方阵的齐次线性方程组的解向量。当r = n时，由于该齐次方程组只要零解，故此时 B = 0，即此时r(A) = n，r(B) = 0,结论成立。当r〈 n 时，该齐次线性方程组的基础解系中含n-r个向量，

从而B 的列向量组的秩≤n-r,即r （B ）≤ n-r 所以 r(A) + r(B) ≤ n 2设A 为m n ?矩阵，B 为n s ?矩阵，证明不等式r(AB)≤r(A)+r(B)-n 证：设E 为n 阶单位矩阵， S E 为S 阶单位方阵，则由于 000S E B A AB A E E E B ??????= ? ? ?-?????? 而 0S E B E ?? ?-?? 可逆，故 r(A)+r(B) ≥ 秩 0A E B ?? ? ?? =秩 0A AB E ?? ???=秩 0 0AB E ?? ??? =r(AB)+r(E) =r(AB)+n 从而r(AB) ≥ r(A) + r(B) - n 3设A ，B 都是n 阶方阵，E 是n 阶单位方阵，证明秩（AB-E ）≤秩（A-E ）+秩（B-E ）证：因为0A E B E B E --?? ? -??00B E ?? ???00AB E B E -?? = ?-?? 故秩（AB-E ）≤秩00AB E B E -?? ?-??≤秩0A E B E B E --?? ?-?? =秩（A-E ）+秩（B-E ）因此秩（AB-E ）≤秩（A-E ）+秩（B-E ） 4 设A ，B ，C 依次为,,m n n s s t ???的矩阵，证明 r(ABC) ≥ r(AB) + r(BC) - r(B)