计 算 机 系 统 应 用 https://www.doczj.com/doc/0916058775.html, 2011 年 第20卷 第 1期
178 经验交流 Experiences Exchange
GPU 上的矩阵乘法的设计与实现①
梁娟娟，任开新，郭利财，刘燕君
(中国科学技术大学 计算机科学与技术学院，合肥 230027)
摘 要: 矩阵乘法是科学计算中最基本的操作，高效实现矩阵乘法可以加速许多应用。本文使用NVIDIA 的CUDA
在GPU 上实现了一个高效的矩阵乘法。测试结果表明，在Geforce GTX 260上，本文提出的矩阵乘法的速度是理论峰值的97%，跟CUBLAS 库中的矩阵乘法相当。
关键词: 矩阵乘法；GPU ；CUDA
Design and Implementation of Matrix Multiplication on GPU
LIANG Juan-Juan, REN Kai-Xin, GUO Li-Cai, LIU Yan-Jun
(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China)
Abstract: Matrix multiplication is a basic operation in scientific computing. Efficient implementation of matrix multiplication can speed up many applications. In this paper, we implement an efficient matrix multiplication on GPU using NVIDIA’s CUDA. The experiment shows that our implementation is as fast as the implementation in CUBLAS, and the speed of our implementation can reach the peak speed’s 97%, on Geforce GTX260. Keywords: matrix multiplication; GPU; CUDA
GPU 是一种高性能的众核处理器，可以用来加速许多应用。CUDA 是NVIDIA 公司为NVIDIA 的GPU 开发的一个并行计算架构和一门基于C 的编程语言。在CUDA 中程序可以直接操作数据而无需借助于图形系统的API 。现在已经有许多应用和典型算法使用CUDA 在GPU 上实现出来。
1 引言
矩阵乘法是科学计算中的最基本的操作，在许多领域中有广泛的应用。对于矩阵乘法的研究有几个方向。一个是研究矩阵乘法的计算复杂度，研究矩阵乘法的时间复杂度的下界，这方面的工作有strassen 算法[1]等。另外一个方向是根据不同的处理器体系结构，将经典的矩阵乘法高效的实现出来，这方面的结果体现在许多高效的BLAS 库。许多高效的BLAS 库都根据体系结构的特点高效的实现了矩阵乘法，比如GotoBLAS [2], ATLAS [3]等。Fatahalian [4]等人使
用着色语言设计了在GPU 上的矩阵乘法。CUBLAS 库是使用CUDA 实现的BLAS 库，里面包含了高性能的矩阵乘法。
本文剩下的部分组织如下，第2节介绍了CUDA 的编程模型，简单描述了CUDA 上编程的特点。第3节讨论了数据已经拷贝到显存上的矩阵乘法，首先根据矩阵分块的公式给出了一个朴素的矩阵乘法实现，分析朴素的矩阵乘法的资源利用情况，然后提出了一种新的高效的矩阵乘法。第4节讨论了大规模的矩阵乘法的设计和实现，着重讨论了数据在显存中的调度。第5节是实验结果。第6节是总结和展望。
2 CUDA 编程模型和矩阵乘法回顾
2.1 CUDA 编程模型
NVIDIA 的GPU 是由N 个多核处理器和一块显存构成的。每个多核处理器由M 个处理器核，1个指令部件，一个非常大的寄存器堆，一小块片上的共享内
① 基金项目:国家自然科学基金(60833004);国家高技术研究发展计划(863)(2008AA010902)
收稿时间:2010-04-26;收到修改稿时间:2010-05-21
2011 年 第20卷 第 1期 https://www.doczj.com/doc/0916058775.html, 计 算 机 系 统 应 用
Experiences Exchange 经验交流 179
存以及一些只读的缓存(包括纹理缓存和常量缓存)。多处理器内所有核共用一个指令部件，在一个时钟周期内，每个处理器核执行同一条指令，但是数据可以是不一样的。
GT200是NVIDIA 的第10代GPU ，它发布于2008年6月。GT200的多核处理器包含8个处理器核，16K 字节的片上共享存储器，16384个32位的寄存器，1个指令部件，1个特殊功能单元部件，1个双精度部件以及一些只读的缓存。GT200是第一代支持双精度计算的显卡。
在CUDA 中的核心概念是内核函数。内核函数是从CPU 端调用，运行在GPU 上的函数。CUDA 的运行管理系统产生一个grid 来运行一个内核函数。1个grid 包含一组block ，每个block 是有一组线程组成。grid 维度和block 的维度都是在调用内核函数的时候指定的。在一个grid 中，block 之间没有同步和通信机制，因此block 之间必须是独立的。在一个block 里面，线程之间可以用同步原语_syncthreads()来同步，每个block 可以分配一定量的所有线程都可以访问的共享内存。一个block 只能映射到一个多核处理器上执行，而不能将线程分布在不同的处理器中。一个多核处理器上可以同时运行多个block 。在运行一个block 的线程时，CUDA 运行管理系统将block 中的线程分成一个个warp ，每次取出一个warp 来运行。一个warp 分成前半个warp 和后半个warp 。运行的最小单位是半个warp ，一个周期里面，半个warp 的所有线程执行相同的指令。在CUDA 2.3的版本中，一个warp 中含有32个线程。
一个内核函数可以使用的存储器资源包括全局内存，共享内存，纹理内存，常量内存以及寄存器。全局内存，纹理内存以及常量内存都是分配在显存中的，可以被所有的block 访问。纹理内存和常量内存都是只读的，如果重复访问的话，它们会被缓存在片上的缓存上。全局内存是不会被缓存的。GPU 访问显存是使用内存事务来完成的。完成一个内存事务的代价是非常高的，通常需要400-600个周期。但是，如果半个warp 的所有线程的访问满足：(1)所有线程访问1个字节，并且访问的位置在一个32字节对齐的同一个32字节的段里面。(2)所有的线程访问2个字节，并且访问的位置在一个64字节对齐的同一个64字节的段里面。(3)所有的线程访问4个字节，并且访问的位置
在一个128字节对齐的同一个128字节的段里面。三个条件中的一个，则半个warp 的访存会被合并成一个内存事务。 2.2 矩阵乘法回顾
给定矩阵乘法C=AB ，其中()ij C c =是M N ×的矩阵，()ij A a =是M K ×的矩阵，()ij B b =是K N ×的矩阵。则ij c 的定义为
1K
ij ik kj k c a b ==∑
(1)
假定,,M wp N hq K kr ===，将矩阵C 分解为p q ×的分块矩阵()ij c ，每个ij c 是一个w h ×的小矩阵，A 分解成为p k ×的分块矩阵()ij a ，每个ij a 是一个w r ×的矩阵，B 分解成为k q ×的分块矩阵()ij b ，每个ij b 是一个
r h ×的元素。则分块矩阵乘法的定义为
1
k
ij is sj s c a b ==∑ (2)
在等式中核心的操作是
ij is sj ij c a b c =+
(3)
假定缓存中同时可以放下分块后的ij c ，is a ，sj b ，则等式需要的访存数量是wh wK Kh ++，计算量是
2whK
,平均一次访存的计算量是
2/()whK wh wK Kh ++，略去分母中的小项wh 得到2/(1/1/)w h +，从而知道1/1/w h +越小，平均一次访
存做的计算量是越多的。
3 算法设计和实现
本节假定矩阵A ，B ，C 已经存放在显卡的显存中，矩阵是以行主序的方式存储的。假定
,,M wp N hq K kr ===，A ，B ，C 分别是M K ×，K N ×，M N ×的矩阵。
3.1 普通实现
按照等式，每个ij c 的计算是相互独立的。将矩阵C 分成许多w h ×的子矩阵，每个子矩阵使用不同的block 来计算。假定一个block 的线程数目是T ，这样每个线程需要计算C 中/wh T 个元素。将C 中的元素固定分配给某个线程，这样可以将C 中的元素存储在每个线程的寄存器中。为了充分利用GPU 上的带宽，将矩阵A 和B 读取进来的数据先缓存在片上的共享存储器中。每次读取A 的一个w r ×的子矩阵和B 的一个
r h ×的子矩阵到共享存储里，在共享存储器中完成一
个小块的矩阵乘法。这样得到的算法如图1所示。
计 算 机 系 统 应 用 https://www.doczj.com/doc/0916058775.html, 2011 年 第20卷 第 1期
180 经验交流 Experiences Exchange
下面讨论算法的参数。为了提高访问全局内存的效率，r 和h 必须是16的倍数。同时，一个block 需要的共享内存是8()wr rh +字节。每个block 需要的共享内存的大小必须小于一个SM 上的共享存储器的大小，从而得到8()16384wr rh +<，同时所有线程需要的寄存器数目要小于一个SM 上的寄存器数目。每个双精度的数需要占用2个32位的寄存器，w 和h 必须满足不等式216384wh ≤。为了让w 和h 足够大，我们取
16r =，这样有128w h +<。根据矩阵分块乘法，
1/1/w h +越小越好，而h 必须是16的倍数，在算法
中取32w =，64h =。于是有2048wh =。而当前一个block 中的线程数目最多是512，于是可以取T=512，每个线程计算4个数据。使用cuda 编译器编译以后，每个线程需要使用24个寄存器，一个block 总共需要12288个寄存器，需要12728个共享存储器。
图1 矩阵乘法的普通实现
3.2 优化实现
在3.1节的算法中，矩阵A 和B 的子块都是保存在共享存储器中，而C 的子块是保存在寄存器中。主要是根据共享存储器的限制来得到w 和h 的值，寄存器的使用数目远远没有达到处理器的上限，处理器的寄存器资源没有被充分利用。为了充分利用处理器上的寄存器资源，我们改变数据映射方式。仍然假设每个block 计算w h ×的一个子矩阵Cs ，使用一个线程来计算Cs 中的一列，也就是要计算w 个元素。
注意到一个线程只会访问矩阵B 的一列，也就是要计算w 个元素。注意到一个线程只会访问矩阵B 的一列，不同的线程访问B 的元素是不相交的。这样B 的元素可以放在线程中的寄存器中，而不用存放在共享存储器中。在共享存储器中分配一个w r ×的数组As 存放矩阵A 的子块。这样得到的算法如图2所示。
图2 矩阵乘法的优化实现
下面讨论算法的参数。主要考虑的是两个条件，一个是充分利用片上的存储资源，包括寄存器和共享存储器；另外一个是要有足够的线程在运行。一个block 需要的共享存储器是保存A 的子矩阵的数组
As ，大小是8wr 字节；需要的寄存器数目包括矩阵B
和矩阵C 的元素，需要2()wh h +个寄存器。为了节省共享内存，同时充分利用GPU 上的带宽，取r=16。另外一个方面，线程数目应该是32的倍数，为了保证足够的线程来计算，至少需要2个warp 来计算，从而
64h ≥。当h=64时，取w=16，用cuda 编译编译好了
以后，每个线程需要50个寄存器，一个block 需要的总寄存器数目是3328，共享内存是2248字节。这样一个处理器的资源可以容纳的block 数目为
5121638416384
min(
,,)46433282248
=
4 大规模矩阵乘法的算法设计
在本节中，我们假定显卡的显存已经无法同时容
Experiences Exchange 经验交流 181
纳矩阵A ，B 和C 。显存只能存放部分数据，因此把矩阵A ，B 以及C 分块。为了充分利用显卡的资源，可以考虑使用数据拷贝和计算进行重叠的技术。按照
2.2节的分析，w 和h 越大，在主机和显卡之间传送的数据就越小。将矩阵C 分成w h ×的子块，在显存中分配5块内存的空间：00101,,,,C A A B B 。其中0C 用来存放
w h ×的矩阵，01,A A 用来存放w r ×的矩阵，而01,B B 用
来存放r h ×的矩阵。将A ，B 和C 分成形状w r ×，r h ×，
w h ×的子块。假定计算C 中一个子块需要执行等式K
次。这样得到的算法如图3所示。
图3 大规模矩阵乘法的算法实现
5 实验结果
实验平台是Intel core 2 duo E8400，4GB RAM ，Geforce GTX 260，操作系统是32位的Ubuntu 9.04。CUDA 工具包的版本是2.3。
首先考虑小规模的矩阵乘法，所有数据都已经拷贝到显存上，没有考虑主机和显卡的通信。我们记3.1节的算法为normal ，3.2节的算法为opt ，CUDA 工具包中CUBLAS 库的矩阵乘法记做cublas 。
从图4中可以看出，随着输入的规模的增大，三个实现的速度都是慢慢上升的。当输入规模大于2000时，三个算法的速度达到了峰值，且基本保持不变。normal 的峰值是60GFLOPS ，而opt 和cublas 的峰值是65GFLOPS 。而GTX 260的双精度峰值是67.068GFLOPS ，从而opt 的效率达到了97%。
图4 normal ，opt 以及cublas 的速度比较
我们分析opt 的性能，在小规模输入的情况下，由于数据不多，从显存读取数据到GPU 核心的时间没有被覆盖，所以速度比较慢。而当输入数据规模超过2000以后，计算量比较大，从而可以掩盖大部分的访问时间。但是仍然有少量的时间没有被计算重叠，这是由于片上的资源支持的block 数目太少，没有足够的线程切换来掩盖访存的时间。
其次考虑数据没有拷贝到显存中的情况。由于测试平台的限制，本文选取的测试矩阵的情况是，A 的规模是，B 的规模是，C 的规模是。对C 的分块大小是，对A 和B 的分块大小分别为和，测试结果如图5所示。在图5中，dgemm_kernel_NN_10是计算的内核，而memcpyDtoHAsync 和memcpyHtoDAsync 分别是从设备到主机和从主机到设备进行数据拷贝的原语。Stream_3将C 矩阵从主机端拷贝到设备端，Stream_2将A 矩阵和B 矩阵从主机端拷贝到设备端。Stream_1进行矩阵乘的计算。Stream_4将计算好的C 矩阵从设备端拷贝到主机端。从图5可以看出，GPU 计算使用的时间占到90%以上，而数据拷贝使用的时间不到10%。
图5 GPU 的运行时序图
(下转第149页)
图5不同故障条件下EAPS切换时长
4结束语
文中针对校园网用户对网络可靠性的电信级要求的现状，将目前校园网中所采用生成树协议来解决可靠性的方法与EAPS技术作了对比，描述了EAPS的工作机制。结合我校设备情况，引入利用EAPS技术来解决校园网的可靠性，对我校网络拓朴进行了
(上接第181页)
6结论
本文在GPU上设计和实现了一个高效的矩阵乘法。在Geforce GTX 260上，在数据已经拷贝到显存的前提下，双精度的实现的效率达到了97%。如果数据不能够一次全部的拷贝到显存中，通过数据调度，本文的算法拷贝数据的时间不超过总时间的10%。
参考文献
1 V olker Strassen. Gaussian Elimination is not Optimal. Numerische Mathe-matik, 1969,13(4):354－356. 重设置。事实证明，无论是设备宕机还是线路意外断开，环路的切换时间均能满足电信级要求，能保障网络业务的正常开展。进一步工作是关于EAPS 多环在大规模校园网、大型园区网中的应用及可靠性研究。
参考文献
1 胡中栋.图书馆网络的安全可靠性分析.信息安全,2007 (3):57－59.
2 庞雄琦.ESR的研究与实现.光通信技术,2005(11):39－41.
3 田晓宏,赵方.城域以太网发展综述.光通信技术,2008 (6):28
－30.
4 何强,张祖平.基于MSTP协议的一致性测试设计.计算机应
用,2007(27):27－29.
5 郭彦伟,郑建德.生成树协议与交换网络环路研究.厦门大学
学报(自然科学版),2006(5):301－304.
6 Etrame Network Ethernet automatic protection switching version1. 2003.
2 Goto K. Anatomy of High-Performance Matrix Multiplication. ACM Trans. on Mathematical Software, 2007,34(3):1－24.
3 Whaley RC, Petitet A and Dongarra J. Automated Empirical Optimization of Software and the Atlas Project. Parallel Computing, 2001,27(1-2):3－35.
4 Fatahalian K, Sugerman J, Hanrahan P. Understanding the Efficiency of GPU Algorithms for Matrix-matrix Multiplication. Proc. of the ACM SIGGRAPH/ EUROGRAPHICS Conference on Graphics Hardware (HWWS’04). New York: ACM Press, 2004. 133－137.
Applied Technique 应用技术149
实现稀疏矩阵（采用三元组表示）的基本运算实验报告 一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组； （3）输出a + b 的三元组； （4）输出 a * b 的三元组； 三实验内容: 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系: R={ Row , Col } Row ={
CreateSMatrix(&M) 操作结果：创建稀疏矩阵 M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在 操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在 操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在 操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在 操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在 操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T) 初始条件：稀疏矩阵M已经存在 操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q) 初始条件：稀疏矩阵M已经存在
数据结构课程设计报告 题目：十字链表成为存储结构，实现稀疏矩阵的求和运算 学生姓名:张旋 班级:软件三班学号:201213040304 指导教师: 吴小平
一、需求分析 1.问题描述： 要求：十字链表下的稀疏矩阵的加、转、乘的实现。 2.基本功能 实现十字链表下的转置，乘法，加法运算。 3.输入输出 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （5）构造函数进行稀疏矩阵的转置，并输出结果。 （6）退出系统。 二、概要设计 1.设计思路： 本实验要求在三元组，十字链表下实现稀疏矩阵的加、转、乘。首先要进行矩阵的初始化操作，定义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。 2.数据结构设计： 抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{ 数据对象：D={aij | i=1,2,…,m; j=1,2,..,n; aij∈Elemset, m和n分别称为矩阵的行数和列数。} 数据关系：R={Row,Col} Row={
经典题目 这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。 不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个二维数组。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果的那个4等于2*2+0*1： 右面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵： 矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢？因为交换后两个矩阵有可能不能相乘。为什么它又满足结合律呢？假设你有三个矩阵A、B、C，那么(AB)C和 A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（枚举所有的k和l）。 经典题目1 给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。 经典题目2 给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。 由于矩阵乘法具有结合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论：当n 为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、A^6、A^3的值即可。根据这里的一些结果，我们可以在计算过程中不断取模，避免高精度运算。 经典题目3 POJ3233 (感谢rmq) 题目大意：给定矩阵A，求A + A^2 + A^3 + ... + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。 这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。
矩阵基本运算及应用 牛晨晖 在数学中，矩阵是一个按照长方阵列排列的或集合。矩阵是高等代中的常见工具，也常见于统计分析等应用数学学科中。在物理学中，矩阵于电路学、、光学和中都有应用；中，制作也需要用到矩阵。矩阵的运算是领域的重要问题。将为简单矩阵的组合可以在理论和实际应用上简化矩阵的运算。在电力系统方面，矩阵知识已有广泛深入的应用，本文将在介绍矩阵基本运算和运算规则的基础上，简要介绍其在电力系统新能源领域建模方面的应用情况，并展望随机矩阵理论等相关知识与人工智能电力系统的紧密结合。 1矩阵的运算及其运算规则 1.1矩阵的加法与减法 1.1.1运算规则 设矩阵，， 则 简言之，两个矩阵相加减，即它们相同位置的元素相加减！ 注意：只有对于两个行数、列数分别相等的矩阵（即同型矩阵），加减法运算才有意义，即加减运算是可行的．
1.1.2运算性质 满足交换律和结合律 交换律； 结合律． 1.2矩阵与数的乘法 1.2.1运算规则 数乘矩阵A，就是将数乘矩阵A中的每一个元素，记为或．特别地，称称为的负矩阵． 1.2.2运算性质 满足结合律和分配律 结合律：(λμ)A=λ(μA)；(λ+μ)A =λA+μA． 分配律：λ(A+B)=λA+λB． 1.2.3典型举例 已知两个矩阵 满足矩阵方程，求未知矩阵． 解由已知条件知
? 1.3矩阵与矩阵的乘法 1.3.1运算规则 设，，则A与B的乘积是这样一个矩阵： (1) 行数与（左矩阵）A相同，列数与（右矩阵）B相同，即． (2) C的第行第列的元素由A的第行元素与B的第列元素对应相乘，再取乘积之和． 1.3.2典型例题 设矩阵 计算 解是的矩阵．设它为
1.稀疏矩阵运算器
数据结构课程设计任务书 针对本课程设计，完成以下课程设计任务： 1、熟悉系统实现工具和上机环境。 2、根据课程设计任务，查阅相关资料。 3、针对所选课题完成以下工作： （1）需求分析 （2）概要分析 （3）详细设计 （4）编写源程序 （5）静态走查程序和上机调试程序 4、书写上述文档和撰写课程设计报告。
3.课程设计报告目录
4.正文 （1）问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算频率。实现一个能进行稀疏矩阵基本运算的运算器。 （2）需求分析 本课程设计的稀疏矩阵运算器在visual studio 2013下运行调试成功，可以实现的功能有： 1.矩阵运算方式选择 2.根据提示输入相应数据 3.显示最终结果 使用的主要存储结构为三元组，并用三元组形式进行运算。所有参与运算数据类型为整形，因此输入的数据应为整形数据。为了节省存储空间使用三元组数据进行运算，可以通过多次扫描三元组数据来实现，即使用嵌套循环函数。输出结果为通常的阵列形式，因此使用了右对齐，保证输出形式的整齐。 （3）概要分析 本次课程设计中定义的结构体 typedef struct { int i, j;//矩阵元素所在行列 int v;//元素的值 }triple; typedef struct { triple data[MAXSIZE]; triple cop[MAXSIZE];//辅助数组 int m, n, t;//矩阵的行列数 }tripletable; Main函数调用子函数时输入1为调用 int Push_juzhen(int m, int n, int count)函数，可以实现矩阵相加功能 输入2为调用 int Dec_juzhen(int m, int n, int count)函数，可实现矩阵相减功能 输入3为调用 int Mul_juzhen()函数，可以实现矩阵相乘功能 （4）详细分析（流程图伪代码） 加法函数 int Push_juzhen(int m, int n, int count)//矩阵相加（行，列，矩阵数） { // p行，q列，s非零元素个数，v元素值 //ucount对数组下标计数的变量，与变量x实现多个矩阵相加 for (int c = 0; c < count; c++) { int x = 0; cout << "请输入第" << c + 1 << "个矩阵的非零元素个数" << endl; cin >> s; cout << "请依次输入非零元素所在行和列以及该非零元素的值并以空格隔开" << endl; for (; x< s; x++)//传递行列及元素值
2 矩阵 矩阵是学好线性代数这门课程的基础，而对于初学者来讲，对于矩阵的理解是尤为的重要；许多学生在最初的学习过程中感觉矩阵很难，这也是因为对矩阵所表示的内涵模糊的缘故。其实当我们把矩阵与我们的实际生产经济活动相联系的时候，我们才会发现，原来用矩阵来表示这些“繁琐”的事物来是多么的奇妙！于是当我们对矩阵产生无比的兴奋时，那么一切问题都会变得那么的简单! 2.1 知识要点解析 2.1.1 矩阵的概念 1．矩阵的定义 由m×n 个数),,2,1;,,2,1(n j m i a ij 组成的m 行n 列的矩形数表 mn m m n n a a a a a a a a a A 21 22221 11211 称为m×n 矩阵，记为n m ij a A )( 2．特殊矩阵 （1）方阵：行数与列数相等的矩阵； （2）上（下）三角阵：主对角线以下（上）的元素全为零的方阵称为上（下） 三角阵； （3）对角阵：主对角线以外的元素全为零的方阵； （4）数量矩阵：主对角线上元素相同的对角阵； （5）单位矩阵：主对角线上元素全是1的对角阵，记为E ； （6）零矩阵：元素全为零的矩阵。 3．矩阵的相等 设mn ij mn ij b B a A )(; )( 若 ),,2,1;,,2,1(n j m i b a ij ij ，则称A 与B 相等，记为A=B 。 2.1.2 矩阵的运算
1．加法 （1）定义：设mn ij mn ij b B A A )(,)( ，则mn ij ij b a B A C )( （2）运算规律 ① A+B=B+A ； ②（A+B ）+C =A +（B+C ） ③ A+O=A ④ A +（-A ）=0， –A 是A 的负矩阵 2．数与矩阵的乘法 （1）定义：设,)(mn ij a A k 为常数，则mn ij ka kA )( （2）运算规律 ① K (A+B ) =KA+KB , ② (K+L )A =KA+LA , ③ (KL ) A = K (LA ) 3．矩阵的乘法 （1）定义：设.)(,)(np ij mn ij b B a A 则 ,)(mp ij C C AB 其中 n k kj ik ij b a C 1 （2）运算规律 ①)()(BC A C AB ；②AC AB C B A )( ③CA BA A C B )( （3）方阵的幂 ①定义：A n ij a )( ，则K k A A A ②运算规律：n m n m A A A ；mn n m A A )( （4）矩阵乘法与幂运算与数的运算不同之处。 ①BA AB ②;00,0 B A AB 或不能推出 ③k k k B A AB )( 4．矩阵的转置 （1）定义：设矩阵A =mn ij a )(，将A 的行与列的元素位置交换，称为矩阵A 的转置，记为nm a A ji T )( ， （2）运算规律 ①;)(A A T T ②T T T B A B A )(； ③;)(T T KA kA ④T T T A B AB )(。
矩阵基本运算及应用 201700060牛晨晖 在数学中，矩阵是一个按照长方阵列排列的复数或实数集合。矩阵是高等代数学中的常见工具，也常见于统计分析等应用数学学科中。在物理学中，矩阵于电路学、力学、光学和量子物理中都有应用；计算机科学中，三维动画制作也需要用到矩阵。矩阵的运算是数值分析领域的重要问题。将矩阵分解为简单矩阵的组合可以在理论和实际应用上简化矩阵的运算。在电力系统方面，矩阵知识已有广泛深入的应用，本文将在介绍矩阵基本运算和运算规则的基础上，简要介绍其在电力系统新能源领域建模方面的应用情况，并展望随机矩阵理论等相关知识与人工智能电力系统的紧密结合。 1矩阵的运算及其运算规则 1.1矩阵的加法与减法 1.1.1运算规则 设矩阵，， 则
简言之，两个矩阵相加减，即它们相同位置的元素相加减！ 注意：只有对于两个行数、列数分别相等的矩阵（即同型矩阵），加减法运算才有意义，即加减运算是可行的． 1.1.2运算性质 满足交换律和结合律 交换律； 结合律． 1.2矩阵与数的乘法 1.2.1运算规则 数乘矩阵A，就是将数乘矩阵A中的每一个元素，记为或． 特别地，称称为的负矩阵． 1.2.2运算性质 满足结合律和分配律 结合律：(λμ)A=λ(μA)；(λ+μ)A =λA+μA． 分配律：λ(A+B)=λA+λB．
已知两个矩阵 满足矩阵方程，求未知矩阵． 解由已知条件知 1.3矩阵与矩阵的乘法 1.3.1运算规则 设，，则A与B的乘积是这样一个矩阵： (1) 行数与（左矩阵）A相同，列数与（右矩阵）B相同，即 ． (2) C的第行第列的元素由A的第行元素与B的第列元素对应相乘，再取乘积之和．
专业课程设计I报告（2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号
指导教师成绩评定表
附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主
控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输
科技大学 数据结构课程设计说明书 题目：稀疏矩阵运算器设计 学生： 学号： 专业：计算机科学与技术 班级：计09-1班 指导教师：月峰 2011 年 6 月 24 日
稀疏矩阵运算器设计 摘要 摘要：设计一稀疏矩阵运算器。实现转置，相加，相乘的功能。用“带行逻辑信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相转置、相加和相乘的运算，采用分级的设计方法，分别设计出转置、加、乘运算器的子程序，相加运算时只要依次扫描两矩阵的行号和列号，若相等则相加后存入结果矩阵，不等时则存入较小的。相减运算与相加运算相同，同样比较两矩阵的行号和列号，只是不等时，若第一个小，则存入第一个的元素，若第二个小，则存入其相反数。相乘运算要先判断两矩阵能否相乘。通过给顶的行号和列号找出原矩阵对应的元素值。当在三元组表示中找到时返回其元素值，找不到时，说明该位置为0，因此返回0。然后利用该函数计算出C的行号i和列号j 处的元素值，若该值不为0，则存入矩阵，否则不存入。通过实验表明本程序能够进行稀疏矩阵的相加，相减，相乘运算。具备矩阵的加、减、乘功能。 关键词：转置运算器；相加运算器；相乘运算器
目录 稀疏矩阵运算器设计........................................................ I 摘要................................................................... II 第一章需求分析. (1) 第二章概要设计 (2) 第三章设计步骤 (6) 3.1 函数说明 (6) 3.2 设计步骤 (7) 第四章设计理论分析方法 (20) 4.1 算法一：矩阵转置 (20) 4.2 算法二：矩阵加法 (20) 4.3 算法三：矩阵乘法 (21) 第五章程序调试 (23) 第六章心得体会 (25) 参考文献 (26)
分块矩阵乘法的例子 例 1 用分块法计算,AB 其中 00 51 2414 21,5 31001200 2 0-???? ? ?== ? ? ? ?-? ?? ? A B . 解 B A,如上分块， ???? ??=2221 1211 A A A A A ， ??? ? ??=2322 21 131211 B B B B B B B ， 其中 111221224 21(0,0),(5), ,,0 12????==== ? ?-?? ?? A A A A ()()()0,20,0,01,1342,51232221131211===??? ? ??-=???? ??=???? ??=B B B B B B ； 令==C AB ??? ? ??232221 131211 C C C C C C ，其中 =+=2112111111B A B A C )0()0)(5(51)00(=+??? ? ??， =+=2212121112B A B A C )00(()()()1002051342=+???? ??， =+=2312131113B A B A C )0()0)(5(01)00(=+???? ??-， =+=2122112121B A B A C ??? ? ??-=???? ??+???? ?????? ??-514)0(21511024， =+=2222122122B A B A C ???? ??-=???? ??+???? ?????? ??-332014)20(2113421024， =+=2322132123B A B A C ??? ? ??-=???? ??+???? ??-???? ??-04)0(21011024.
Born T o Win 考研数学线性代数之矩阵的乘法运算 任意两个矩阵不一定能够相乘，即两个矩阵要相乘必须满足的条件是：只有当第一个矩阵A 的列数与第二个矩阵B 的行数相等时A ×B 才有意义。一个m ×n 的矩阵A 左乘一个n ×p 的矩阵B ，会得到一个m ×p 的矩阵C 。左乘：又称前乘，就是乘在左边(即乘号前)，比如说,A 左乘E 即AE 。 一个m 行n 列的矩阵与一个n 行p 列的矩阵可以相乘，得到的结果是一个m 行p 列的矩阵，其中的第i 行第j 列位置上的数为第一个矩阵第i 行上的n 个数与第二个矩阵第j 列上的n 个数对应相乘后所得的n 个乘积之和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果矩阵的那个4（结果矩阵中第二（i ）行第二（j)列）= 2（第一个矩阵第二(i)行第一列）*2（第二个矩阵中第一行第二(j)列） + 0（第一个矩阵第二(i)行第二列）*1（第二个矩阵中第二行第二(j)列）： 矩阵乘法的两个重要性质：一，矩阵乘法满足结合律； 二，矩阵乘法不满足交换律。为什么矩阵乘法不满足交换律呢？这是由矩阵乘法定义决定的。因为矩阵AB=C ，C 的结果是由A 的行与B 的列相乘和的结果；而BA=D ，D 的结果是由B 的行与A 的列相乘和的结果。显然，得到的结果C 和D 不一定相等。同时，交换后两个矩阵有可能不能相乘。 因为矩阵乘法不满足交换律，所以矩阵乘法也不满足消去律。即由AB=AC 是得不到B=C 的，这是因为()AB AC A B C O =?-=是得不到A=O 或B-C=O 即B=C.例 111000010A B ????=≠=≠ ? ?-????0， 但0000AB O ??== ??? 那么由AB=O 一定得不到A=O 或B=O 吗？回答是否定的。比如A 是m ×n 阶矩阵，B 是n ×s 阶矩阵，若A 的秩为n ，则AB=O ，得B=O ；若B 的秩为m ，则AO ，得A=O.为什么吗？原因会在有关齐次线性方程组的文章里进行讲解.
数据结构----稀疏矩阵运算器课程设计 目录 稀疏矩阵运算器设计............................................................................................ I 摘要................................................................................................................ ... II 第一章需求分析 (1) 第二章概要设计 (2) 第三章设计步骤 (6) 3.1 函数说明 (6) 3.2 设计步骤 (7) 第四章设计理论分析方法 (20) 4.1 算法一：矩阵转置.....................................................................
20 4.2 算法二：矩阵加法..................................................................... 20 4.3 算法三：矩阵乘法 (21) 第五章程序调试 (23) 第六章心得体会 (25) 参考文献 (26) 第一章需求分析 1．稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。
2．以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，求逆，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 3．演示程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。 4．由题目要求可知：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。 5．程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。 6．在用三元组表示稀疏矩阵时，相加、乘积和相减所得结果矩阵应该另生成；矩阵求逆时，为了算法方便，使用二维数组存放。 7．程序在VC6.0环境下设计。 程序执行的命令为：1.稀疏矩阵转置; 2.稀疏矩阵加法; ;3. 稀疏矩阵乘法; 4.退出 的工作。 第二章概要设计 1．抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{ 数据对象：D={a|i=1,2,…,m; j=1,2,…,n;
第六节．矩阵乘法的法则 教学目标： （1）通过几何变换，使学生理解矩阵乘法不满足交换律（但并不是绝对的）。 （2）通过实例，了解矩阵的乘法满足结合律。 教学重点：理解矩阵乘法不满足交换律。 教学难点：从图形变换的角度理解矩阵的乘法不满足交换律。 教学过程： 一、引入：对上节课的练习的讨论： 已知三角形ABC 的三个顶点的坐标分别为：A （0，0），B （2，0），C （2， 2），先将三角形作以原点为中心的反射变换（变换矩阵为?? ?? ??--1001），再以x 轴为基准，将所得图形压缩到原来的一半（变换矩阵为????????21001），试求：（1）这连续两次变换所对应的变换矩阵U ； 问：U=??????--1001??????? ?21001=????????--21001 U=????????21001??????--1001=??? ?????--21001 问题：矩阵的乘法是否满足交换律呢？ 2、例题 例1．已知矩阵A 、B ，计算AB 及BA ，并比较他们是否相同，能否从几何变换的角度给予解释？ （1）A=??????2001，B=????? ?-0110； （2）A=??? ?????21001，B=??????1003。 解：（1）AB=??????2001??????-01 10=??????-0210，BA=??????-0110??????2001=?? ????-0120 显然，AB ≠BA 。 从几何变换的角度，AB 表示先作反射变换（变换矩阵为B ），后作伸缩变换（变换矩阵为A ）；而BA 表示先作伸缩变换（变换矩阵为A ），后作反射变换（变换矩阵为B ）。当连续进行一系列变换时，交换变换次序得到的结果，一般说会不相同。仍以正方形（顶点分别为A(0,0)，B(1,0)，C(1,1)，D(0,1)）为例，如下图：
数据结构 课程设计说明书题目: 稀疏矩阵的运算 院系：计算机科学与工程学院 专业班级：计算机10-**班 学号： 201030**** 学生姓名： ****** 指导教师： ****** 2011年 12 月 28 日
安徽理工大学课程设计（论文）任务书 计算机科学与工程学院 2011年 11 月 8 日
安徽理工大学课程设计（论文）成绩评定表
目录 1 问题描述 (1) 2 需求分析 (1) 3 总体设计 (2) 3.1 Matrix结构的定义 (2) 3.2 系统流程图 (3) 4 详细设计 (4) 4.1 “菜单”界面 (4) 4.2 建立矩阵 (4) 4.3 显示矩阵 (6) 4.4 矩阵的转置 (7) 4.5 矩阵的加法运算 (8) 4.6 矩阵的减法运算 (9) 4.7 矩阵的乘法运算 (9) 5 程序运行 (11) 5.1 输入矩阵 (11) 5.2 矩阵转置 (11) 5.3 矩阵加法 (12) 5.4 矩阵减法 (12) 5.5 矩阵乘法 (12) 5.6 退出及错误提示 (13) 6 总结 (13) 参考文献 (14)
1 问题描述 (1)题目内容：设计稀疏矩阵运算系统实现两个稀疏矩阵的加法、减法、乘法以 及转置操作。 (2)基本要求： ①存储结构选择三元组存储方式； ②实现一个稀疏矩阵的转置运算； ③实现两个稀疏矩阵的加法运算； ④实现两个稀疏矩阵的减法运算； ⑤实现两个稀疏矩阵的乘法运算。 (3)设计目的：通过本次课程设计，了解稀疏矩阵的一些基本运算操作，并通过 相关的程序代码实现。 2 需求分析 经过本次的课程设计，我认为稀疏矩阵运算系统主要实现的功能如下：(1)建立矩阵：只有先建立了矩阵，才能够对矩阵进行运算操作，包括建立矩阵 A和矩阵B； (2)转置运算操作：对矩阵A或者矩阵B进行转置运算，输出相应的转置矩阵； (3)四则运算操作：该步骤由两个矩阵同时参与，对其进行加法运算(A+B)、减 法运算(A-B)以及乘法运算(A*B和B*A)； (4)退出：当做完矩阵的运算操作之后，就可以点击它退出该界面。 在这次设计中用到了一些变量和函数，例如：void Display(Matrix M)；int Max(int i,int j)；Matrix Zero(Matrix M)等，下面会做进一步详细的介绍。
第二章 矩阵及其运算测试题 一、选择题 1.下列关于矩阵乘法交换性的结论中错误的是（ ）。 (A)若A 是可逆阵，则1A -与1A -可交换； (B)可逆矩阵必与初等矩阵可交换； (C)任一n 阶矩阵与n cE 的乘法可交换，这里c 是常数； (D)初等矩阵与初等矩阵的乘法未必可交换。 2.设n (2n ≥)阶矩阵A 与B 等价，则必有（ ） (A) 当A a =（0a ≠）时，B a =； (B)当A a =（0a ≠）时，B a =-； (C) 当0A ≠时，0B =； (D)当0A =时，0B =。 3.设A 、B 为方阵，分块对角阵00A C B ??= ??? ，则* C =( )。 (A) **00 A B ?? ??? (B) **||00 ||A A B B ?? ??? (C) **||00||B A A B ?? ??? (D) **||||0 0||||A B A A B B ?? ??? 4.设A 、B 是n (2n ≥)阶方阵，则必有（ ）。 (A)A B A B +=+ (B)kA k A = (C) A A B B =-g (D) AB A B = 5.设4阶方阵 44(),()||,ij A a f x xE A ?==-其中E 是4阶单位矩阵，则()f x 中3 x 的系数为（ ）。 (A)11223344()a a a a -+++ (B)112233112244223344113344a a a a a a a a a a a a +++ (C) 11223344a a a a (D)11223344a a a a +++ 6.设A 、B 、A B +、11A B --+均为n 阶可逆矩阵，则1()A B -+为( )。 (A) 11A B --+ (B) A B + (C) 111()A B ---+ (D)11111 ()B A B A -----+
一、矩阵的线性运算 定义1 设有两个矩阵和,矩阵与的和记作, 规定为 注：只有两个矩阵是同型矩阵时，才能进行矩阵的加法运算. 两个同型矩阵的和，即为两个矩阵对应位置元素相加得到的矩阵. 设矩阵记 , 称为矩阵的负矩阵, 显然有 . 由此规定矩阵的减法为 . 定义2 数与矩阵A的乘积记作或, 规定为 数与矩阵的乘积运算称为数乘运算. 矩阵的加法与矩阵的数乘两种运算统称为矩阵的线性运算. 它满足下列运算规律：设都是同型矩阵，是常数，则 (1) (2) ; (3) (4) (5) (6) (7) (8) 注：在数学中，把满足上述八条规律的运算称为线性运算. 二、矩阵的相乘 定义3设
矩阵与矩阵的乘积记作, 规定为 其中，( 记号常读作左乘或右乘. 注: 只有当左边矩阵的列数等于右边矩阵的行数时, 两个矩阵才能进行乘法运算. 若，则矩阵的元素即为矩阵的第行元素与矩阵的第列对应元素乘积的和. 即 . 矩阵的乘法满足下列运算规律(假定运算都是可行的)： （1） （2） （3） （4） 注: 矩阵的乘法一般不满足交换律, 即 例如, 设则 而 于是且 从上例还可看出: 两个非零矩阵相乘, 可能是零矩阵, 故不能从必然推出 或 此外, 矩阵乘法一般也不满足消去律,即不能从必然推出例如, 设 则 但 定义4如果两矩阵相乘, 有
则称矩阵A与矩阵B可交换.简称A与B可换. 注：对于单位矩阵, 容易证明 或简写成 可见单位矩阵在矩阵的乘法中的作用类似于数1. 更进一步我们有 命题1设是一个n阶矩阵，则是一个数量矩阵的充分必要条件是与任何n阶矩阵可换。 命题2设均为n阶矩阵，则下列命题等价： （1） （2） （3） （4） 三、线性方程组的矩阵表示 设有线性方程组 若记 则利用矩阵的乘法, 线性方程组(1)可表示为矩阵形式： (2) 其中矩阵称为线性方程组(1)的系数矩阵. 方程(2)又称为矩阵方程. 如果是方程组(1)的解, 记列矩阵 则 ，
选修4－2矩阵与变换 2.3.1 矩阵乘法的概念 编写人： 编号：008 学习目标 1、 熟练掌握二阶矩阵与二阶矩阵的乘法。 2、 理解两个二阶矩阵相乘的结果仍然是一个二阶矩阵，从几何变换的角度来看，它表 示的是原来两个矩阵对应的连续两次变换。 学习过程： 一、预习： （一）阅读教材，解决下列问题： 问题：如果我们对一个平面向量连续实施两次几何变换,结果会是怎样?举例说明。 归纳1：矩阵乘法法则: 归纳2：矩阵乘法的几何意义： （二）初等变换：在数学中，一一对应的平面几何变换都可看做是伸压、反射、旋转、切变变换的一次或多次复合，而伸压、反射、切变变换通常叫做初等变换，对应的矩阵叫做初等变换矩阵。 练习 、.?? ??????????10110110=（ ） A 、???? ??1110 B 、??????1011 C 、? ? ? ???0111 D 、??????0110 、已知矩阵X 、M 、N,若M =?? ? ???--1111, N =??????--3322，则下列X 中不满足:XM=N ,的一个 是（ ） A 、X =???? ??--2120 B 、X =??????--1211 C 、X =??????--3031 D 、X =? ? ? ???-3053
二、课堂训练： 例1．（1）已知A= 11 22 11 22 ?? ? ? ? ? ?? ，B= 11 22 11 22 ?? - ? ? ? - ? ?? ,计算AB （2）已知A= 10 02 ?? ? ?? ，B= 14 23 ?? ? - ?? ，计算AB,BA (3)已知A= 10 00 ?? ? ?? ，B= 10 01 ?? ? ?? ，C= 10 02 ?? ? ?? 计算AB,AC 例2、已知梯形ABCD，其中A(0,0),B(3,0),C(2,2),D(1,2),先将梯形作关于x轴的反射变换，再将所得图形绕原点逆时针旋转0 90 (1)求连续两次变换所对应的变换矩阵M (2)求点A,B,C,D在 M T作用下所得到的结果 (3)在平面直角坐标系内画出两次变换对应的几何图形，并验证(2)中的结论。
专业课程设计I报告（ 2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号
指导教师成绩评定表
附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。
2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）稀疏矩阵的转置： 此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始
稀疏矩阵 一、问题描述 假若在n m ?阶中，有t 个元素不为零，令n m t ?=δ称为矩阵的稀疏因子。通常认为≤δ0.05时称为稀疏矩阵。稀疏矩阵的研究大大的减少了数据在计算机中存储所需的空间，然而，它们的运算却与普通矩阵有所差异。通过本次实验实现稀疏矩阵的转置、加法和乘法等多种运算。 二、基本要求 1、稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出; 2、编写算法，完成稀疏矩阵的转置操作； 3、编写算法，完成对两个具有相同行列数的稀疏矩阵进行求和操作； 4、编写算法，对前一矩阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。 三、测试数据 1、转置操作的测试数据： ??????? ? ?00200013000010020100 2、相加操作的测试数据： ??????? ? ?002000130000100 20100 ??????? ??00200010000210030300 3、相乘操作的测试数据： ?????? ? ??000000030040 0021 ??????? ??001002000021 四、算法思想 1、三元组结构类型为Triple ，用i 表示元素的行，j 表示元素的列，e 表示元素值。稀疏矩阵的结构类型为TSMatrix ，用数组data[]表示三元组，mu 表示行数，nu 表示列数，tu 表示非零元个数。 2、稀疏矩阵转置的算法思想 将需要转置的矩阵a 所有元素存储在三元组表a.data 中，按照矩阵a 的列序来转置。
为了找到a的每一列中所有非零元素，需要对其三元组表a.data扫描一遍，由于a.data 是以a的行需序为主序来存放每个非零元的，由此得到的就是a的转置矩阵的三元组表，将其储存在b.data中。 3、稀疏矩阵相加的算法思想 比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。 4、稀疏矩阵相乘的算法思想 两个相乘的矩阵为M与N，对M中每个元素M.data[p](p=1,2,…,M.tu),找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.data[q].v 的乘积，又T(i,j)=∑M(i,k)×N(k,j),乘积矩阵T中每个元素的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是T[i][j]中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去。 五、模块划分 1、Status CreateM(TSMatrix *M, int a[],int row, int col)，创立三元组； 2、void PrintM(TSMatrix M)，按数组方式输出； 3、void PrintM3(TSMatrix M)，按三元组方式输出； 4、Status TransposeSMatrix(TSMatrix M, TSMatrix *T)，稀疏矩阵的转置； 5、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵加法； 6、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵相乘； 7、main(),主函数。 六、数据结构//(ADT) 1、三元组结构类型 typedef struct { int i,j; ElemType e; } Triple; 2、稀疏矩阵 typedef struct { Triple data[MAXSIZE+1];