用本征求解小型齐次线性系统的最快方法

Question

我需要求解许多 Ax=0 形式的小 (n=4) 齐次线性系统，其中 A 是奇异矩阵。我目前正在使用以下代码：

void solve(const matrix_t& A, vector_t& x){
    auto svd = A.jacobiSvd(Eigen::ComputeFullU | Eigen::ComputeFullV);
    auto V = svd.matrixV();
    x = V.col( A.rows() - 1 );
    x.normalize();
}

有没有更快的方法？

Answer 1

获得具有特征的一般矩阵的零空间的最快方法是使用其 LU 分解。在实践中，我使用 Householder QR 分解而不是 LU，因为当输入矩阵不是完全奇异时它似乎更稳定。 QR 仍然比问题中提出的 SVD 快很多，并且为我的问题提供了非常相似的结果。可以在此处找到不同特征分解的基准：https://eigen.tuxfamily.org/dox/group__DenseDecompositionBenchmark.html

用 LU、QR 和 SVD 计算零空间的代码（注意：x.normalize() 不是必需的，但有助于比较解决方案）：

template<typename matrix_t, typename vector_t>
void solveNullspaceLU(const matrix_t& A, vector_t& x){
    x = A.fullPivLu().kernel();
    x.normalize();
}

template<typename matrix_t, typename vector_t>
void solveNullspaceQR(const matrix_t& A, vector_t& x){
    auto qr = A.transpose().colPivHouseholderQr();
    matrix_t Q = qr.householderQ();
    x = Q.col(A.rows() - 1);
    x.normalize();
}

template<typename matrix_t, typename vector_t>
void solveNullspaceSVD(const matrix_t& A, vector_t& x){
    x = A.jacobiSvd(Eigen::ComputeFullV).matrixV().col( A.rows() - 1 );
    x.normalize();
}

用本征求解小型齐次线性系统的最快方法

Fastest way to solve small homogeneous linear systems with eigen

c++

linear-algebra

eigen