一、什么是稀疏多项式

稀疏多项式（Sparse Polynomial）是指其中大部分项的系数为0的多项式。这种多项式通常用于解决存在许多未使用变量的数学问题，可以用更少的存储空间来表示这些多项式。在稀疏多项式中，只有一小部分项具有非零系数，而大多数项的系数为0。对于非稀疏的多项式，我们把补齐零项，把多项式写成：1×x6+0×x5+2×x4+5×x3+0×x2+1×x+01\times x^6+0\times x^5+2\times x^4+5\times x^3+0\times x^2+1\times x+0。

储存方式可以是：

float coef[7]={0,1,0,5,2,0,1};

然而对于稀疏的多项式如:x10000+xx^{10000}+x，若用常规的储存方法储存会占用很大的空间。我们通常采用结构体来储存，即:

struct {      float coef;      int exp; }

为了区分这类多项式，我们把它叫做稀疏多项式。

二、一元稀疏多项式

一元稀疏多项式简单计算器的基本功能是：

#include using namespace std;typedef struct PNode{    float coef;        //系数    int expn;          //指数    struct PNode *next;//指针域}PNode,*PnodeList;int InitList(PnodeList &L){L=new PNode;L->next=NULL;return 0; }void Createlist(PnodeList &P,int n){    PnodeList s,pre,q;    for(int i=1;i<=n;++i)          //依次输入n个非零项    {        s=new PNode;        cin>>s->coef>>s->expn;        pre=P;                 //用于保存q的前驱，初值为头结点        q=P->next;             //q初始化指向首元结点        while(q&&q->expn>s->expn)  //通过比较指数找到名列前茅个小于输入项指数的项*q        {            pre=q;            q=q->next;        }        s->next=q;                  //将输入项s插入到q和其前驱结点pre之间        pre->next=s;    }}void Opertion(PnodeList &pa,PnodeList &pb)//多项式运算：加法pa=pa+pb{    PnodeList p1,p2,p3,r;    int sum;    p1=pa->next;//p1,p2初值指向首元结点    p2=pb->next;    p3=pa;      //p3指向和多项式当前结点，初值为pa    while(p1&&p2)    {        if(p1->expn==p2->expn)        {              sum=p1->coef+p2->coef;            if(sum!=0)            {                p1->coef=sum;//修改pa为两系数的和                p3->next=p1;p3=p1;//将修改后的pa当前结点链在p3之后，p3指向p1                p1=p1->next;                r=p2;p2=p2->next;delete r;//删除pb当前结点            }            else            {                r=p1;p1=p1->next;delete r;//删除当前结点，指向后一项                r=p2;p2=p2->next;delete r;            }        }        else if(p1->expn>p2->expn)        {            p3->next=p1;     //将p1链在p3之后            p3=p1;            p1=p1->next;        }        else        {            p3->next=p2;     //将p2链在p3之后            p3=p2;            p2=p2->next;        }    }    p3->next=p1?p1:p2;   //插入非空多项式的剩余段    delete pb;}void Opertion1(PnodeList &pa,PnodeList &pb)//多项式运算：减法pa=pa-pb{    PnodeList p1,p2,p3,r;    int sum;    p1=pa->next;//p1,p2初值指向首元结点    p2=pb->next;    p3=pa;      //p3指向差多项式当前结点，初值为pa    while(p1&&p2)    {        if(p1->expn==p2->expn)        {              sum=p1->coef-p2->coef;            if(sum!=0)            {                p1->coef=sum;//修改pa为两系数的和                p3->next=p1;p3=p1;//将修改后的pa当前结点链在p3之后，p3指向p1                p1=p1->next;                r=p2;p2=p2->next;delete r;//删除pb当前结点            }            else            {                r=p1;p1=p1->next;delete r;//删除当前结点，指向后一项                r=p2;p2=p2->next;delete r;            }        }        else if(p1->expn>p2->expn)        {            p3->next=p1;     //将p1链在p3之后            p3=p1;            p1=p1->next;        }        else        {            p2->coef=0-p2->coef;            p3->next=p2; //将p2链在p3之后            p3=p2;            p2=p2->next;        }    }    if(p3->next=p1)  //插入非空多项式的剩余段        p3->next=p1;    else{        p3->next=p2;        while(p2)//第二段连上要变成负的       {        p2->coef=0-p2->coef;        p2=p2->next;       }    }    delete pb;}int main(){    PnodeList a,b;    InitList(a);    InitList(b);    int n1,n2;    cout<<"请输入pa表中的多项式项数：";    cin>>n1;    cout<<"请输入pa表的系数和指数：(格式：1 2)"<>n2;    cout<<"请输入pb表中的系数和指数：(格式：1 2)"<>m;    if(m=="+")      {        Opertion(a,b);        cout<<"相加的结果为：";        outlist(a);      }    else if(m=="-")      {        Opertion1(a,b);        cout<<"相减的结果为：";        outlist(a);      }    else        cout<<"当前运算符不在操作范围内！！！";    return 0;}

三、稀疏表示简介

1、稀疏表示概念

用较少的基本信号的线性组合来表达大部分或者全部的原始信号。其中，这些基本信号被称作原子，是从过完备字典中选出来的；而过完备字典则是由个数超过信号维数的原子聚集而来的。可见，任一信号在不同的原子组下有不同的稀疏表示。

假设我们用一个MN的矩阵表示数据集X，每一行代表一个样本，每一列代表样本的一个属性，一般而言，该矩阵是稠密的，即大多数元素不为0。 稀疏表示的含义是，寻找一个系数矩阵A（KN）以及一个字典矩阵B（MK），使得BA尽可能的还原X，且A尽可能的稀疏。A便是X的稀疏表示。

2、稀疏表示的应用

假设一条数据长度为1024的信号占用的储存空间为1 kb，在计算机内部会表示成大小为1024×1的矩阵，我们可以将其改写成32×32大小的信号矩阵。那么我们要传输这样的一个信号就需要1 kb的流量。

但由于信号的稀疏性质，我们可以将其表达为一个储存在本地的字典D，大小为32×64，和一个稀疏向量α，大小为64×32，因为稀疏表示的性质我们知道向量α中绝大部分位置上的数值为0，根据经验超过90%位置的数值为0，计算64×32×0.1=204.8，因此我们知道一般矩阵α中不会有超过205个有效值，因此我们记录每个值所在的位置，占用205个数据空间。因此现在我们如果需要传输这个长度为1024的信号，仅需要传输205×2大小的矩阵，消耗流量仅0.4 kb。

接收方在接受到这个矩阵后按特定的方式重构系数矩阵，再与储存在本地的字典做内积就得到了原始的长度为1024的信号，整个过程节省的数据传输流量为60%。需要注意的是，这只是一个很简单很粗浅的例子，实际情况比这复杂很多，但这已经足够表示稀疏在数据存储传输中的作用。

延伸阅读1：稀疏矩阵简介

矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵(sparse matrix)，该比值称为这个矩阵的稠密度；与之相区别的是，如果非零元素的分布存在规律（如上三角矩阵、下三角矩阵、对角矩阵），则称该矩阵为特殊矩阵。

上一篇

wait-free是指什么?

下一篇

文献管理的专业软件有哪些?