【演算法】使用二維陣列實作矩陣運算（使用 Java）

程式中的二維陣列結構與數學上的矩陣十分雷同。矩陣的應用包括數值分析、深度學習、圖論等。由於筆者不是數學專業，也未涉及相關應用領域，因此不多加介紹。

本文會利用二維陣列模擬出矩陣的加法、乘法運算，以及轉置矩陣。最後再透過三項式（3-tuple）表示法，來壓縮稀疏矩陣，以節省記憶體空間。

一、矩陣的結構

下圖是一些矩陣，它的寫法是由中括號將多個數字包在一起，且每個位置都有數字，不會是空的。

矩陣有「列」（row）跟「行」（column）。其他地區的用語可能不同，在本文，橫的叫列，直的叫行。所以上圖的矩陣一是2列2行；矩陣二是3列4行。下面我們設計一個「Matrix」的類別，用來儲存二維陣列，並實作矩陣的運算方法。

public class Matrix {
    private int[][] data;

    public Matrix(int[][] data) {
        this.data = data;
    }

    public void add(Matrix matrix) {
        // TODO
    }

    public void multiply(Matrix matrix) {
        // TODO
    }

    public void transpose() {
        // TODO
    }

    public int[][] to3TupleTable() {
        // TODO
        return null;
    }

    public static Matrix restoreFrom3TupleTable(int[][] table) {
        // TODO
        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int row = 0; row < data.length; row++) {
            for (int column = 0; column < data[row].length; column++) {
                sb.append(data[row][column]).append("\t");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

以下是這些方法的用途

add：與另一個矩陣相加。
multiply：與另一個矩陣相乘。
transpose：轉置矩陣，將列變成行，將行變成列。
to3TupleTable：將矩陣轉換為三項式表示法。
restoreFrom3TupleTable：將三項式表示法還原成原本的矩陣。

建構 Matrix 物件的方式，是傳入二維陣列。比方說上圖的矩陣二，其建構方式如下：

int[][] array = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
};
Matrix matrix = new Matrix(array);

二、矩陣相加

矩陣的加法很單純，當兩個矩陣的列數與行數都相同就可進行。做法是將相同位置的數字相加。以下是示意圖與範例程式。

public void add(Matrix matrix) {
    int[][] array = matrix.data;
    if (data.length != array.length || data[0].length != array[0].length) {
        throw new IllegalArgumentException();
    }

    for (int row = 0; row < data.length; row++) {
        for (int column = 0; column < data[row].length; column++) {
            data[row][column] += array[row][column];
        }
    }
}

三、矩陣相乘

矩陣的乘法稍微有點變化，第一個矩陣的列數需等於第二個矩陣的行數才可進行。假設矩陣A為 i 列 j 行，矩陣B為 j 列 k 行，而結果是矩陣C，則C為 i 列 k 行。做法是將A的第一列與B的第一行做「加權總和」，放到C的第一列第一行；而A的第一列與B的第二行之結果，放到C的第一列第二行，依此類推。以下是示意圖。

在程式實作方面，我們先完成計算加權總和的程式。它接收兩個矩陣，以及矩陣A的列索引與矩陣B的行索引。

private int calcWeightedValue(Matrix matrix1, int rowOfMatrix1, Matrix matrix2, int columnOfMatrix2) {
    int amountOfPair = matrix1.data[0].length;
    int result = 0;
    for (int i = 0; i < amountOfPair; i++) {
        result += matrix1.data[rowOfMatrix1][i] * matrix2.data[i][columnOfMatrix2];
    }

    return result;
}

一開始先獲取矩陣A的行數，因為這個值也代表有多少組數字需要相乘。再根據方法參數指定的列與行，計算加權總和。知道如何算出矩陣C的一個數字後，接下來就是求出整個矩陣C，以下是範例程式。

public void multiply(Matrix matrix) {
    if (data[0].length != matrix.data.length) {
        throw new IllegalArgumentException();
    }

    int[][] result = new int[data.length][matrix.data[0].length];
    for (int row = 0; row < result.length; row++) {
        for (int column = 0; column < result[row].length; column++) {
            result[row][column] = calcWeightedValue(this, row, matrix, column);
        }
    }
    data = result;
}

根據前面的解說，矩陣C的第i列第k行，是由矩陣A的第 i 列與矩陣B的第 k 行計算而來。只要正確地傳入參數到 calcWeightedValue 方法即可。

四、轉置矩陣

所謂轉置矩陣，意思是將矩陣的第一列變成第一行、第二列變第二行的動作，依此類推。以下是示意圖與範例程式。

public void transpose() {
    int[][] result = new int[data[0].length][data.length];
    for (int row = 0; row < data.length; row++) {
        for (int column = 0; column < data[row].length; column++) {
            result[column][row] = data[row][column];
        }
    }

    data = result;
}

從程式實作中可以看出，事實上就是將陣列元素的列索引與行索引交換。

五、三項式表示法

假設矩陣中大部份的數字是0，則稱之為「稀疏矩陣」（Sparse Matrix）。以二維陣列來看，則能理解成有許多元素的值是0或 null。陣列中若包含許多用不到的零資料，或者元素位置為空，則該陣列會浪費太多記憶體空間。

「三項式表示法」（3-tuple representation）是一種解決浪費空間問題的方式。它只記錄非零資料及其所在的索引，以及原矩陣的列數與行數。以下是示意圖。

從圖中可以看到，稀疏矩陣被轉換成三欄的表格。在表格的第一列，分別紀錄原矩陣的列數、行數及非零資料的數量。其他列的資料則紀錄非零資料的列索引、行索引及它的值。以下是轉換的範例程式。

public int[][] to3TupleTable() {
    int amountOfElement = data.length * data[0].length;
    Integer[] rowsOfNonZero = new Integer[amountOfElement];
    Integer[] columnsOfNonZero = new Integer[amountOfElement];
    int amountOfNonZero = 0;
    for (int row = 0; row < data.length; row++) {
        for (int column = 0; column < data[row].length; column++) {
            if (data[row][column] != 0) {
                rowsOfNonZero[amountOfNonZero] = row;
                columnsOfNonZero[amountOfNonZero] = column;
                amountOfNonZero++;
            }
        }
    }

    int[][] table = new int[amountOfNonZero + 1][3];
    table[0][0] = data.length;
    table[0][1] = data[0].length;
    table[0][2] = amountOfNonZero;
    for (int i = 1; i <= amountOfNonZero; i++) {
        table[i][0] = rowsOfNonZero[i - 1];
        table[i][1] = columnsOfNonZero[i - 1];
        table[i][2] = data[table[i][0]][table[i][1]];
    }

    return table;
}

在範例程式中，首先要掃描整個矩陣陣列，紀錄非零資料的數量以及列、行索引。此處宣告 amountOfNonZero 變數、rowsOfNonZero 與 columnsOfNonZero 陣列來儲存。為確保空間足夠，這兩個陣列的長度會設成整個矩陣的資料總數。

掃描完矩陣陣列後，再另外宣告一個二維陣列做為三項式表示法的表格。在表格的第一列，寫入原始矩陣的列數、行數與非零資料數。接著開始取出 rowsOfNonZero 與 columnsOfNonZero 陣列的資料，將非零資料的索引與值寫入，就完成了。

如果要將該表格還原成原始矩陣，其實並不難。透過表格第一列，我們知道矩陣的列數與行數，能藉此宣告出二維陣列。接著從表格第二列開始走訪，將每一列所紀錄的列、行索引與資料寫回二維陣列即可。以下是範例程式。

public static Matrix restoreFrom3TupleTable(int[][] table) {
    if (table.length < 1 || table[0].length != 3) {
        throw new IllegalArgumentException();
    }

    int[][] result = new int[table[0][0]][table[0][1]];
    for (int i = 1; i < table.length; i++) {
        int row = table[i][0];
        int column = table[i][1];
        result[row][column] = table[i][2];
    }
    
    return new Matrix(result);
}

以下是本文的完整程式碼：
https://gist.github.com/ntub46010/c0653c166c8c0b50d1784e52fdc95ba6

新手工程師的程式教室

搜尋此網誌