精华内容
下载资源
问答
  • 稀疏矩阵相乘
    千次阅读
    2021-01-05 15:23:48

    这是一个用pytorch操作稀疏矩阵的实例

    在您需要操作很大的矩阵,例如100000100000大小,电脑存不下去的时候,可以考虑使用稀疏矩阵进行计算。注意pytorch只允许sparse和dense操作,不允许sparse和sparse相乘。在这个例子中,100000100000的矩阵和1000001000的矩阵相乘,结果是1000001000

    from scipy.sparse import csc_matrix,find
    import numpy as np
    import torch
    data1 = np.ones(100000*100)
    row = np.ones(100000*100)
    col = np.ones(100000*100)
    for i in range(100000):
        for j in range(100):
            row[i*100+j]=i
            col[i*100+j]=j
    index = np.vstack((row, col))
    index = torch.LongTensor(index)
    val = data1
    val = torch.FloatTensor(val)
    z = torch.ones(100000, 1000)
    y = torch.sparse.FloatTensor(index, val, (100000, 100000))
    x = torch.matmul(y,z)
    print(x.shape)
    #X = csc_matrix((data1, (row, col)), shape=(100000, 100000))
    #print(X)```
    
    更多相关内容
  • 某福建大三本的某三本学院的数据结构作业,题号对应清华殷人昆版。有一些可能参考借鉴了网上的代码,大体应该都能运行(尤其是大作业),仅供参考
  • 使用C语言以实现稀疏矩阵之间相乘的简单矩阵运算,亦可以使用于非稀疏矩阵之间的矩阵乘法运算,因为机制是一样的,只是因为稀疏矩阵在算法设计中比较特殊,故而特意加以区分
  • 稀疏矩阵相乘包含1.目的 2.设计要求 3.概要设计 4.模块设计 5.详细设计 6.测试分析 7.设计总结
  • 实现稀疏矩阵相乘C/C++

    万次阅读 多人点赞 2016-10-14 20:34:44
    实现稀疏矩阵相乘C/C++ 1、问题描述:已知稀疏矩阵A(m1,n1)和B(m2,n2),求乘积C(m1,n2)。 A=|3 0 0 7| B=|4 1| C=|12 17|  |0 0 0 -1| |0 0| |0 -2|  |0 2 0 0| |1 -1| |0 0|  

    实现稀疏矩阵相乘C/C++

    1、问题描述:已知稀疏矩阵A(m1,n1)和B(m2,n2),求乘积C(m1,n2)。
    A=|3 0 0  7|    B=|4  1|   C=|12 17|
         |0 0 0 -1|         |0  0|        |0    -2|
         |0 2 0  0|         |1 -1|        |0      0|
                                 |0   2|
    A、B、C的三元组表示法分别为:
    A
     ijv
    1112
    2147
    324-1
    4322
    B
     ijv
    1114
    2121
    3311
    432-1
    5422
    C
     ijv
    11112
    21217
    322-2
    2、解决思路:由矩阵乘法规则可知C(i,j) = A(i,1)*B(1,j)+A(i,2)*B(2,j)+....+A(i,n)*B(n,j),即C(i,j)为A的第i行与B的第j列非零元素乘积之和。设置累加器temp[B的列值]保存C矩阵每行的值,结束后将temp中的值赋给C矩阵。
    3、定义数据结构:
    3.1、稀疏矩阵中节点的定义:
    //定义三元组表的节点
    typedef struct{
     int i,j;
     int v;
    }SPNode;
    i,j为行列值,v为此位置的数值。
    3.2、稀疏矩阵的定义:
    //定义三元组表
    typedef struct{
     int mu,nu,tu;
     SPNode data[SMAX];
    }SPMatrix;
    mu为矩阵行数,nu为矩阵列数,tu为矩阵中非零元素的个数。
    4、具体实现:
    为了便于B.data寻找第k行第一个非零元素,在此引入num和rpot两个内容。num[k]表示矩阵B中第k行非零元素的个数;rpot[k]表示第k行的第一个非零元素在B.data中的位置。
    rpot[1] = 0;
    rpot[k] = rpot[k-1]+num[k-1];
    矩阵B中的num与rpot的值
    col1234
    num[col]2020
    rpot[col]0224
    4.1、初始化。清理一些单元,准备按行顺序存放乘积矩阵。
    4.2、求B的num与rpot。
    4.3、做矩阵的乘法。
    5、代码的具体实现:
    /*
     *进行两个稀疏矩阵之间的乘法
    */
    #include<stdio.h>
    #include<malloc.h>
    #define SMAX 1024
    //定义三元组表的节点
    typedef struct{
     int i,j;
     int v;
    }SPNode;
    //定义三元组表
    typedef struct{
     int mu,nu,tu;
     SPNode data[SMAX];
    }SPMatrix;
    //进行两个稀疏矩阵之间的乘法,返回值为乘积矩阵
    SPMatrix * MulSMatrix(SPMatrix *A,SPMatrix *B){
      SPMatrix *C;
      int p,j,q,i,r,k,t;
      //用于结果的暂存
      int temp[B->nu+1];
      int num[B->mu+1],rpot[B->mu+1];
      C = (SPMatrix*)malloc(sizeof(SPMatrix));
      if(C==NULL){
        printf("申请内存空间失败!\n");
        return NULL;
      }
      //A的列值与B的行值不相等时
      if(A->nu!=B->mu) return NULL;
      C->mu = A->mu;
      C->nu = B->nu;
      //当A或B中的非零元素为0时
      if(A->tu*B->tu==0){
        C->tu = 0;
        return C;
      }
      //计算B矩阵中每行非0元素的个数
      for(i = 1;i<=B->mu;i++)
        num[i] = 0;
      for(i = 0;i<B->tu;i++)
        num[B->data[i].i]++;
      rpot[1] = 0;
      //计算B矩阵中每行首位非0元素的位置
      for(i = 2;i<=B->mu;i++)
        rpot[i] = rpot[i-1]+num[i-1];
       r = 0;//记录当前C矩阵中非0元素的个数
       p = 0;//指示当前A矩阵中非零元素的位置
       //进行矩阵的乘积运算
       for(i = 1;i<=A->mu;i++){
           //将Cij的累加器初始化
            for(j = 1;j<=B->nu;j++)
                temp[j] = 0;
                //求Cij第i行的元素集合
          while(i==A->data[p].i){
            k = A->data[p].j;//获取A矩阵中第p个非零元素的列值
          //确定B中的k行的非零元素在B.data中的下限位置
            if(k<B->mu) t = rpot[k+1];
            else t = B->tu;
            //将B中第k行的每一列非零元素与A中非零元素记录到累加器中
            for(q = rpot[k];q<t;q++){
                j = B->data[q].j;
                temp[j] += A->data[p].v*B->data[q].v;
            }
           p++;
          }
          //将第i行的结果赋值给C矩阵
          for(j = 1;j<=B->nu;j++){
            if(temp[j]!=0){
                C->data[r] = {i,j,temp[j]};
                r++;
            }
          }
       }
       C->tu = r;
       return C;
    }
    int main(){
        SPMatrix *A,*B,*C;
        int i;
        A = (SPMatrix*)malloc(sizeof(SPMatrix));
        B = (SPMatrix*)malloc(sizeof(SPMatrix));
        printf("请输入A矩阵的行列值与非零元素");
        scanf("%d %d %d",&A->mu,&A->nu,&A->tu);
        printf("请输入A矩阵的非零元素值:\n");
        for(i = 0;i<A->tu;i++)
            scanf("%d %d %d",&A->data[i].i,&A->data[i].j,&A->data[i].v);
        printf("请输入B矩阵的行列值与非零元素");
        scanf("%d %d %d",&B->mu,&B->nu,&B->tu);
        printf("请输入B矩阵阵的非零元素值:\n");
        for(i = 0;i<B->tu;i++)
            scanf("%d %d %d",&B->data[i].i,&B->data[i].j,&B->data[i].v);
        C = MulSMatrix(A,B);
        printf("C->nu:%d,C->mu:%d,C->tu:%d\n",C->mu,C->nu,C->tu);
        for(i = 0;i<C->tu;i++)
            printf("i:%d,j:%d,v:%d\n",C->data[i].i,C->data[i].j,C->data[i].v);
        delete A,B,C;
     return 0;
    }
    
    5、算法的时间复杂度:
    5.1、求num的时间复杂度为:O(2*B->nu)
    5.2、求rpot的时间复杂度为:O(B->mu)
    5.3、求temp的时间复杂度为:O(A->mu*B->nu)
    5.4、求C中所有元素的时间复杂度为:O(A->tu*B->tu/B->mu)





    展开全文
  • 写的不是很好 用类写的 不过要加上模板就好了
  • 稀疏矩阵相乘

    千次阅读 2017-11-14 18:59:57
    对于用三元组实现稀疏矩阵相乘的算法,首先构造一个结构体,结构图体中应该有五个量。其中第一个量是表示稀疏矩阵常用的三元组,定义如下:typedef struct{ int i, j; //该非零元素行列下标 ElemType e; }Triple; /...

    对于用三元组实现稀疏矩阵相乘的算法,首先构造一个结构体,结构图体中应该有五个量。其中第一个量是表示稀疏矩阵常用的三元组,定义如下:

    typedef struct{
        int i, j;         //该非零元素行列下标
        ElemType e;
    }Triple;
    /*--------稀疏矩阵的三元组顺序表存储表示-------*/

    下面是结构体的完整定义:

    typedef struct {
        Triple data[MAXSIZE+1];   //三元组
        int num[MAXRC];           //一个数组记录矩阵每一行非零元个数
        int rpos [MAXRC+1];       //一个数组记录第一个非零元个数
        int mu, nu, tu;           //
        .
    
    }RLSMatrix;

    定义好结构体之后,我们要对结构体表示的矩阵实现矩阵相乘算法(注释已经写好了):

    Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
        if (M.nu != N.mu)return ERROR;
        Q.mu = M.mu;
        Q.nu = N.nu;
        Q.tu = 0;
        if (M.tu*N.tu != 0) {                               //  说明Q是非零矩阵
                int ctemp[100];                             // 设置累加器ctemp数组
                int brow; 
                for (int col = 1; col < M.mu; ++col) {      //将表示M,N每行元素非零元个数的数组初始化
                    M.num[col] = 0; N.num[col] = 0; }
                for (int t = 1; t <= M.tu; ++t) {
                    ++M.num[M.data[t].i];
    
                }for (int t = 1; t <= N.tu; ++t) {
                    ++N.num[N.data[t].i];
    
                }                                           //求出M,N每行元素非零元个数
                M.rpos[1] = 1;
                N.rpos[1] = 1;
                for (int col = 2; col <= M.mu; ++col) {
                    M.rpos[col] = M.rpos[col - 1] + M.num[col - 1];
                    N.rpos[col] = N.rpos[col - 1] + N.num[col - 1];
                }                                            //通过计算得出每行第一个非零元在三元组中的位置并将其放入rpos数组
            for (int arow = 1;arow<=M.mu;arow++) {
    
                for (int j = 1; j <= N.nu; j++) ctemp[j] = 0;//初始化累加器
                Q.rpos[arow] = Q.tu + 1;
                int tp;
                if (arow < M.mu)tp = M.rpos[arow + 1];
                else { tp = M.tu + 1; }
                for (int p = M.rpos[arow]; p < tp; ++p) {            
                    brow = M.data[p].j;                         //找到每行第一个非零元的列下标,此下标在N中对应一个行号
                    int t;
                    if (brow < N.mu)t = N.rpos[brow + 1];
                    else { t = N.tu + 1; }                      //如果对应行不超过N的行数,设置t为下一行首字母下标,否则,则设置t为最后一个非零元下标
                    for (int q = N.rpos[brow]; q < t; ++q) {
                        int ccol = N.data[q].j;
                        ctemp[ccol]+= M.data[p].e*N.data[q].e;  //在不超过t的范围内做对应乘和累加操作
    
                    }
                }
                for(int ccol = 1;ccol<=Q.nu;++ccol) {
                    if (ctemp[ccol]) {
                        if (++Q.tu > MAXSIZE)return ERROR;      //将该行非零元放入Q的三元组
                        Q.data[Q.tu].i = arow;
                        Q.data[Q.tu].j = ccol;
                        Q.data[Q.tu].e=ctemp[ccol];
                    }
                }
            }
        }
        return OK;
    }

    之后在主函数中初始化M和N,并进行计算

    int main(){
        RLSMatrix *a, *b, c;
        a = (RLSMatrix*)malloc(sizeof(RLSMatrix));
        b = (RLSMatrix*)malloc(sizeof(RLSMatrix));
        cout<<"请输入A矩阵的行列式和非零元素的值"<<endl;
        cin>> a->mu >> a->nu >> a->tu;                                     
        for (int i = 1; i <=a->tu; i++)
            cin >> a->data[i].i >> a->data[i].j >> a->data[i].e;
        cout << "请输入B矩阵的行列式和非零元素的值" << endl;
        cin >> b->mu >> b->nu >> b->tu;
        for (int i = 1; i <= b->tu; i++)
            cin >> b->data[i].i >> b->data[i].j >> b->data[i].e;
    
        if (!MultSMatrix(*a, *b, c)) {
            cout << "矩阵无法相乘" <<endl;
        }
        else {
            cout<<"结果如下"<<endl;
        }
        cout <<c.mu<<"\t"<<c.nu<<"\t"<<c.tu;
        for (int i = 1; i <= c.tu; i++) {
            cout << "\n" << c.data[i].i << "\t" << c.data[i].j << "\t" << c.data[i].e;
        }
        free(a); free(b);
        a = NULL;
        b = NULL;
        system("pause");
    }

    这样就完成了稀疏矩阵相乘的操作,也可以自己根据需要修改主函数

    展开全文
  • 稀疏矩阵相乘-Python版

    千次阅读 2018-09-02 15:26:59
    稀疏矩阵相乘-Python版 Given two sparse matrices A and B, return the result of AB. You may assume that A's column number is equal to B's row number. Example: A = [ ...

                                          稀疏矩阵相乘-Python版

    Given two sparse matrices A and B, return the result of AB.

    You may assume that A's column number is equal to B's row number.

    Example:

    A = [
      [ 1, 0, 0],
      [-1, 0, 3]
    ]
    
    B = [
      [ 7, 0, 0 ],
      [ 0, 0, 0 ],
      [ 0, 0, 1 ]
    ]
    
    
         |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
    AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                      | 0 0 1 |

    使用传统的矩阵相乘的算法肯定会处理大量的0乘0的无用功,所以我们适当的优化算法,我们知道一个 i x k 的矩阵A乘以一个 k x j 的矩阵B会得到一个 i x j 大小的矩阵C,那么我们来看结果矩阵中的某个元素C[i][j]是怎么来的,起始是A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][k]*B[k][j],那么为了不重复计算0乘0,我们首先遍历A数组,要确保A[i][k]不为0,才继续计算,然后我们遍历B矩阵的第k行,如果B[K][J]不为0,我们累加结果矩阵res[i][j] += A[i][k] * B[k][j]; 这样我们就能高效的算出稀疏矩阵的乘法,参见代码如下:

    # -*- coding: utf-8 -*-
    """
    Created on Sun Sep 02 15:10:34 2018
    
    @author: Administrator
    """
    def SparseMatrixMultiply(A, B):#减少计算次数
        res = [[0 for i in range(len(B[0]))] for j in range(len(A))]
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] != 0:#non-zero
                    for k in range(len(B[0])):
                        if B[j][k] != 0:#non-zero
                            res[i][k] += A[i][j] * B[j][k]
        return res
    if __name__ == '__main__':
        A = [[1,0,0],[-1,0,3]]
        B = [[7,0,0],[0,0,0],[0,0,1]]
        result = SparseMatrixMultiply(A, B)
        print(result)

    三元组方法

    typedef struct NODE{ //定义稀疏矩阵结点       
     int i;       //行
     int j;       //列
     int data;   //值
    } Node;
    typedef struct MATRIX{ //定义稀疏矩阵(可以快速访问)       
     int mu, nu, tu;      // mu为矩阵行数,nu为矩阵列数,tu为矩阵中非零元素的个数
     Node matrix[MAXSIZE+1];       
     int rpos[MAXR+1];
    } Matrix; 

    算法时间复杂度为:O(A->tu*B->tu/B->mu)

    此外还有十字链表法。

    Python科学计算包scipy

    import scipy as sp

    a = sp.sparse.linalg.norm(S, 'fro')

    展开全文
  • 稀疏矩阵相乘——三元组稀疏矩阵

    千次阅读 2016-12-15 20:03:28
    请编写并测试一个稀疏矩阵相乘的函数 matrix sparse_matrix_mul(const matrix&m1, constmatrix& m2) 其中matrix为一个描述稀疏矩阵的结构体: struct matrix { float* _elements; //矩阵中所有元素的数组(按列...
  • Matlab 的内置稀疏矩阵乘法函数会在不应该发生的情况下导致内存不足异常。 这个文件可以节省一天! 用“mex mex_amub.cpp”编译它。
  • 提出了一种应用于软件回归测试过程中的基于遗传算法的最小化测试用例集算法模型。该算法针对在软件回归测试过程中,测试套间内的测试用例间往往存在着重复覆盖测试需求的情况,因而测试套间中将存在着大量的冗余测试...
  • 稀疏矩阵相乘运算 一、目的 1.了解稀疏矩阵相乘运算特点 2.知道稀疏矩阵存储,创建,显示,转置方法 二、设计要求 1.问题描述 利用稀疏的特点进行存储和计算可大大节省存储空间,并实现稀疏矩阵相乘运算 2.需求分析 ...
  • 清华大学出版社数据结构稀疏矩阵相乘编程,程序不大。。。
  • 稀疏矩阵相乘代码

    2013-04-17 13:59:15
    一个计算稀疏矩阵相乘的小程序,数据结构课设题目
  • 但上面的算法内层循环里遍历每一行来检查每一行是否在对应的列中有元素,对于稀疏矩阵(大部分元素为nil或0的矩阵),这个循环除了遍历少量的非0元素,还遍历了很多的0元素,所以做简单的调换,避免遍历列: ...
  • 请编写并测试一个稀疏矩阵相乘的函数 matrix sparse_matrix_mul(const matrix& m1, constmatrix& m2) 其中matrix为一个描述稀疏矩阵的结构体: struct matrix { float* _elements; //矩阵中所有元素的数组(按...
  • 基于mapreduc框架的稀疏矩阵相乘运算。
  • 这道题让我们实现稀疏矩阵相乘,稀疏矩阵的特点是矩阵中绝大多数的元素为0,而相乘的结果是还应该是稀疏矩阵,即还是大多数元素为0,那么我们使用传统的矩阵相乘的算法肯定会处理大量的0乘0的无用功,所以我们需要...
  • Lua 稀疏矩阵相乘

    2020-02-12 09:40:18
    function mult ( a , b ) local c = { } for i = 1 , #a do local resultline ... 来处理稀疏的元素,这样可以只访问非 nil 的元素。此外,代码还删去了结果中偶然为0的元素。
  • 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵,实现两个矩阵相乘的运算。稀疏矩阵采用十字链表表示,而运算结果的矩阵则以通常的阵列形式列出。 测试用例见题集p136。 内容: 题目分析(ppt),完整工程文件...
  • c语言+稀疏矩阵相乘

    2009-11-22 00:05:46
    用c语言实现稀疏矩阵相乘,同时可以形象的打印出来
  • 数据结构试验中稀疏矩阵相乘的程序清单,多多学习,多多进步

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,551
精华内容 4,220
关键字:

稀疏矩阵相乘