0

ブール配列「ベクトル」が「マトリックス」の列から線形に独立しているかどうかを確認する必要があるプロジェクトを行っています。MATLAB では、rank(gf([matrix vector])) コマンドを使用して、拡張行列 [matrix vector] のランクを見つけることで実行できます。'gf' は行列がブール値であるためです。しかし、C ++でそれを行う方法。これは私が試したことです：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "engine.h"
#define  BUFSIZE 256

int main()
{
Engine *ep;
mxArray *M = NULL, *V = NULL, *result = NULL;
bool matrix[4][4]={1,1,1,0,0,1,1,0,0,1,0,0}, vector[4][1]={1,1,1,1};
double *rank;

if (!(ep = engOpen("\0"))) {
    fprintf(stderr, "\nCan't start MATLAB engine\n");
    return EXIT_FAILURE;
}

V = mxCreateDoubleMatrix(4, 1, mxREAL);
M = mxCreateDoubleMatrix(4, 4, mxREAL);
memcpy((void *)mxGetPr(V), (void *)vector, sizeof(vector));
memcpy((void *)mxGetPr(M), (void *)matrix, sizeof(matrix));
engPutVariable(ep, "V", V);
engPutVariable(ep, "M", M);

engEvalString(ep, "R = rank(gf([M V]));");
result = engGetVariable(ep, "R");
engClose(ep);
rank = mxGetPr(result);
printf("%f", *rank);

printf("Done with LI\n");
mxDestroyArray(M);
mxDestroyArray(V);
mxDestroyArray(result);
engEvalString(ep, "close;");
}

上記のコードは機能し、望ましい結果が得られています。しかし、それは非常に遅いです。誰かがそれを速くする方法を私に提案できますか? または、ブール行列のランクを見つける他の方法を提案してください。いくつかのライブラリが出回っていますが、それらは int または double 行列に対してのみ関数を持っているようです。

4

2 に答える 2

1

2 のガロア体 (Matlab コードで行っているように) でランクを見つけることにより、ブール行列のランクを見つけることができます。これは、基本的に mod 2 演算です。

以下のコードは、部分的なピボットでガウス消去法を使用することにより、同じアイデアを使用してブール行列のランクを見つけます。

#include <iostream>
#include <vector>

using namespace std;

class BooleanMatrix{
    vector< vector<bool> > mat; //boolean matrix
    int n, m;           //size of matrix nxm
    int rank;           //rank of the matrix

    public:

    /*Constructor
     * Required Parameters:
     * M ==> boolean matrix
     * n ==> number of rows
     * m ==> number of columns
     */
    template <size_t size_m>
    BooleanMatrix(bool M[][size_m], int n, int m){
        this -> n = n;
        this -> m = m;
        for (int i = 0; i < n; i++){
            vector<bool> row(m);
            for (int j = 0; j < m; j++) row[j] = M[i][j];
            mat.push_back(row);         
        }
        gaussElimination();
    }

    /* Does Gauss Elimination with partial pivoting on the matrix */
     void gaussElimination(){
        rank = n;
        for (int i = 0; i < n; i++){
            if (!mat[i][i]){
                int j;
                for (j = i+1; j < n && !mat[j][i]; j++);
                if (j == n){
                       rank--;
                       continue;
                }
                else
                    for (int k = i; k < m; k++){
                        bool t = mat[i][k];
                        mat[i][k] = mat[j][k];
                        mat[j][k] = t;
                    }
            }
            for (int j = i+1; j < n; j++){
                if (mat[j][i]){
                    for (int k = i; k < m; k++)
                        mat[j][k] = mat[j][k] - mat[i][k];
                }
            }
        }
    }

    /* Get the row rank of the boolean matrix
     * If you require the rank of the matrix, make sure that n > m.
     * i.e. if n < m, call the constructor over the transpose.
     */
    int getRank(){
        return rank;
    }
};

int main(){
    bool M1[3][3] = {   {1, 0, 1},
                {0, 1, 1}, 
                {1, 1, 0}   };
    BooleanMatrix booleanMatrix1(M1, 3, 3);
    cout << booleanMatrix1.getRank() << endl;   

    bool M2[4][4] = {   {1,1,1,0},
                {0,1,1,0},
                {0,1,0,0},
                {1,1,1,1}   };
    BooleanMatrix booleanMatrix2(M2, 4, 4);
    cout << booleanMatrix2.getRank() << endl;   
}

これにより、両方のケースで期待どおりの結果が得られます。アルゴリズムは、すべての実用的な目的でうまく機能するはずです。ささいな改善とアプリケーション固有の変更は、要件に合わせて行うことができます。

私はそれを徹底的にテストしていません。誰かがバグを見つけた場合は、回答を編集して修正してください。

お役に立てれば。

于 2013-10-09T09:37:44.590 に答える
0

簡単な解決策は、演算子がブール値で定義されている最小二乗問題を解くことです。

min_x |matrix * x - vector|^2

次に、vectorが の列ベクトルの範囲内にある場合matrix、解の残差は非常に小さいはずです。

于 2013-10-08T20:16:24.520 に答える