Data Structure Lab Report 2 — Sparse Matrix Multiplication

2023-12-12 2023-12-12

Problem Analysis

The primary objective of this experiment is to develop a sparse matrix multiplication algorithm capable of multiplying two sparse matrices, A and B, and outputting the resulting matrix C. In this algorithm, sparse matrices are represented using triplets, and users can input different matrix data multiple times to compute their products.

Algorithm Design

The sparse matrix multiplication algorithm is designed as follows:

A struct is used to represent the matrix, which includes the number of rows (m), columns (n), the count of non-zero elements (L), and an array to store node information.
The input function input retrieves the triplet representation of the matrix, checks the validity of the input, and stores it in the memory structure.
The output function output prints the sparse matrix in standard matrix form for user review.
The matrix multiplication function multiplier takes two input matrices, A and B, computes their product, and stores the result in matrix C.

Data Structure Design

The matrix struct contains the number of rows (m), columns (n), the count of non-zero elements (L), and the Ma array for storing node information.
The node struct represents each non-zero element in the sparse matrix, including the row index (i), column index (j), and the element value (data).

Debugging Process

The code includes error-handling mechanisms, such as validating input legality, checking memory allocation success, and ensuring matrix multiplication compatibility.
When inputting sparse matrix data, users receive error messages and are prompted to re-enter data if it exceeds the matrix dimensions.
The sparse matrix multiplication algorithm checks whether the columns of the first matrix match the rows of the second matrix to ensure valid multiplication.

Output Results

Pasted image 20231020161652.png
Matlab verification results:
Pasted image 20231020161908.png
Pasted image 20231020161929.png

Users can input two matrices, A and B, and the program will compute their product and output the resulting matrix C. Users may choose to continue with additional sparse matrix multiplications or exit the program. The program runs continuously until the user opts to exit.

Summary

Overall, this experiment successfully implements sparse matrix multiplication, providing a user-friendly interface and robust error-handling mechanisms to ensure valid matrix input. It correctly computes the product of two sparse matrices and outputs the result in standard matrix form.

Source Code

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000

struct node{
    int i;
    int j;
    int data;
};
struct matrix{
    int m;
    int n;
    int L;
    node* Ma[MAX];
};

int input(matrix* A){
    int m,n,data;
    for(int i=0;i<A->L;i++){
        cin>>m>>n>>data;
        if(m<0||m>=A->m||n<0||n>=A->n){
            cout<<"Input error: Row/column exceeds matrix dimensions!"<<endl;
            return 1;
        }
        A->Ma[i]=(node*)malloc(sizeof(node));
        if(!A->Ma[i]){
            cout<<"Memory allocation failed!"<<endl;
            return 2;
        }else{
            A->Ma[i]->i=m;
            A->Ma[i]->j=n;
            A->Ma[i]->data=data;
        }
    }
    return 0;
}

void output(matrix* A,string name){
    cout<<"Matrix "<<name<<":"<<endl;
    int nums[A->m][A->n];

    memset(nums,0,sizeof(nums));
    for(int i=0;i<A->L;i++){
        nums[A->Ma[i]->i][A->Ma[i]->j]=A->Ma[i]->data;
    }
    for(int i=0;i<A->m;i++){
        for(int j=0;j<A->n;j++){
            cout<<nums[i][j]<<'\t';
        }
        cout<<endl;
    }
}

void multiplier(matrix* A,matrix* B,matrix* C){
    C->m=A->m;
    C->n=B->n;
    C->L=0;
    int x,y,z;
    bool found=false;
    for(int i=0;i<A->L;i++){
        for(int j=0;j<B->L;j++){
            if(A->Ma[i]->j==B->Ma[j]->i){ // Column of A matches row of B
                x=A->Ma[i]->i;
                y=B->Ma[j]->j;
                z=A->Ma[i]->data*B->Ma[j]->data;
                found=false;
                for(int k=0;k<C->L;k++){
                    if(x==C->Ma[k]->i&&y==C->Ma[k]->j){
                        C->Ma[k]->data+=z;
                        found=true;
                        break;
                    }
                }
                if(!found){
                    C->L++;
                    C->Ma[C->L-1]=(node*)malloc(sizeof(node));
                    C->Ma[C->L-1]->i=x;
                    C->Ma[C->L-1]->j=y;
                    C->Ma[C->L-1]->data=z;
                }
            }
        }
    }
}

int main(){
start:
    matrix* A=(matrix*)malloc(sizeof(matrix));
    matrix* B=(matrix*)malloc(sizeof(matrix));
    matrix* C=(matrix*)malloc(sizeof(matrix));
    cout<<"Enter triplet length, rows, and columns for matrix A:"<<endl;
    cin>>A->L>>A->m>>A->n;
    cout<<"Enter matrix A:"<<endl;
    if(input(A)){
        cout<<"Error detected. Please re-enter!"<<endl;
        goto start;
    }
    output(A,"A");
    cout<<"Enter triplet length, rows, and columns for matrix B:"<<endl;
    cin>>B->L>>B->m>>B->n;
    cout<<"Enter matrix B:"<<endl;
    if(input(B)){
        cout<<"Error detected. Please re-enter!"<<endl;
        goto start;
    }
    output(B,"B");
    multiplier(A,B,C);
    output(C,"C");

    cout<<"Continue sparse matrix multiplication? (y/n):";
    char choice;
choice_input:
    cin>>choice;
    if(choice=='y'||choice=='Y'){
        goto start;
    }else if(choice=='n'||choice=='N'){
        return 0;
    }else{
        cout<<"Invalid input. Please re-enter:";
        goto choice_input;
    }
    return 0;
}

New version found