導言
線性代數(shù)是大學理工科學生的必修課。學過線性代數(shù)的同學一定對矩陣不陌生，因為線性代數(shù)就是一門關于矩陣的學科。
程序設計中有一種儲存數(shù)據(jù)的方式是二維數(shù)組，而二維數(shù)組本質(zhì)上就是矩陣。但是，假如我們想要用二維數(shù)組去儲存一個大規(guī)模的矩陣并進行運算的話，會造成很大的資源浪費。舉個例子，假如我們想要用二維數(shù)組去儲存一個20W*20W的單位矩陣，事實上其中只有20W個數(shù)是1，其他數(shù)字都是0。所以，我們或許可以利用一種“忽略矩陣中的0項”的方式，來實現(xiàn)對矩陣的壓縮儲存，這種儲存方式就叫做稀疏矩陣。對于大部分位置都是0，只有少部分位置有值的矩陣來說，使用稀疏矩陣可以讓矩陣的儲存密度大大提高。
我們可以使用一個二維單向鏈表來儲存稀疏矩陣——因為鏈表在插入方面具有極低的時間復雜度，可以保證一個稀疏矩陣在經(jīng)過各種運算后依然保持行與列間有序的組織。為了能夠?qū)崿F(xiàn)單向鏈表的刪除，我們需要指向每一個有值結(jié)點前一個結(jié)點的引用。為此，我們還需要在第一行設置一個空行結(jié)點，每一行的第一列設置一個空列結(jié)點。形象地說，這種組織方式如下圖所示：
使用鏈表的代價是尋址成本的提高，因此二維迭代器的封裝對于基于鏈表的稀疏矩陣也是必不可少的。此外，比起二維數(shù)組矩陣，在各項操作方面，稀疏矩陣更難做到高效。因此如何高效地進行稀疏矩陣的各項操作也是本文需要探討的話題。
本文中需要實現(xiàn)的稀疏矩陣基本操作如下：
- 增加與修改單個元素
- 從二維數(shù)組復制元素
- 矩陣復制
- 矩陣加減法
- 數(shù)乘
- 矩陣乘法
- 矩陣轉(zhuǎn)置
同時稀疏矩陣還有派生類稀疏方陣，它實現(xiàn)的基本操作如下：
- 求行最簡矩陣
- 求行列式的值
- 求逆矩陣
1.1行索引鏈表
基于鏈表的稀疏矩陣的基礎是行索引。因為我們定位一個矩陣中的元素，是先定位其行位置，再定位其列位置的。
因此矩陣包含了一個作為基準的行索引鏈表結(jié)點。這個結(jié)點包含一個值，代表行號；包含一個橫向指針指向一個列索引鏈表結(jié)點（在C#中就是對一個列索引鏈表結(jié)點的引用），也就是該行第一個有非0元素的列；包含一個縱向指針指向下一個有非0元素的行索引鏈表結(jié)點。
矩陣的基礎構(gòu)造與行索引鏈表結(jié)點如下所示：
namespace exp6lib
{
public class mat
{
private class rowNode
{
}
protected class lineNode
{
public int lineId;
public rowNode firstRow;
public lineNode nextLine;
public lineNode()
{
firstRow = new rowNode();
firstRow.rowId = -1;
}
}
private lineNode baseLine;
protected int rowCount;
protected int lineCount;
}
}
1.2列索引鏈表
當確定矩陣中元素所在的行時，再通過列索引鏈表確定元素所在的列，就可以將該元素定位了。因此，列索引鏈表中包含兩個值，一個表示自己的列號，一個表示由行索引和列索引確定的元素的值。此外，還包含一個指向和自己同行的下一個非0元素的引用。
protected class rowNode
{
public int rowId;
public double value;
public rowNode nextRow;
}
1.3二維迭代器
由于二維鏈表在定位元素時需要先在行索引鏈表中尋址，再在列索引鏈表中尋址，其時間復雜度為$o(n)$，因此在實現(xiàn)諸如矩陣遍歷等有序操作時必須依賴二維迭代器，否則會造將大量時間浪費在尋址上，其時間復雜度將是無法想象的。為矩陣維護一個包含一個行索引結(jié)點引用、一個列索引結(jié)點引用的對象，它將通過四個引用，分別指向一行、一列和該行的前一行、該行的前一列，并且通過所引用的結(jié)點內(nèi)部包含的、指向其他結(jié)點的引用來實現(xiàn)自身所指元素的移動。
迭代器在初始化或者行復位時需要將指向前一行的引用放置到矩陣結(jié)構(gòu)的“第0行”上，將指向當前行的引用放置到第一行。同理，每移動到下一行或者進行列復位，都要把指向前一列的引用放置到該行的“第0列”上，將指向當前列的引用放置到第一列。
迭代器實現(xiàn)了五個方法，分別是移動到下一列、移動到下一行并指向該行第一列、移動到該行第一列、在當前指向行和前一行之間插入行、在當前指向列和前一列之間增加列。此外，在大類中還實現(xiàn)了一個私有方法reLine，用來將迭代器恢復至整個稀疏矩陣第一行。在大類中聲明一個迭代器對象，用來方便省時地訪問其中的元素。
protected class iterator
{
public rowNode row;
public lineNode line;
public rowNode prerow;
public lineNode preline;
public void nextRow()
{
prerow = row;
row = row.nextRow;
}
public void nextLine()
{
preline = line;
line = line.nextLine;
if (line != null)
{
prerow = line.firstRow;
row = line.firstRow.nextRow;
}
}
public void reRow()
{
row = line.firstRow.nextRow;
prerow = line.firstRow;
}
public void addLine(int lineId)
{
lineNode newLine = new lineNode();
newLine.lineId = lineId;
newLine.nextLine = preline.nextLine;
preline.nextLine = newLine;
line = newLine;
prerow = newLine.firstRow;
row = null;
}
public void addRow(int rowId, double value)
{
rowNode newRow = new rowNode();
newRow.rowId = rowId;
newRow.nextRow = prerow.nextRow;
prerow.nextRow = newRow;
newRow.value = value;
row = newRow;
}
}
protected iterator it;
protected void reLine()
{
it.preline = baseLine;
it.line = baseLine.nextLine;
if (it.line != null)
{
it.prerow = it.line.firstRow;
it.row = it.line.firstRow.nextRow;
}
else
{
it.prerow = null;
it.row = null;
}
}
1.4 單個元素的操作
利用迭代器指向矩陣中的元素，可以單獨設置這個元素的內(nèi)容。而如果要求設置一個不超出矩陣大小，但原本不存在（也就是為0）的位置的元素，就需要在二維鏈表中插入行或列。這一判斷需要依靠迭代器來作出。比如，若迭代器判定其指向位置的前一行小于目標行、而當前行大于目標行，就要在當前位置前插入目標行。同理，如果把一個原本不為0的位置的元素設為0，就要刪除當前列，而列為空時，則要刪除當前行。
public void set(int line, int row, double value)
{
if (line < 0 || row < 0 ||line>=lineCount||row>=rowCount)
return;
while (true)
{
if (it.line == null)
{
it.addLine(line);
break;
}
if (it.line.lineId == line)
break;
if (line<it.line.lineId&&line>it.preline.lineId)
{
it.nextLine();
it.addLine(line);
break;
}
if (line <= it.preline.lineId)
{
reLine();
continue;
}
it.nextLine();
}
while (true)
{
if (it.row == null)
{
if (value == 0)
break;
it.addRow(row, value);
break;
}
if (it.row.rowId == row)
{
it.row.value = value;
if (it.row.value == 0)
{
it.row = it.row.nextRow;
it.prerow.nextRow = it.row;
if (it.line.firstRow.nextRow == null)
{
it.line = it.line.nextLine;
it.preline.nextLine = it.line;
it.row = it.line.firstRow.nextRow;
it.prerow.nextRow = it.line.firstRow;
}
}
break;
}
if (row < it.row.rowId && row > it.prerow.rowId)
{
if (value == 0)
break;
it.addRow(row, value);
break;
}
if (row <= it.prerow.rowId)
{
it.reRow();
continue;
}
it.nextRow();
}
}
而單個元素的加減和乘除本質(zhì)也是相同的。記住要分成三種情況考慮需要實現(xiàn)的操作：
- 對已有元素操作
- 把為0的元素變成非0
- 把非0的元素變成0
protected void add(int line, int row, double value)
{
if (line < 0 || row < 0 || line >= lineCount || row >= rowCount)
return;
while (true)
{
if (line <= it.preline.lineId)
{
reLine();
continue;
}
if (it.line == null)
{
it.addLine(line);
break;
}
if (it.line.lineId == line)
break;
if (line < it.row.rowId && line > it.preline.lineId)
{
it.nextLine();
it.addLine(line);
break;
}
it.nextLine();
}
while (true)
{
if (row <= it.prerow.rowId)
{
it.reRow();
continue;
}
if (it.row == null)
{
if (value == 0)
break;
it.addRow(row, value);
break;
}
if (it.row.rowId == row)
{
it.row.value += value;
if (it.row.value == 0)
{
it.row = it.row.nextRow;
it.prerow.nextRow = it.row;
if (it.line.firstRow.nextRow == null)
{
it.line = it.line.nextLine;
it.preline.nextLine = it.line;
it.row = it.line.firstRow.nextRow;
it.prerow.nextRow = it.line.firstRow;
}
}
break;
}
if (row < it.row.rowId && row > it.prerow.rowId)
{
if (value == 0)
break;
it.addRow(row, value);
break;
}
it.nextRow();
}
}
protected void times(int line, int row, double value)
{
if (line < 0 || row < 0 || line >= lineCount || row >= rowCount)
return;
while (true)
{
if (line <= it.preline.lineId)
{
reLine();
continue;
}
if (it.line == null)
return;
if (it.line.lineId == line)
break;
if (line < it.row.rowId && line > it.preline.lineId)
return;
it.nextLine();
}
while (true)
{
if (row <= it.prerow.rowId)
{
it.reRow();
continue;
}
if (it.row == null)
return;
if (it.row.rowId == row)
{
it.row.value *= value;
if (it.row.value == 0)
{
it.row = it.row.nextRow;
it.prerow.nextRow = it.row;
if (it.line.firstRow.nextRow == null)
{
it.line = it.line.nextLine;
it.preline.nextLine = it.line;
it.row = it.line.firstRow.nextRow;
it.prerow.nextRow = it.line.firstRow;
}
}
return;
}
if (row < it.row.rowId && row > it.prerow.rowId)
return;
it.nextRow();
}
}
而獲取單個元素使用的方法也運用同樣的思想，只不過在獲取不到元素時返回元素類型的默認值。
public double get(int line, int row)
{
if (line < 0 || row < 0 || line >= lineCount || row >= rowCount)
return 0;
while (true)
{
if (it.line == null)
return 0;
if (it.line.lineId == line)
break;
if (line < it.line.lineId && line > it.preline.lineId)
return 0;
if (line <= it.preline.lineId)
{
reLine();
continue;
}
it.nextLine();
}
while (true)
{
if (it.row == null)
return 0;
if (it.row.rowId == row)
return it.row.value;
if (row < it.row.rowId && row > it.prerow.rowId)
return 0;
if (row <= it.prerow.rowId)
{
it.reRow();
continue;
}
it.nextRow();
}
}
2.1 稀疏矩陣的初始化
默認初始化時，用戶需要指定該矩陣的行數(shù)和列數(shù)。此外，將迭代器置于第一行第一列，雖然此時第一行第一列沒有聲明，但是要記得我們矩陣的鏈表結(jié)構(gòu)中存在一個空的“第0行”。將迭代器的preline引用指向該“第0行”，其他引用則設為null。
public mat(int line,int row)
{
baseLine = new lineNode();
baseLine.lineId = -1;
it = new iterator();
it.preline = baseLine;
it.line = null;
it.row = null;
it.prerow = null;
lineCount = line;
rowCount = row;
}
使用其他mat初始化時，稀疏矩陣會調(diào)用目標矩陣中的迭代器和自身的迭代器來實現(xiàn)矩陣遍歷。遍歷只需要不斷調(diào)用nextRow方法，在指向的列為空時調(diào)用nextLine方法，直到指向的行為空為止即可。
在這里強調(diào)一下reLine的作用，它是迭代器的復位方法，也可以視為聲明一個指向第一行第一列的迭代器。如果不進行reLine的話，假如目標矩陣中的迭代器已經(jīng)指向了一個很后面的元素，那么利用迭代器nextRow和nextLine方法進行的遍歷就是不成立的。
public mat(mat tar)
{
baseLine = new lineNode();
baseLine.lineId = -1;
it = new iterator();
it.preline = baseLine;
it.line = null;
it.row = null;
it.prerow = null;
tar.reLine();
lineCount = tar.lineCount;
rowCount = tar.rowCount;
while (tar.it.line!=null)
{
while (tar.it.row != null)
{
set(tar.it.line.lineId, tar.it.row.rowId, tar.it.row.value);
tar.it.nextRow();
}
tar.it.nextLine();
}
}
使用二維數(shù)組初始化通過遍歷二維數(shù)組的方式，將二維數(shù)組中的數(shù)據(jù)一個一個set到矩陣當中。
public mat(int[][] tar)
{
baseLine = new lineNode();
baseLine.lineId = -1;
it = new iterator();
it.preline = baseLine;
it.line = null;
it.row = null;
it.prerow = null;
for (int i = 0; i < tar.Length; i++)
for (int j = 0; j < tar[i].Length; j++)
set(i, j, tar[i][j]);
}
2.2 矩陣加減和數(shù)乘
矩陣的加減用第一個矩陣初始化一個新矩陣，同時用新矩陣和第二個矩陣的迭代器遍歷兩個矩陣，再在新矩陣的每個位置調(diào)用加方法，加上第二個矩陣對應位置的元素值（或其相反數(shù)），最后把新矩陣返回。
static public mat operator+(mat obj,mat tar)
{
if (tar.rowCount != obj.rowCount || tar.lineCount != obj.lineCount)
return new mat(0, 0);
mat result=new mat(obj);
tar.reLine();
while (tar.it.line != null)
{
while (tar.it.row != null)
{
result.add(tar.it.line.lineId, tar.it.row.rowId, tar.it.row.value);
tar.it.nextRow();
}
tar.it.nextLine();
}
return result;
}
static public mat operator -(mat obj, mat tar)
{
if (tar.rowCount != obj.rowCount || tar.lineCount != obj.lineCount)
return new mat(0, 0);
mat result = new mat(obj);
tar.reLine();
while (tar.it.line != null)
{
while (tar.it.row != null)
{
result.add(tar.it.line.lineId, tar.it.row.rowId, -tar.it.row.value);
tar.it.nextRow();
}
tar.it.nextLine();
}
return result;
}
矩陣的數(shù)乘用第一個矩陣初始化一個新矩陣，同時用新矩陣的迭代器遍歷新矩陣，再在新矩陣的每個位置調(diào)用乘方法，乘上目標值，最后把新矩陣返回。
static public mat operator *(mat obj,double value)
{
mat result = new mat(obj);
result.reLine();
while (result.it.line!= null)
{
while (result.it.row != null)
{
result.times(result.it.line.lineId, result.it.row.rowId, value);
result.it.nextRow();
}
result.it.nextLine();
}
return result;
}
static public mat operator *(double value,mat obj)
{
mat result = new mat(obj);
result.reLine();
while (result.it.line != null)
{
while (result.it.row != null)
{
result.times(result.it.line.lineId, result.it.row.rowId, value);
result.it.nextRow();
}
result.it.nextLine();
}
return result;
}
2.3 矩陣乘法
依然通過迭代器來選取兩個矩陣里的元素，通過矩陣乘法的特殊運算順序來運算，將結(jié)果放進新矩陣中。返回的矩陣是通過new創(chuàng)建的新矩陣，因此不會對原來兩個矩陣產(chǎn)生影響。
static public mat operator *(mat tar,mat obj)
{
mat result = new mat(tar.lineCount,obj.rowCount);
tar.reLine();
obj.reLine();
while (tar.it.line!=null)
{
for (int i = 0; i < obj.rowCount; i++)
{
double sum = 0;
while (tar.it.row != null)
{
sum += tar.it.row.value * obj.get(tar.it.row.rowId, i);
tar.it.nextRow();
}
result.set(tar.it.line.lineId, i,sum);
tar.it.reRow();
}
tar.it.nextLine();
}
return result;
}
2.4 矩陣的轉(zhuǎn)置
矩陣轉(zhuǎn)置創(chuàng)建一個新的矩陣，其行數(shù)為原矩陣的列數(shù)，列數(shù)為原矩陣的行數(shù)，并將原矩陣中的元素所在行列對換后放進新矩陣中。
public mat turn()
{
mat result = new mat(rowCount,lineCount);
reLine();
while (it.line!= null)
{
while (it.row!= null)
{
result.set(it.row.rowId, it.line.lineId,it.row.value);
it.nextRow();
}
it.nextLine();
}
return result;
}
2.5 打印矩陣
public void print()
{
reLine();
int lineNum = 0;
while(it.line!=null)
{
int rowNum = 0;
while(it.row!=null)
{
for (; rowNum < it.row.rowId; rowNum++)
Console.Write("0\t");
rowNum++;
Console.Write(it.row.value);
Console.Write("\t");
it.nextRow();
}
for(;rowNum<rowCount;rowNum++)
Console.Write("0\t");
Console.Write("\n");
lineNum++;
it.nextLine();
}
for(;lineNum<lineCount;lineNum++)
{
for (int rowNum=0; rowNum < rowCount; rowNum++)
Console.Write("0\t");
Console.Write("\n");
}
}
3.1 稀疏方陣的初始化
基本上就是從矩陣當中繼承了初始化方法。注意構(gòu)造函數(shù)是要繼承自base(父類構(gòu)造函數(shù)參數(shù))的。以及行和列的數(shù)目應該相同。
public class smat : mat
{
public smat(int n):base(n,n){}
public smat(smat tar) : base(tar){}
}
3.2 稀疏方陣的基本運算
都是對稀疏矩陣基本運算的重寫。由于行列數(shù)目相同，實際實現(xiàn)會容易得多。
static public smat operator +(smat obj, smat tar)
{
if (tar.rowCount != obj.rowCount || tar.lineCount != obj.lineCount)
return new smat(0);
smat result = new smat(obj);
tar.reLine();
while (tar.it.line != null)
{
while (tar.it.row != null)
{
result.add(tar.it.line.lineId, tar.it.row.rowId, tar.it.row.value);
tar.it.nextRow();
}
tar.it.nextLine();
}
return result;
}
static public smat operator -(smat obj, smat tar)
{
if (tar.rowCount != obj.rowCount || tar.lineCount != obj.lineCount)
return new smat(0);
smat result = new smat(obj);
tar.reLine();
while (tar.it.line != null)
{
while (tar.it.row != null)
{
result.add(tar.it.line.lineId, tar.it.row.rowId, -tar.it.row.value);
tar.it.nextRow();
}
tar.it.nextLine();
}
return result;
}
static public smat operator *(smat obj, double value)
{
smat result = new smat(obj);
result.reLine();
while (result.it.line != null)
{
while (result.it.row != null)
{
result.times(result.it.line.lineId, result.it.row.rowId, value);
result.it.nextRow();
}
result.it.nextLine();
}
return result;
}
static public smat operator *(double value, smat obj)
{
smat result = new smat(obj);
result.reLine();
while (result.it.line != null)
{
while (result.it.row != null)
{
result.times(result.it.line.lineId, result.it.row.rowId, value);
result.it.nextRow();
}
result.it.nextLine();
}
return result;
}
static public smat operator *(smat tar, smat obj)
{
smat result = new smat(tar.lineCount);
tar.reLine();
obj.reLine();
while (tar.it.line != null)
{
for (int i = 0; i < obj.rowCount; i++)
{
double sum = 0;
while (tar.it.row != null)
{
sum += tar.it.row.value * obj.get(tar.it.row.rowId, i);
tar.it.nextRow();
}
result.set(tar.it.line.lineId, i,sum);
tar.it.reRow();
}
tar.it.nextLine();
}
return result;
}
new public smat turn()
{
smat result = new smat(rowCount);
reLine();
while (it.line != null)
{
while (it.row != null)
{
result.set(it.row.rowId, it.line.lineId, it.row.value);
it.nextRow();
}
it.nextLine();
}
return result;
}
3.3 求行最簡矩陣
求行最簡矩陣的目的就是把原矩陣通過初等行變換化為相抵的上三角矩陣。其具體做法是：
- 從原矩陣中尋找第一個非0元素最靠左（行坐標最?。┑囊恍?/li>
- 從原矩陣中尋找第一個非0元素次靠左（行坐標次?。┑囊恍?/li>
- 如果1、2步找出的行的第一個非0元素行坐標一致，說明需要通過高斯消元法相消。將第一行第一個非0元素設為a，第二行第一個非0元素設為b，第二行每個位置減去第一行每個位置對應元素乘以b/a后的結(jié)果，就可以把第二行第一個非0元素變成0，然后重新開始第1步
- 如果1、2步找出的行的第一個非0元素行坐標不一致，則將第1步找出的行從原矩陣中刪除，放入新矩陣，然后重新開始第1步
- 如果找不到行，說明原矩陣中所有行以及被移入新矩陣，循環(huán)結(jié)束
public smat tri()
{
smat tmp = new smat(this);
smat result = new smat(lineCount);
lineNode maxline = null;
lineNode max2line = null;
lineNode premaxline = null;
lineNode premax2line = null;
tmp.reLine();
int i = 0;
while (tmp.it.line!= null)
{
while (tmp.it.line!= null)
{
if (maxline == null || tmp.it.row.rowId < maxline.firstRow.nextRow.rowId)
{
max2line = maxline;
premax2line = premaxline;
maxline = tmp.it.line;
premaxline = tmp.it.preline;
}
else if ((max2line == null || tmp.it.row.rowId < max2line.firstRow.nextRow.rowId) && tmp.it.line.lineId != maxline.lineId)
{
max2line = tmp.it.line;
premax2line = tmp.it.preline;
}
tmp.it.nextLine();
}
if (max2line!=null&&maxline.firstRow.nextRow.rowId == max2line.firstRow.nextRow.rowId)
{
double basis = max2line.firstRow.nextRow.value / maxline.firstRow.nextRow.value;
rowNode rowit = maxline.firstRow.nextRow;
while (rowit != null)
{
tmp.add(max2line.lineId, rowit.rowId, -(rowit.value * basis));
rowit = rowit.nextRow;
}
}
else
{
premaxline.nextLine = maxline.nextLine;
maxline.nextLine = null;
if (premax2line == maxline)
premax2line = premaxline;
rowNode j = maxline.firstRow.nextRow;
while(j!=null)
{
result.set(i, j.rowId, j.value);
j = j.nextRow;
}
i++;
result.it.nextLine();
maxline = null;
premaxline = null;
max2line = null;
premax2line = null;
}
tmp.reLine();
}
return result;
}
3.4 求行列式的值
求完行最簡矩陣之后，求行列式的值也變成了非常簡單的工作。只需把對角線上所有元素相乘即可。
public double det()
{
smat result = tri();
int i = 0;
double sum = 1;
result.reLine();
while (result.it.line != null)
{
if (result.it.row.rowId != i)
return 0;
i++;
sum *= result.it.row.value;
result.it.nextLine();
}
return sum;
}
3.5 求逆矩陣
逆矩陣同樣通過初等行變換法來解出，方法是把一個行列數(shù)與原矩陣相同的單位矩陣進行和原矩陣同步的行變換。當把原矩陣變成單位矩陣時，單位矩陣也變成了原矩陣的逆矩陣。
- 從原矩陣中尋找第一個非0元素最靠左（行坐標最?。┑囊恍?，并選擇單位矩陣中行id對應的一行
- 從原矩陣中尋找第一個非0元素次靠左（行坐標次?。┑囊恍?，并選擇單位矩陣中行id對應的一行
- 如果1、2步找出的行的第一個非0元素行坐標一致，說明需要通過高斯消元法相消。將第一行第一個非0元素設為a，第二行第一個非0元素設為b，第二行每個位置減去第一行每個位置對應元素乘以b/a后的結(jié)果，就可以把第二行第一個非0元素變成0，單位矩陣重復同樣的內(nèi)容，然后重新開始第1步
- 如果1、2步找出的行的第一個非0元素行坐標不一致，則將第1步找出的行從原矩陣中刪除，放入新矩陣，然后重新開始第1步，單位矩陣重復同樣的內(nèi)容
- 如果找不到行，說明原矩陣中所有行以及被移入新矩陣，進入第6步
- 從最后一行開始，將原矩陣對應新矩陣每一行乘以第一個非0元素的倒數(shù)，再用行id比當前行更大的每一行的第一個元素來和當前行每一個非0元素相消，同時單位矩陣對應新矩陣也作同步變換，即可得到逆矩陣
public smat re()
{
smat tmp = new smat(this);
smat tmp2 = new smat(lineCount);
smat resultTmp = new smat(lineCount);
smat result = new smat(lineCount);
for (int l = 0; l < lineCount; l++)
resultTmp.set(l, l, 1);
tmp.reLine();
resultTmp.reLine();
lineNode maxline = null;
lineNode max2line = null;
lineNode premaxline = null;
lineNode premax2line = null;
lineNode resMaxline = null;
lineNode resMax2line = null;
lineNode preresMaxline = null;
lineNode preresMax2line = null;
int i = 0;
while (tmp.it.line != null)
{
while (tmp.it.line != null)
{
if (maxline == null || tmp.it.row.rowId < maxline.firstRow.nextRow.rowId)
{
max2line = maxline;
premax2line = premaxline;
resMax2line = resMaxline;
preresMax2line = preresMaxline;
maxline = tmp.it.line;
premaxline = tmp.it.preline;
resMaxline = resultTmp.it.line;
preresMaxline = resultTmp.it.preline;
}
else if ((max2line == null || tmp.it.row.rowId < max2line.firstRow.nextRow.rowId) && tmp.it.line.lineId != maxline.lineId)
{
max2line = tmp.it.line;
premax2line = tmp.it.preline;
resMax2line = resultTmp.it.line;
preresMax2line = resultTmp.it.preline;
}
tmp.it.nextLine();
resultTmp.it.nextLine();
}
if (max2line != null && maxline.firstRow.nextRow.rowId == max2line.firstRow.nextRow.rowId)
{
double basis = max2line.firstRow.nextRow.value / maxline.firstRow.nextRow.value;
rowNode rowit = maxline.firstRow.nextRow;
rowNode resRowit = resMaxline.firstRow.nextRow;
while (rowit != null)
{
add(max2line.lineId, rowit.rowId, -(rowit.value * basis));
add(resMax2line.lineId, resRowit.rowId, -(resRowit.value * basis));
rowit = rowit.nextRow;
resRowit = resRowit.nextRow;
}
}
else
{
premaxline.nextLine = maxline.nextLine;
preresMaxline.nextLine = resMaxline.nextLine;
maxline.nextLine = null;
resMaxline.nextLine = null;
if (premax2line == maxline)
{
premax2line = premaxline;
preresMax2line = preresMaxline;
}
rowNode j = maxline.firstRow.nextRow;
rowNode k = resMaxline.firstRow.nextRow;
while (j != null)
{
tmp2.set(i, j.rowId, j.value/ maxline.firstRow.nextRow.value);
j = j.nextRow;
}
while (k != null)
{
result.set(i, k.rowId, k.value/ maxline.firstRow.nextRow.value);
k = k.nextRow;
}
i++;
tmp2.it.nextLine();
result.it.nextLine();
maxline = null;
resMaxline = null;
premaxline = null;
preresMaxline = null;
max2line = null;
resMax2line = null;
premax2line = null;
preresMax2line = null;
}
tmp.reLine();
resultTmp.reLine();
}
if (i != lineCount)
return new smat(0);
tmp2.reLine();
result.reLine();
for (int l = lineCount - 1; l >= 0; l--)
for (int j = lineCount - 1; j > l; j--)
{
for(int k=j;k<lineCount;k++)
result.add(l, k, -result.get(j, k) * tmp2.get(l, j));
tmp2.it.reRow();
}
return result;
}
