算法导论第4章strassen算法JAVA实现

2024-06-02 16:38
文章标签 java 算法 实现 导论 strassen

本文主要是介绍算法导论第4章strassen算法JAVA实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

今天看了strassen算法，用java实现了一下。

另外题目4.2-3，如何修改Strassen算法，使之适应矩阵规模n不是2的幂的情况？

答：添加额外的行或列使之成为2的幂的方阵，添加的行或列均为0即可。

 

文章中提到在分解矩阵时使用复杂度为θ(1)的下标运算，本人为了方便，是采用拷贝赋值的方式进行的矩阵分解。

 

package answers.chapter04;import java.util.Arrays;public class MatrixMultiply {public static void SquareMatrixMultiply(int A[][], int B[][]) {int rows = A.length;int C[][] = new int[rows][rows];for (int i = 0; i < rows; i++) {for (int j = 0; j < rows; j++) {C[i][j] = 0;for (int k = 0; k < rows; k++) {C[i][j] += A[i][k] * B[k][j];}}}displaySquare(C);}public static void displaySquare(int matrix[][]) {for (int i = 0; i < matrix.length; i++) {for (int j : matrix[i]) {System.out.print(j+" ");}System.out.println();}}public static void copyToMatrixArray(int srcMatrix[][], int startI, int startJ, int iLen, int jLen, int destMatrix[][]) {for (int i = startI; i < startI + iLen; i++) {for (int j = startJ; j < startJ + jLen; j++) {destMatrix[i - startI][j - startJ] = srcMatrix[i][j]; }}}public static void copyFromMatrixArray(int destMatrix[][], int startI, int startJ, int iLen, int jLen, int srcMatrix[][]) {for (int i = 0; i < iLen; i++) {for (int j = 0; j < jLen; j++) {destMatrix[startI + i][startJ + j] = srcMatrix[i][j]; }}}public static void squareMatrixAdd(int A[][], int B[][], int C[][]) {for (int i = 0; i < A.length; i++) {for (int j = 0; j < A[i].length; j++) {C[i][j] = A[i][j] + B[i][j];}}}public static void squareMatrixSub(int A[][], int B[][], int C[][]) {for (int i = 0; i < A.length; i++) {for (int j = 0; j < A[i].length; j++) {C[i][j] = A[i][j] - B[i][j];}}}public static int[][] squareMatrixMultiplyRecursive(int A[][], int B[][]) {int n = A.length;int C[][] = new int[n][n];if (n == 1) {C[0][0] = A[0][0] * B[0][0];} else {int A11[][], A12[][], A21[][], A22[][];int B11[][], B12[][], B21[][], B22[][];int C11[][], C12[][], C21[][], C22[][];A11 = new int[n/2][n/2];A12 = new int[n/2][n/2];A21 = new int[n/2][n/2];A22 = new int[n/2][n/2];copyToMatrixArray(A, 0, 0, n/2, n/2, A11);copyToMatrixArray(A, 0, n/2, n/2, n/2, A12);copyToMatrixArray(A, n/2, 0, n/2, n/2, A21);copyToMatrixArray(A, n/2, n/2, n/2, n/2, A22);B11 = new int[n/2][n/2];B12 = new int[n/2][n/2];B21 = new int[n/2][n/2];B22 = new int[n/2][n/2];copyToMatrixArray(B, 0, 0, n/2, n/2, B11);copyToMatrixArray(B, 0, n/2, n/2, n/2, B12);copyToMatrixArray(B, n/2, 0, n/2, n/2, B21);copyToMatrixArray(B, n/2, n/2, n/2, n/2, B22);C11 = new int[n/2][n/2];C12 = new int[n/2][n/2];C21 = new int[n/2][n/2];C22 = new int[n/2][n/2];squareMatrixAdd(squareMatrixMultiplyRecursive(A11, B11), squareMatrixMultiplyRecursive(A12, B21),C11);squareMatrixAdd(squareMatrixMultiplyRecursive(A11, B12), squareMatrixMultiplyRecursive(A12, B22),C12);squareMatrixAdd(squareMatrixMultiplyRecursive(A21, B11), squareMatrixMultiplyRecursive(A22, B21),C21);squareMatrixAdd(squareMatrixMultiplyRecursive(A21, B12), squareMatrixMultiplyRecursive(A22, B22),C22);copyFromMatrixArray(C, 0, 0, n/2, n/2, C11);copyFromMatrixArray(C, 0, n/2, n/2, n/2, C12);copyFromMatrixArray(C, n/2, 0, n/2, n/2, C21);copyFromMatrixArray(C, n/2, n/2, n/2, n/2, C22);}return C;}public static int[][] strassenMatrixMultiplyRecursive(int A[][], int B[][]) {int n = A.length;int C[][] = new int[n][n];if (n == 1) {C[0][0] = A[0][0] * B[0][0];} else {int A11[][], A12[][], A21[][], A22[][];int B11[][], B12[][], B21[][], B22[][];int C11[][], C12[][], C21[][], C22[][];int S1[][], S2[][], S3[][], S4[][], S5[][], S6[][], S7[][], S8[][], S9[][], S10[][];int P1[][], P2[][], P3[][], P4[][], P5[][], P6[][], P7[][];A11 = new int[n/2][n/2];A12 = new int[n/2][n/2];A21 = new int[n/2][n/2];A22 = new int[n/2][n/2];copyToMatrixArray(A, 0, 0, n/2, n/2, A11);copyToMatrixArray(A, 0, n/2, n/2, n/2, A12);copyToMatrixArray(A, n/2, 0, n/2, n/2, A21);copyToMatrixArray(A, n/2, n/2, n/2, n/2, A22);B11 = new int[n/2][n/2];B12 = new int[n/2][n/2];B21 = new int[n/2][n/2];B22 = new int[n/2][n/2];copyToMatrixArray(B, 0, 0, n/2, n/2, B11);copyToMatrixArray(B, 0, n/2, n/2, n/2, B12);copyToMatrixArray(B, n/2, 0, n/2, n/2, B21);copyToMatrixArray(B, n/2, n/2, n/2, n/2, B22);S1 = new int[n/2][n/2];S2 = new int[n/2][n/2];S3 = new int[n/2][n/2];S4 = new int[n/2][n/2];S5 = new int[n/2][n/2];S6 = new int[n/2][n/2];S7 = new int[n/2][n/2];S8 = new int[n/2][n/2];S9 = new int[n/2][n/2];S10 = new int[n/2][n/2];squareMatrixSub(B12, B22, S1);squareMatrixAdd(A11, A12, S2);squareMatrixAdd(A21, A22, S3);squareMatrixSub(B21, B11, S4);squareMatrixAdd(A11, A22, S5);squareMatrixAdd(B11, B22, S6);squareMatrixSub(A12, A22, S7);squareMatrixAdd(B21, B22, S8);squareMatrixSub(A11, A21, S9);squareMatrixAdd(B11, B12, S10);P1 = new int[n/2][n/2];P2 = new int[n/2][n/2];P3 = new int[n/2][n/2];P4 = new int[n/2][n/2];P5 = new int[n/2][n/2];P6 = new int[n/2][n/2];P7 = new int[n/2][n/2];P1 = strassenMatrixMultiplyRecursive(A11, S1);P2 = strassenMatrixMultiplyRecursive(S2, B22);P3 = strassenMatrixMultiplyRecursive(S3, B11);P4 = strassenMatrixMultiplyRecursive(A22, S4);P5 = strassenMatrixMultiplyRecursive(S5, S6);P6 = strassenMatrixMultiplyRecursive(S7, S8);P7 = strassenMatrixMultiplyRecursive(S9, S10);C11 = new int[n/2][n/2];C12 = new int[n/2][n/2];C21 = new int[n/2][n/2];C22 = new int[n/2][n/2];int temp[][] = new int[n/2][n/2];squareMatrixAdd(P5, P4, temp);squareMatrixSub(temp, P2, temp);squareMatrixAdd(temp, P6, C11);squareMatrixAdd(P1, P2, C12);squareMatrixAdd(P3, P4, C21);squareMatrixAdd(P5, P1, temp);squareMatrixSub(temp, P3, temp);squareMatrixSub(temp, P7, C22);copyFromMatrixArray(C, 0, 0, n/2, n/2, C11);copyFromMatrixArray(C, 0, n/2, n/2, n/2, C12);copyFromMatrixArray(C, n/2, 0, n/2, n/2, C21);copyFromMatrixArray(C, n/2, n/2, n/2, n/2, C22);}return C;}public static int sMatrixA[][] = new int[][] {{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},};public static int sMatrixB[][] = new int[][] {{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},};public static void main(String[] args) {System.out.println("普通矩阵乘法");SquareMatrixMultiply(sMatrixA, sMatrixB);System.out.println("\n递归矩阵乘法");int C[][] = squareMatrixMultiplyRecursive(sMatrixA, sMatrixB);displaySquare(C);System.out.println("\n Strassen 递归矩阵乘法");C = strassenMatrixMultiplyRecursive(sMatrixA, sMatrixB);displaySquare(C);}
}

这篇关于算法导论第4章strassen算法JAVA实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/1024516。

相关文章

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键
阅读更多...
SpringCloud中的@FeignClient注解使用详解

SpringCloud中的@FeignClient注解使用详解

《SpringCloud中的@FeignClient注解使用详解》在SpringCloud中使用Feign进行服务间的调用时,通常会使用@FeignClient注解来标记Feign客户端接口,这篇文章... 在Spring Cloud中使用Feign进行服务间的调用时，通常会使用@FeignClient注解
阅读更多...
Java Spring 中的监听器Listener详解与实战教程

Java Spring 中的监听器Listener详解与实战教程

《JavaSpring中的监听器Listener详解与实战教程》Spring提供了多种监听器机制,可以用于监听应用生命周期、会话生命周期和请求处理过程中的事件,：本文主要介绍JavaSprin... 目录一、监听器的作用1.1 应用生命周期管理1.2 会话管理1.3 请求处理监控二、创建监听器2.1 Ser
阅读更多...
C/C++中OpenCV 矩阵运算的实现

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算（标量与矩阵）、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元
阅读更多...
C/C++的OpenCV 进行图像梯度提取的几种实现

C/C++的OpenCV 进行图像梯度提取的几种实现

《C/C++的OpenCV进行图像梯度提取的几种实现》本文主要介绍了C/C++的OpenCV进行图像梯度提取的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录预www.chinasem.cn备知识1. 图像加载与预处理2. Sobel 算子计算 X 和 Y
阅读更多...
C/C++和OpenCV实现调用摄像头

C/C++和OpenCV实现调用摄像头

《C/C++和OpenCV实现调用摄像头》本文主要介绍了C/C++和OpenCV实现调用摄像头,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录准备工作1. 打开摄像头2. 读取视频帧3. 显示视频帧4. 释放资源5. 获取和设置摄像头属性
阅读更多...
JVisualVM之Java性能监控与调优利器详解

JVisualVM之Java性能监控与调优利器详解

《JVisualVM之Java性能监控与调优利器详解》本文将详细介绍JVisualVM的使用方法,并结合实际案例展示如何利用它进行性能调优,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全... 目录1. JVisualVM简介2. JVisualVM的安装与启动2.1 启动JVisualVM2
阅读更多...
c/c++的opencv图像金字塔缩放实现

c/c++的opencv图像金字塔缩放实现

《c/c++的opencv图像金字塔缩放实现》本文主要介绍了c/c++的opencv图像金字塔缩放实现,通过对原始图像进行连续的下采样或上采样操作,生成一系列不同分辨率的图像,具有一定的参考价值,感兴... 目录图像金字塔简介图像下采样 (cv::pyrDown)图像上采样 (cv::pyrUp)C++ O
阅读更多...
c/c++的opencv实现图片膨胀

c/c++的opencv实现图片膨胀

《c/c++的opencv实现图片膨胀》图像膨胀是形态学操作,通过结构元素扩张亮区填充孔洞、连接断开部分、加粗物体,OpenCV的cv::dilate函数实现该操作,本文就来介绍一下opencv图片... 目录什么是图像膨胀？结构元素 (KerChina编程nel)OpenCV 中的 cv::dilate() 函
阅读更多...
Java如何从Redis中批量读取数据

Java如何从Redis中批量读取数据

《Java如何从Redis中批量读取数据》：本文主要介绍Java如何从Redis中批量读取数据的情况,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一.背景概述二.分析与实现三.发现问题与屡次改进3.1.QPS过高而且波动很大3.2.程序中断，抛异常3.3.内存消
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2