如何在C++中使用Eigen库来加速我的功能？

Question

我试图从使用for循环的C++程序获得一系列Squarts残余总和(RSS).我曾经RcppEigen.package.skeleton()无缝地结合使用C++和R.而当我使用788rows*857cols运行数据X和使用788rows*1cols运行Y时,C++程序的运行时间是用户(4.62s)系统(3.87s)已经过去(8.51s) ),R程序的运行时间是用户(8.68s)系统(1.78s)过去(10.53s).C++程序比R快.我使用的平台是带有8G RAM的win7(X64).我怎么能加快我的计划？任何帮助将不胜感激.

这是C++程序:

#include <RcppEigen.h>

//*---get Residual Sum of Squarts via Matrix Operation
//fastLm()
double getRSS(const Eigen::MatrixXd& X, const Eigen::MatrixXd& Y){
   Eigen::MatrixXd RSS=((Y-X*((X.transpose()*X).inverse()*X.transpose()*Y)).transpose())*(Y-X*((X.transpose()*X).inverse()*X.transpose()*Y));
   double RSSd = RSS.determinant();   
   return RSSd;             
}

//*---get F value from RSS and df
double getFval(double RSS1,double RSS2, int n1,int n2,int nObs){
  return (RSS1-RSS2)/(n1-n2)/(RSS2/(nObs-n2-1));      
}

//*---remove p columns from  i-th collumn of matrix
Eigen::MatrixXd removeColumn(const Eigen::MatrixXd& matrix, unsigned int i,int p){
    unsigned int numRows = matrix.rows();
    unsigned int numCols = matrix.cols()-p;

    Eigen::MatrixXd X;
    X=matrix;
    if( i < numCols )
        X.block(0,i,numRows,numCols-i) = matrix.block(0,i+p,numRows,numCols-i);

    X.conservativeResize(numRows,numCols);
    return X;
}

// [[Rcpp::export]]
Rcpp::List getPIcvalue(bool findIn,int p,int n, const Eigen::VectorXd& varIn, const Eigen::MatrixXd& Y,const Eigen::MatrixXd& Xf,const Eigen::MatrixXd& X0){
          //  varIn=(0,1,0,1...,0); p=1 :addition or elimination column; findIn=false,add 1 column of Xf to X0, findIn=false,eliminate 1 column to X0. n=X0.rows();
    bool valid;     
    valid=true;  
    double FitStat1;
    FitStat1 = 1e+10;              

    int pointer;
    pointer=-2;
    double FitStat;
    int nR = n-X0.cols();   // n is the X0.rows()
    int nF;     //nF=nR-1  //findIn=false
    double RSSr;
    double RSSf;
    double F_value;
    RSSr = getRSS(X0,Y);
    int k;
    if(false==findIn){
        k = p;                  
    }else{
        k = -p;      
    }
    Eigen::MatrixXd X(n,X0.cols()+k); 

    if(false==findIn){
        for(int i=0;i<Xf.cols();i++){
            if(0==varIn[i]){
                X<<X0,Xf.col(i);   // X: combine X0 and ith column of Xf                  
                nF = n-X.cols();     
                RSSf = getRSS(X,Y);
                FitStat = getFval(RSSr,RSSf,X.cols(),X0.cols(),n);
                //FitStat = getPvalue(F_value,nF,nR); 
                if(FitStat<FitStat1){
                    FitStat1=FitStat;
                    pointer=i;                    
                }                 
            }//varIn     
        }//for i                 
    }else{
        for(int i=1;i<X0.cols();i++){
            X =  removeColumn(X0,i,p);       
            RSSf = getRSS(X,Y);
            FitStat = getFval(RSSf,RSSr,X0.cols(),X.cols(),n);
            //FitStat = getPvalue(F_value,nR,nF); 
            if(FitStat<FitStat1){
                FitStat1=FitStat;
                pointer=i;                    
            }                 
        }//for i    
    }//findIn 
    return Rcpp::List::create(Rcpp::Named("keyV")=FitStat1,
                              Rcpp::Named("keyP")=pointer+1,
                              Rcpp::Named("keyR")=valid);
}

Answer 1

您对RSS矩阵公式的表达式效率极低.你做这个:

Eigen::MatrixXd RSS = (
  (Y - X * 
    ( ( X.transpose() * X ).inverse() * X.transpose() * Y ) 
  ).transpose() ) * 
  ( Y - X * 
    ( ( X.transpose() * X ).inverse() * X.transpose() * Y ) 
  );

这显然是非常重复的,并且多次重新计算相同的昂贵操作.转置矩阵应该非常便宜,除非它最终需要复制.但是反转一个矩阵(即使是对称的正定矩阵,就像这里的情况一样,除非你告诉它,Eigen不知道)是非常昂贵的.哎..甚至矩阵乘法都很昂贵.

您可能会认为Eigen做了一些引人注目的魔术来消除冗余操作,并找到最有效的操作序列来获得结果.但是Eigen在这方面保持相当保守(依赖于在编译时解析的保守表达式模板,当它真的应该使用运行时表达式优化时).所以,这里真的不会那么多.您需要通过自己完成这项工作来帮助它删除冗余操作.

最后,你可以结合反转并做线性系统解决方案,而不是(而不是乘法A = inv(X) * B,你这样做solve(X * A = B)),这也允许你指定最合适的分解(在这里,它要么LLT或活体肝移植,这取决于如何良好条件你期望你的矩阵(Xt*X)是).

你得到这个:

auto Xt = X.transpose(); //<- deduce the type with 'auto' to avoid copy-evaluation of the transpose.
const Eigen::MatrixXd A = X * ( Xt * X ).ldlt().solve(Xt);
const Eigen::MatrixXd Y_AY = Y - A * Y;
Eigen::MatrixXd RSS = Y_AY.transpose() * Y_AY;

但实际上,你可以进一步实现了优化这X * (Xt * X)^-1 * Xt * Y实际上相当于X * B地方B是最小二乘解决方案X*B = Y.如果你使用QR方法(不要在这里使用SVD,它总是矫枉过正而且很慢,我不明白为什么它甚至在Eigen docs中被提到作为线性最小二乘的可行方法(可能是因为Eigen人是业余爱好者!)),你可以这样做:

const Eigen::MatrixXd B = X.colPivHouseholderQr().solve( Y );
const Eigen::MatrixXd Y_XB = Y - X * B;
Eigen::MatrixXd RSS = Y_XB.transpose() * Y_XB;

这应该比以前更快(至少,在时间复杂度方面,这应该快几个数量级).

此外,如果Y碰巧是一个方阵,那么你应该计算它的行​​列式Y_XB并将其平方,而不是用它自己的转置计算其乘积的行列式.这将删除一个矩阵乘法(并复制到RSS).

最后,我没有太多关注你的其他函数(调用getRSS),但是你应该尽一切可能避免重新计算(在每次迭代时)不改变或不改变太多的东西,比如X的QR分解.有一些方法可以在X的变化中保持QR分解,但这比我在这里可以详细说明的要多,而且可能不是你可以用Eigen做的事情.