本例输入为两个任意尺寸的矩阵m * n, n * m,输出为两个矩阵的乘积。计算任意尺寸矩阵相乘时,使用了Strassen算法。程序为自编,经过测试,请放心使用。基本算法是:
1.对于方阵(正方形矩阵),找到最大的l, 使得l = 2 ^ k, k为整数并且l < m。边长为l的方形矩阵则采用Strassen算法,其余部分以及方形矩阵中遗漏的部分用蛮力法。
2.对于非方阵,依照行列相应添加0使其成为方阵。
StrassenMethodTest.java
package matrixalgorithm; import java.util.Scanner; public class StrassenMethodTest { private StrassenMethod strassenMultiply; StrassenMethodTest(){ strassenMultiply = new StrassenMethod(); }//end cons public static void main(String[] args){ Scanner input = new Scanner(System.in); System.out.println("Input row size of the first matrix: "); int arow = input.nextInt(); System.out.println("Input column size of the first matrix: "); int acol = input.nextInt(); System.out.println("Input row size of the second matrix: "); int brow = input.nextInt(); System.out.println("Input column size of the second matrix: "); int bcol = input.nextInt(); double[][] A = new double[arow][acol]; double[][] B = new double[brow][bcol]; double[][] C = new double[arow][bcol]; System.out.println("Input data for matrix A: "); /*In all of the codes later in this project, r means row while c means column. */ for (int r = 0; r < arow; r++) { for (int c = 0; c < acol; c++) { System.out.printf("Data of A[%d][%d]: ", r, c); A[r][c] = input.nextDouble(); }//end inner loop }//end loop System.out.println("Input data for matrix B: "); for (int r = 0; r < brow; r++) { for (int c = 0; c < bcol; c++) { System.out.printf("Data of A[%d][%d]: ", r, c); B[r][c] = input.nextDouble(); }//end inner loop }//end loop StrassenMethodTest algorithm = new StrassenMethodTest(); C = algorithm.multiplyRectMatrix(A, B, arow, acol, brow, bcol); //Display the calculation result: System.out.println("Result from matrix C: "); for (int r = 0; r < arow; r++) { for (int c = 0; c < bcol; c++) { System.out.printf("Data of C[%d][%d]: %f\n", r, c, C[r][c]); }//end inner loop }//end outter loop }//end main //Deal with matrices that are not square: public double[][] multiplyRectMatrix(double[][] A, double[][] B, int arow, int acol, int brow, int bcol) { if (arow != bcol) //Invalid multiplicatio return new double[][]{{0}}; double[][] C = new double[arow][bcol]; if (arow < acol) { double[][] newA = new double[acol][acol]; double[][] newB = new double[brow][brow]; int n = acol; for (int r = 0; r < acol; r++) for (int c = 0; c < acol; c++++) newA[r][c] = 0.0; for (int r = 0; r < brow; r++) for (int c = 0; c < brow; c++) newB[r][c] = 0.0; for (int r = 0; r < arow; r++) for (int c = 0; c < acol; c++) newA[r][c] = A[r][c]; for (int r = 0; r < brow; r++) for (int c = 0; c < bcol; c++) newB[r][c] = B[r][c]; double[][] C2 = multiplySquareMatrix(newA, newB, n); for(int r = 0; r < arow; r++) for(int c = 0; c < bcol; c++) C[r][c] = C2[r][c]; }//end if else if(arow == acol) C = multiplySquareMatrix(A, B, arow); else { int n = arow; double[][] newA = new double[arow][arow]; double[][] newB = new double[bcol][bcol]; for (int r = 0; r < arow; r++) for (int c = 0; c < arow; c++) newA[r][c] = 0.0; for (int r = 0; r < bcol; r++) for (int c = 0; c < bcol; c++) newB[r][c] = 0.0; for (int r = 0; r < arow; r++) for (int c = 0; c < acol; c++) newA[r][c] = A[r][c]; for (int r = 0; r < brow; r++) for (int c = 0; c < bcol; c++) newB[r][c] = B[r][c]; double[][] C2 = multiplySquareMatrix(newA, newB, n); for(int r = 0; r < arow; r++) for(int c = 0; c < bcol; c++) C[r][c] = C2[r][c]; }//end else return C; }//end method //Deal with matrices that are square matrices. public double[][] multiplySquareMatrix(double[][] A2, double[][] B2, int n){ double[][] C2 = new double[n][n]; for(int r = 0; r < n; r++) for(int c = 0; c < n; c++) C2[r][c] = 0; if(n == 1){ C2[0][0] = A2[0][0] * B2[0][0]; return C2; }//end if int exp2k = 2; while(exp2k <= (n / 2) ){ exp2k *= 2; }//end loop if(exp2k == n){ C2 = strassenMultiply.strassenMultiplyMatrix(A2, B2, n); return C2; }//end else //The "biggest" strassen matrix: double[][][] A = new double[6][exp2k][exp2k]; double[][][] B = new double[6][exp2k][exp2k]; double[][][] C = new double[6][exp2k][exp2k]; for(int r = 0; r < exp2k; r++){ for(int c = 0; c < exp2k; c++){ A[0][r][c] = A2[r][c]; B[0][r][c] = B2[r][c]; }//end inner loop }//end outter loop C[0] = strassenMultiply.strassenMultiplyMatrix(A[0], B[0], exp2k); for(int r = 0; r < exp2k; r++) for(int c = 0; c < exp2k; c++) C2[r][c] = C[0][r][c]; int middle = exp2k / 2; for(int r = 0; r < middle; r++){ for(int c = exp2k; c < n; c++){ A[1][r][c - exp2k] = A2[r][c]; B[3][r][c - exp2k] = B2[r][c]; }//end inner loop }//end outter loop for(int r = exp2k; r < n; r++){ for(int c = 0; c < middle; c++){ A[3][r - exp2k][c] = A2[r][c]; B[1][r - exp2k][c] = B2[r][c]; }//end inner loop }//end outter loop for(int r = middle; r < exp2k; r++){ for(int c = exp2k; c < n; c++){ A[2][r - middle][c - exp2k] = A2[r][c]; B[4][r - middle][c - exp2k] = B2[r][c]; }//end inner loop }//end outter loop for(int r = exp2k; r < n; r++){ for(int c = middle; c < n - exp2k + 1; c++){ A[4][r - exp2k][c - middle] = A2[r][c]; B[2][r - exp2k][c - middle] = B2[r][c]; }//end inner loop }//end outter loop for(int i = 1; i <= 4; i++) C[i] = multiplyRectMatrix(A[i], B[i], middle, A[i].length, A[i].length, middle); /* Calculate the final results of grids in the "biggest 2^k square, according to the rules of matrice multiplication. */ for (int row = 0; row < exp2k; row++) { for (int col = 0; col < exp2k; col++) { for (int k = exp2k; k < n; k++) { C2[row][col] += A2[row][k] * B2[k][col]; }//end loop }//end inner loop }//end outter loop //Use brute force to solve the rest, will be improved later: for(int col = exp2k; col < n; col++){ for(int row = 0; row < n; row++){ for(int k = 0; k < n; k++) C2[row][col] += A2[row][k] * B2[k][row]; }//end inner loop }//end outter loop for(int row = exp2k; row < n; row++){ for(int col = 0; col < exp2k; col++){ for(int k = 0; k < n; k++) C2[row][col] += A2[row][k] * B2[k][row]; }//end inner loop }//end outter loop return C2; }//end method }//end class
StrassenMethod.java
package matrixalgorithm; import java.util.Scanner; public class StrassenMethod { private double[][][][] A = new double[2][2][][]; private double[][][][] B = new double[2][2][][]; private double[][][][] C = new double[2][2][][]; /*//Codes for testing this class: public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("Input size of the matrix: "); int n = input.nextInt(); double[][] A = new double[n][n]; double[][] B = new double[n][n]; double[][] C = new double[n][n]; System.out.println("Input data for matrix A: "); for (int r = 0; r < n; r++) { for (int c = 0; c < n; c++) { System.out.printf("Data of A[%d][%d]: ", r, c); A[r][c] = input.nextDouble(); }//end inner loop }//end loop System.out.println("Input data for matrix B: "); for (int r = 0; r < n; r++) { for (int c = 0; c < n; c++) { System.out.printf("Data of A[%d][%d]: ", r, c); B[r][c] = input.nextDouble(); }//end inner loop }//end loop StrassenMethod algorithm = new StrassenMethod(); C = algorithm.strassenMultiplyMatrix(A, B, n); System.out.println("Result from matrix C: "); for (int r = 0; r < n; r++) { for (int c = 0; c < n; c++) { System.out.printf("Data of C[%d][%d]: %f\n", r, c, C[r][c]); }//end inner loop }//end outter loop }//end main*/ public double[][] strassenMultiplyMatrix(double[][] A2, double B2[][], int n){ double[][] C2 = new double[n][n]; //Initialize the matrix: for(int rowIndex = 0; rowIndex < n; rowIndex++) for(int colIndex = 0; colIndex < n; colIndex++) C2[rowIndex][colIndex] = 0.0; if(n == 1) C2[0][0] = A2[0][0] * B2[0][0]; //"Slice matrices into 2 * 2 parts: else{ double[][][][] A = new double[2][2][n / 2][n / 2]; double[][][][] B = new double[2][2][n / 2][n / 2]; double[][][][] C = new double[2][2][n / 2][n / 2]; for(int r = 0; r < n / 2; r++){ for(int c = 0; c < n / 2; c++){ A[0][0][r][c] = A2[r][c]; A[0][1][r][c] = A2[r][n / 2 + c]; A[1][0][r][c] = A2[n / 2 + r][c]; A[1][1][r][c] = A2[n / 2 + r][n / 2 + c]; B[0][0][r][c] = B2[r][c]; B[0][1][r][c] = B2[r][n / 2 + c]; B[1][0][r][c] = B2[n / 2 + r][c]; B[1][1][r][c] = B2[n / 2 + r][n / 2 + c]; }//end loop }//end loop n = n / 2; double[][][] S = new double[10][n][n]; S[0] = minusMatrix(B[0][1], B[1][1], n); S[1] = addMatrix(A[0][0], A[0][1], n); S[2] = addMatrix(A[1][0], A[1][1], n); S[3] = minusMatrix(B[1][0], B[0][0], n); S[4] = addMatrix(A[0][0], A[1][1], n); S[5] = addMatrix(B[0][0], B[1][1], n); S[6] = minusMatrix(A[0][1], A[1][1], n); S[7] = addMatrix(B[1][0], B[1][1], n); S[8] = minusMatrix(A[0][0], A[1][0], n); S[9] = addMatrix(B[0][0], B[0][1], n); double[][][] P = new double[7][n][n]; P[0] = strassenMultiplyMatrix(A[0][0], S[0], n); P[1] = strassenMultiplyMatrix(S[1], B[1][1], n); P[2] = strassenMultiplyMatrix(S[2], B[0][0], n); P[3] = strassenMultiplyMatrix(A[1][1], S[3], n); P[4] = strassenMultiplyMatrix(S[4], S[5], n); P[5] = strassenMultiplyMatrix(S[6], S[7], n); P[6] = strassenMultiplyMatrix(S[8], S[9], n); C[0][0] = addMatrix(minusMatrix(addMatrix(P[4], P[3], n), P[1], n), P[5], n); C[0][1] = addMatrix(P[0], P[1], n); C[1][0] = addMatrix(P[2], P[3], n); C[1][1] = minusMatrix(minusMatrix(addMatrix(P[4], P[0], n), P[2], n), P[6], n); n *= 2; for(int r = 0; r < n / 2; r++){ for(int c = 0; c < n / 2; c++){ C2[r][c] = C[0][0][r][c]; C2[r][n / 2 + c] = C[0][1][r][c]; C2[n / 2 + r][c] = C[1][0][r][c]; C2[n / 2 + r][n / 2 + c] = C[1][1][r][c]; }//end inner loop }//end outter loop }//end else return C2; }//end method //Add two matrices according to matrix addition. private double[][] addMatrix(double[][] A, double[][] B, int n){ double C[][] = new double[n][n]; for(int r = 0; r < n; r++) for(int c = 0; c < n; c++) C[r][c] = A[r][c] + B[r][c]; return C; }//end method //Substract two matrices according to matrix addition. private double[][] minusMatrix(double[][] A, double[][] B, int n){ double C[][] = new double[n][n]; for(int r = 0; r < n; r++) for(int c = 0; c < n; c++) C[r][c] = A[r][c] - B[r][c]; return C; }//end method }//end class
希望本文所述对大家学习java程序设计有所帮助。
本文向大家介绍Java实现的求逆矩阵算法示例,包括了Java实现的求逆矩阵算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Java实现的求逆矩阵算法。分享给大家供大家参考,具体如下: 运行结果: 更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
本文向大家介绍java实现的n*n矩阵求值及求逆矩阵算法示例,包括了java实现的n*n矩阵求值及求逆矩阵算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了java实现的n*n矩阵求值及求逆矩阵算法。分享给大家供大家参考,具体如下: 先来看看运行结果: java版的写出来了,用的跟c语言相同的算法,然后看看能不能以后加个框做成程序: 更多关于java算法相关内容感兴趣的读者可查看本站
C++:15秒(源) Python:6分13秒(来源) C++:45分钟(源) 蟒蛇:10小时后被杀死(来源) 为什么Strassen矩阵乘法比标准矩阵乘法慢得多? null null null
本文向大家介绍Ruby实现的矩阵连乘算法,包括了Ruby实现的矩阵连乘算法的使用技巧和注意事项,需要的朋友参考一下 动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果。 代码:
问题内容: 我正在尝试计算Java中的逆矩阵。 我遵循伴随方法(首先计算伴随矩阵,然后转置该矩阵,最后将其乘以行列式值的倒数)。 当矩阵不太大时有效。我检查过,对于尺寸最大为12x12的矩阵,可以快速提供结果。但是,当矩阵大于12x12时,完成计算所需的时间呈指数增长。 我需要反转的矩阵是19x19,并且花费太多时间。消耗更多时间的方法是用于行列式计算的方法。 我使用的代码是: 有人知道如何更有效
本文向大家介绍C++实现矩阵原地转置算法,包括了C++实现矩阵原地转置算法的使用技巧和注意事项,需要的朋友参考一下 本文实例描述了C++实现矩阵原地转置算法,是一个非常经典的算法,相信对于学习C++算法的朋友有很大的帮助。具体如下: 一、问题描述 微软面试题:将一个MxN的矩阵存储在一个一维数组中,编程实现矩阵的转置。 要求:空间复杂度为O(1) 二、思路分析 下面以一个4x2的矩阵A={1,2,