矩陣轉置演算法

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下調試皆可通過