Some operations of sparse matrices (multiplication, exponentiation, addition, transposition)_Can sparse matrices be multiplied with ordinary matrices_sundial dreams’ blog

I believe everyone knows the matrix, and some common operations, such as multiplication and addition, I believe everyone is familiar with it. Take matrix multiplication as an example. Is the conventional implementation of the computer just a three-layer for?

long[][] sum = new long[n][m];
 for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
       for (int k = 0; k < l; k++)
           sum[i][j] += a[i][k] * b[k][j];

What about sparse matrices?

First introduce the sparse matrix. To put it bluntly, most of the positions in the matrix are 0, and only a small part is not 0, just like the matrix below

. . . . . . . . . . . . . . . . \\ 0 & 1 & 0 & 1 & 0\\ 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 4 & 0 & 0 & 1 \end{pmatrix}” class=”mathcode” src=”https://private.codecogs.com/gif.latex?%5Clarge%20%20%20%5Cbegin%7Bpmatrix%7D%200%20%26%200%20%26%200%20%26%200%20%26%200%5C%5C%200%20%26%201%20%26%200%20%20%20%26%201%20%26%200%5C%5C%200%20%26%202%20%26%200%20%26%200%20%26%200%5C%5C%200%20%20%20%26%200%20%26%201%20%26%200%20%26%200%5C%5C%200%20%26%204%20%26%200%20%26%200%20%26%20%20%201%20%5Cend%7Bpmatrix%7D”>

In terms of storage, if there is a two-dimensional array in the conventional matrix storage method, a lot of space must be wasted, so we can use the adjacency list in graph theory to store sparse matrices in this way, for example , the storage method of the above matrix and adjacency list is

In JAVA, it is the storage structure of Map<Long, Map. After the storage is done, let’s see how to do the matrix multiplication operation.

Sparse matrix multiplication is relatively complicated. Normal matrix multiplication is the operation of two two-dimensional arrays, but according to the above storage method, it will become the operation of two adjacency lists, and the multiplication is still An adjacency list, for example, how to multiply sparse matrices

It can be found that only when the corresponding position is not zero, we can get the value. The picture below may be clearer (the second matrix is ​​transposed)

The above figure describes the process of multiplying sparse matrices. In fact, there are not many steps. First, transpose the second matrix, then intersect the column indices, and finally multiply and add the corresponding positions to get the result.

The addition, exponentiation, and transposition of sparse matrices are actually very simple. In fact, they are operations on the adjacency list, so you can directly refer to the following code.

The Java code is implemented as follows

import java.util.*;

 class Tools {
     static public  Set intersection(Set A, Set B) {
         Set C = new HashSet();
         A.forEach(v -> {
             if (B. contains(v)) C. add(v);
         });
         return C;
     }

 }

 class SparseMatrix {


     private Map<Long, Map> matrix;
     private long n, m;

     public SparseMatrix(long n, long m) {
         this.n = n;
         this.m = m;
         this. matrix = new HashMap();
     }

     public void append(long i, long j, T value) {
         SparseMatrix. makeMap(i, j, value, matrix);
     }

     static private  void makeMap(long i, long j, T v, Map<Long, Map> ref) {
         Map map;
         if ((map = ref. get(i)) != null) {
             map. put(j, v);
         } else {
             map = new HashMap();
             map. put(j, v);
             ref. put(i, map);
         }
     }

     /**
      * matrix multiplication
      *
      * @param A
      * @param B
      * @return result
      */
     static public SparseMatrix multiply(SparseMatrix A, SparseMatrix B) {
         SparseMatrix result = new SparseMatrix(A.n, B.m);
         Map<Long, Map> bMatrix = B.transpose().matrix, aMatrix = A.matrix;aMatrix.forEach((i, mapJ) -> bMatrix.forEach((j, mapI) -> {
             long sum = 0;
             Set set = Tools.intersection(mapI.keySet(), mapJ.keySet());
             for (Long index : set) sum += aMatrix.get(i).get(index) * bMatrix.get(j).get(index);
             if (sum != 0) SparseMatrix. makeMap(i, j, sum, result. matrix);
         }));
         return result;
     }

     /**
      * matrix fast power
      *
      * @param matrix
      * @param n
      * @return
      */
     static public SparseMatrix fastPower(SparseMatrix matrix, Long n) {
         if (n  0");
         if (matrix.n != matrix.m) throw new IndexOutOfBoundsException("n != m");
         SparseMatrix result = new SparseMatrix(matrix.n, matrix.m);
         if (n == 0) {
             for (int i = 0; i < matrix.n; i++) result. append(i, i, 1L);
         } else {
             for (Long i : matrix. matrix. keySet()) result. append(i, i, 1L);
         }
         while (n != 0) {
             if (n % 2 == 1) result = SparseMatrix. multiply(result, matrix);
             matrix = SparseMatrix. multiply(matrix, matrix);
             n /= 2;
         }
         return result;
     }

     /**
      * matrix addition
      *
      * @param matrixA
      * @param matrixB
      * @return
      */
     static public SparseMatrix add(SparseMatrix matrixA, SparseMatrix matrixB) {
         if (matrixA.n != matrixB.n || matrixA.m != matrixB.m) throw new IndexOutOfBoundsException("error");
         SparseMatrix result = new SparseMatrix(matrixA.n, matrixA.m);
         matrixA.matrix.forEach((i, mapJ) -> mapJ.forEach((j, value) -> {
             Map map;
             if ((map = matrixB.matrix.get(i)) != null) {
                 Long valueB;
                 if ((valueB = map.get(j)) != null) {
                     SparseMatrix.makeMap(i, j, value + valueB, result.matrix);
                 } else {
                     SparseMatrix. makeMap(i, j, value, result. matrix);
                 }
             } else {
                 SparseMatrix. makeMap(i, j, value, result. matrix);
             }
         }));
         matrixB.matrix.forEach((i, mapJ) -> mapJ.forEach((j, value) -> {
             if (result. matrix. get(i) == null) {
                 SparseMatrix. makeMap(i, j, value, result. matrix);
             } else if (result. matrix. get(i). get(j) == null) {
                 SparseMatrix. makeMap(i, j, value, result. matrix);
             }
         }));
         System.out.println(result);
         return result;
     }

     /**
      * Matrix transpose
      *
      * @return
      */
     public SparseMatrix transpose() {
         SparseMatrix result = new SparseMatrix(n, m);
         matrix.forEach((i, mapJ) -> mapJ.forEach((j, value) -> {
             SparseMatrix. makeMap(j, i, value, result. matrix);
         }));
         return result;
     }

     public String toString() {
         StringBuilder string = new StringBuilder();
         string.append("MATRIX[").append(n).append(", ").append(m).append("]: ");
         long size = 0;
         for (Map.Entry<Long, Map> entry : matrix.entrySet()) {
             Long i = entry. getKey();
             Map map = entry. getValue();
             for (Map. Entry e : map. entrySet()) {
                 Long j = e. getKey();
                 T value = e. getValue();
                 String str = "matrix(" + i + ", " + j + ") = " + value + " ";
                 string. append(str);
                 size++;
             }
         }
         if (size != n * m) string. append("other matrix(i, j) = 0");
         return string.toString();
     }

 }