矩阵转置算法

1. 矩阵的转置运算

在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合[1]，最早来自于方程组的系数及常数所构成的方阵。这一概念由19世纪英国数学家凯利首先提出。
矩阵是高等代数学中的常见工具，也常见于统计分析等应用数学学科中。[2]在物理学中，矩阵于电路学、力学、光学和量子物理中都有应用；计算机科学中，三维动画制作也需要用到矩阵。 矩阵的运算是数值分析领域的重要问题。将矩阵分解为简单矩阵的组合可以在理论和实际应用上简化矩阵的运算。对一些应用广泛而形式特殊的矩阵，例如稀疏矩阵和准对角矩阵，有特定的快速运算算法。关于矩阵相关理论的发展和应用，请参考《矩阵理论》。在天体物理、量子力学等领域，也会出现无穷维的矩阵，是矩阵的一种推广。
数值分析的主要分支致力于开发矩阵计算的有效算法，这是一个已持续几个世纪以来的课题，是一个不断扩大的研究领域。 矩阵分解方法简化了理论和实际的计算。 针对特定矩阵结构（如稀疏矩阵和近角矩阵）定制的算法在有限元方法和其他计算中加快了计算。 无限矩阵发生在行星理论和原子理论中。 无限矩阵的一个简单例子是代表一个函数的泰勒级数的导数算子的矩阵[3]
中文名
矩阵
外文名
Matrix
别称
矩阵式、纵横阵
表达式
Amn
提出者
凯利
快速
导航
定义基本运算乘法行列式特征值与特征向量矩阵的迹正定性矩阵的分解特殊类别范数应用
历史
矩阵的研究历史悠久，拉丁方阵和幻方在史前年代已有人研究。
在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合[1]，最早来自于方程组的系数及常数所构成的方阵。这一概念由19世纪英国数学家凯利首先提出。作为解决线性方程的工具，矩阵也有不短的历史。成书最早在东汉前期的《九章算术》中，用分离系数法表示线性方程组，得到了其增广矩阵。在消元过程中，使用的把某行乘以某一非零实数、从某行中减去另一行等运算技巧，相当于矩阵的初等变换。但那时并没有现今理解的矩阵概念，虽然它与现有的矩阵形式上相同，但在当时只是作为线性方程组的标准表示与处理方式。
阿瑟·凯利，矩阵论奠基人
矩阵正式作为数学中的研究对象出现，则是在行列式的研究发展起来后。逻辑上，矩阵的概念先于行列式，但在实际的历史上则恰好相反。日本数学家关孝和（1683年）与微积分的发现者之一戈特弗里德·威廉·莱布尼茨（1693年）近乎同时地独立建立了行列式论。其后行列式作为解线性方程组的工具逐步发展。1750年，加布里尔·克拉默发现了克莱姆法则[5]。
矩阵的概念在19世纪逐渐形成。1800年代，高斯和威廉·若尔当建立了高斯—若尔当消去法。1844年，德国数学家费迪南·艾森斯坦（F.Eisenstein）讨论了“变换”（矩阵）及其乘积。1850年，英国数学家詹姆斯·约瑟夫·西尔维斯特（James Joseph Sylvester）首先使用矩阵一词。

2. 稀疏矩阵的转置运算用C语言

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define MAXSIZE 12500 //非零元个数最大值
typedef int Status;
typedef int ElemType;
typedef struct
{
int i,j; //非零元的行下标和列下标
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; //非零元三元组表，data[0]未用
int mu,nu,tu; //矩阵的行数，列数，非零元个数
}TSMatrix;

/*Status TransposeSMatrix(TSMatrix M,TSMatrix *T)
{
//求稀疏矩阵M的转置矩阵T的一般算法
int q,col,p;
T->mu=M.nu;
T->nu=M.mu;
T->tu=M.tu;
if(M.tu)
{
q=1;
for(col=1;col<=M.nu;col++)
for(p=1;p<=M.tu;p++)
if(M.data[p].j==col)
{
T->data[q].i=M.data[p].j;
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e;
q++;
}
}
return OK;
}//TransposeSMatrix*/

Status FastTransposeSMatrix(TSMatrix M,TSMatrix *T)
{
//采用三元组顺序存储表示，求稀疏矩阵M的转置矩阵的快速转置算法
int col,t,q,p;
int num[50]; //num[col]表示矩阵M中第col列中非零元个数
int cpot[50]; //cpot[col]表示M中第col列的第一个非零元在T.data中恰当位置
T->mu=M.nu;
T->nu=M.mu;
T->tu=M.tu;
if(M.tu)
{
for(col=1;col<=M.nu;col++)
num[col]=0;
for(t=1;t<=M.tu;t++)
num[M.data[t].j]++; //求M中每一列含非零元个数

cpot[1]=1;
for(col=2;col<=M.nu;col++)
cpot[col]=cpot[col-1]+num[col-1];
//求第col列中第一个非零元在T.data中的序号

for(p=1;p<=M.tu;p++)
{
col=M.data[p].j;
q=cpot[col];
T->data[q].i=M.data[p].j;
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e;
cpot[col]++;
}

}
return OK;
}//FastTransposeSMatrix

int main()
{
int i;
TSMatrix M,T;
system("color 3e");

printf("请输入矩阵的非零元个数,矩阵的行数和列数:");
scanf("%d%d%d",&M.tu,&M.mu,&M.nu);

for(i=1;i<=M.tu;i++)
{
printf("请输入第%d个非零元的行坐标，列坐标，值:\n",i);
scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);
}
printf("原矩阵为:\n");
printf(" i j e\n");
for(i=1;i<=M.tu;i++)
printf("%4d%4d%4d\n",M.data[i].i,M.data[i].j,M.data[i].e);

// TransposeSMatrix(M,&T);
FastTransposeSMatrix(M,&T);

printf("转置矩阵为:\n");
printf(" i j e\n");
for(i=1;i<=T.tu;i++)
printf("%4d%4d%4d\n",T.data[i].i,T.data[i].j,T.data[i].e);

return 0;

}

/*
请输入矩阵的非零元个数,矩阵的行数和列数:8 6 6
请输入第1个非零元的行坐标，列坐标，值:
1 2 12
请输入第2个非零元的行坐标，列坐标，值:
1 3 9
请输入第3个非零元的行坐标，列坐标，值:
3 1 -3
请输入第4个非零元的行坐标，列坐标，值:
3 6 14
请输入第5个非零元的行坐标，列坐标，值:
4 3 24
请输入第6个非零元的行坐标，列坐标，值:
5 2 18
请输入第7个非零元的行坐标，列坐标，值:
6 1 15
请输入第8个非零元的行坐标，列坐标，值:
6 4 -7
原矩阵为:
i j e
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
转置矩阵为:
i j e
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
Press any key to continue
*/

中间采用了两种转置算法，VC6下调试皆可通过